The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.

# 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