Tie::LazyList - Perl extension for lazy lists growing on demand
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 ..
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 :
0
upto n-1
n
- index of the element to generateThe 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 :
Means arithmetic progression, list init
should contain at least two elements in order to calculate progression's factor.
Means geometric progression, list init
has the same restriction as in APROG.
Means arithmetic progression's summary, list init
should contain, again, at least two elements, but of the original progression !
Means geometric progression's summary, list init
has the same restriction as in APROG_SUM.
Means Fibonacci numbers, list init
should contain at least two elements ( [ 0, 1 ]
, as you know )
Means factorials, list init
should contain one element at least ( 1
, as you know )
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
.
# 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 ];
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 ..
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.
Not found yet
Object Oriented Perl by Damian Conway ( yeap, I've mentioned it too now )
Goldin Evgeny <genie@cpan.org>
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.