NAME

Tie::LazyList - Perl extension for lazy lists growing on demand

SYNOPSIS

  use Tie::LazyList;

  # lazy list of factorials
  tie @arr,  'Tie::LazyList', [ 1 ], 'FACT';
  tie @arr2, 'Tie::LazyList', 1, sub { my ( $array_ref, $n ) = @_; $array_ref->[ $n - 1 ] * $n };
  tie @arr3, 'Tie::LazyList', \@arr;
  print "$_\n" for @arr;   # prints ( eternally ) values of 1!, 2!, 3! ..
  print "$_\n" for @arr2;  # the same
  print "$_\n" for @arr3;  # the same

  # lazy list of powers of 2
  tie @arr,  'Tie::LazyList', 2, 'POW';
  tie @arr2, 'Tie::LazyList', 1, sub { my ( $array_ref, $n ) = @_; $array_ref->[ $n - 1 ] * 2 };
  tie @arr3, 'Tie::LazyList', \@arr2;
  print $arr [ 10 ], "\n", # prints 1024 = 2^10
        $arr2[ 10 ], "\n", # the same
        $arr3[ 10 ], "\n"; # the same

  # lasy lists of Fibonacci numbers, arithmetical/geometrical progressions and their sums, etc ..

DESCRIPTION

Tie::LazyList allows you to create lazy lists ( "infinite lists, whose tail remain unevaluated", Watt ) growing on demand with user-defined generation function.

What you have is a usual Perl array whose elements are generated by some function and which may be accessed by $arr[x] as any other, but actually grows under the hood if the element you're accessing isn't generated yet. This way, the amount of memory wasted for the array is no more ( and no less, unfortunately ) then you need. Think about it as dynamically growing factorials ( Fibonacci numbers, arithmetic progression .. ) table which you can access for any element without need to explicitly build and maintain it.

All you need to specify is the initial list elements, generation function and .. that's it, actually - go and work with it ! See the example above - I think, they demonstrate the simplicity.

So, here are the rules : you create the new lazy list by

tie @array, 'Tie::LazyList', list init, generation function

or

tie @array, 'Tie::LazyList', ARRAY reference

where

list init

Initial elements of your list. It may be a single scalar variable ( number, usually ) or an array reference ( if you'd like to initialize more then one element ). Examples : 1 or 2 or [ 1, 2, 3 ]

generation function

Reference to the function which will be called to generate new list elements. When called it'll be passed the following parameters :

• reference to the array filled from index 0 upto n-1

• n - index of the element to generate

The function should return the value of the n-th array element.

In order to make our life a bit easier there is a number of, what I call, code abbreviations. It means that generation function may be not the code reference, but something much simpler - string, having one of the predefined values. Those values tell the module which generation function to use and they are :

APROG

Means arithmetic progression, list init should contain at least two elements in order to calculate progression's factor.

GPROG

Means geometric progression, list init has the same restriction as in APROG.

APROG_SUM

Means arithmetic progression's summary, list init should contain, again, at least two elements, but of the original progression !

GPROG_SUM

Means geometric progression's summary, list init has the same restriction as in APROG_SUM.

FIBON

Means Fibonacci numbers, list init should contain at least two elements ( [ 0, 1 ], as you know )

FACT

Means factorials, list init should contain one element at least ( 1, as you know )

POW

Means power - arising x to any power, list init should contain only numbers.

???

I'm not a mathematician .. If you have more ideas, send them to genie@cpan.org !

ARRAY reference

Reference to another array, already tied to Tie::LazyList.

EXAMPLES

  # lazy list of fractions 1/(2^n) - 1, 1/2, 1/4, 1/8 ..
  tie @array,  'Tie::LazyList', 1, sub { my( $array_ref, $n ) = @_; $array_ref->[ $n - 1 ] / 2 };

  # the same
  tie @array,  'Tie::LazyList', [ 1, 0.5 ], 'GPROG';

  # lazy list of above geometric progression's summary : arr[ n ] = 1 + 1/2 + 1/4 + .. + 1/(2^n)
  tie @array,  'Tie::LazyList', [ 1, 0.5 ], 'GPROG_SUM';

  # creating tied array from another tied array
  tie @array2, 'Tie::LazyList', \@array;

  # prints 1.99999904632568 = 1 + 1/2 + 1/4 + .. + 1/(2^20)
  print $array[ 20 ];

  # the same
  print $array2[ 20 ];

  # ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  # lazy list of Fibonacci numbers
  tie @array, 'Tie::LazyList', [ 0, 1 ], 'FIBON';

  # the same
  tie @arr2,  'Tie::LazyList', \@array;

  # prints 13 = 5 + 8
  print $array[ 7 ];

  # the same
  print $arr2[ 7 ];

  # ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  # lazy list of factorials
  tie @array, 'Tie::LazyList', 1, 'FACT';

  # prints 1.19785716699699e+100 = 70!
  print $array[ 70 ];

  # ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  # lazy list of powers of e
  tie @array, 'Tie::LazyList', 2.718281828, 'POW';

  # prints 148.413158977261 = e^5
  print $array[ 5 ];

ALLOWED ARRAY OERATIONS

Having tied an array what operations can you do with it ? Does it support a usual array operations like pop, push and splice ? The answer to the first question - not so many, actually. The answer to the second question is further shorter - no, it doesn't.

The only operations an array tied to Tie::LazyList currently supports are element access $arr[x] and for ( @array ) eternal iteration ( isn't it great already ? ). Trying to apply anything else is a fatal error. Some functions ( like storing ) doesn't have any sense in lazy lists, others ( like filtering via grep ) may be implemented later ..

LOCALITY

There's a $Tie::LazyList::locality variable stating how many additional list elements should be evaluated when expanding it. It's default value is 10 and it means whenever list should grow to index n it'll actually grow to index n + 10. You may set it to any number you like, but note that my benchmarks showed that locality equal to 0 makes iteration from arr[0] to arr[1e6] about 30% slower then iteration from arr[1e6] to arr[0] ( which is, obviously, the fastest in the total time ), while iteration with locality equal to 10 showed the same result "in both directions". Locality equal to 100 and 1000 didn't bring any further speedup, so 10 looks Ok.

TODO

1. Apply map and grep on lazy lists

BUGS

Not found yet

SEE ALSO

perltie

Object Oriented Perl by Damian Conway ( yeap, I've mentioned it too now )

AUTHOR

Goldin Evgeny <genie@cpan.org>

COPYRIGHT

Copyright (c) Goldin Evgeny. All rights reserved.

This library is free software. You can redistribute it and/or modify it under the same terms as Perl itself.

cpanm Tie::LazyList

perl -MCPAN -e shell
install Tie::LazyList