lazy_lists.at

It can be important to avoid evaluating the thunk defining an infinite list
more than once, but instead store the values that have already been computed.
Indeed this will make it possible to define a non-pure function as thunk that
simply assumes that each successive call is done to produce the coefficient
following the one of the previous call; this assumes that no access to the
function is exported other than the one given to the |memoize| function below.

Another application is when we want to solve a recursion like that of
Fibonacci by directly referring, via a |shift|, to previous values of the list
under construction. This remains delicate, since a simple application of
|memoize| will not suffice, and probably will not often prove to be the best
choice of strategy to solve a recurrence relation.

The function |memoize| adds the necessary storage on top of an infinite list:
before actually calling the thunk, it defines a variable that can store the
node produced, but initially stores nothing. The first time the memoized
function is called, the thunk is called and the result stored, from which
further calls will retrieve it. The magic comes from applying |memoize|
recursively to the tail, before storage.

Formal power series

arithmetic of $\Z[[X]]$, using |inf_list| to represent the elements

here the final result is not passed through |memoize|; if that is desired
the caller should take care to do so

As a proof of concept we show how an infinite list can be recursively
defined using itself (taking care to not make any coefficient require itself)
and use |memoize| to avoid re-evaluating previous terms while computing new
ones. The standard example is to compute the Fibonacci sequence F as 0, 1,
followed by |sum(f,shift(1,F))| (where the first argument to |sum| gives the
coefficient two steps before, the second argument the preceding coefficient).

Using |memoize| remains delicate here, since the |rec_fun| syntax does not
allow anything being done before introducing arguments, as might be thought:
|rec_fun signs = inf_list: memoize(@:(1,@:(-1,signs)))| (NOT SYNTACTIC).
And calling |memoize| inside the function body, necessarily multiple times
if there are multiple recursive uses as is the case for Fibinacci, creates
separate memo tables for each call (even with identical arguments) which
solves nothing (as a general rule, the argument to |memoize| should not be
allowed to be named and accessed elsewhere, lest the efficiency be lost when
those other accessed recompute anyway what |memoize| stores). A solution is
to tie the recursive knot by hand, rather than have |rec_fun| do it for us.

Note that leaving out |memoize| would be possible here, but makes the runtime
increase exponentially with the list length because of repeated evaluations of
the same list elements. That inefficient version would also be obtained by
| set rec_fun Fibo () = inf_node:(0,@:(1,sum(Fibo,shift(1,Fibo))))) |

and note Fibonacci is also |inverse([1,-1,-1].extend_0)|, easy and efficient

The pentagonal numbers are those obtained by adding to a perfect square $k^2$
either the "lower" |binom(k,2)| or "upper" |binom(n+1,2)| triangular number;
call these the lower and uppoer pentagonal numbers for $k$.
Euler's pentagonal series has entries $(-1)^k$ at indices the lower and upper
pentagonal numbers for $k$, for every $k\in\N$, and $0$ at all other indices.
The relavance of Euler's pentagonal  series is that its inverse is the
generating series for the number of partitions of a natural number.

A practical way to generate it is to start at index 0, the upper pentagonal
number for 0, with variables k=0, lower=false and a timer i=1. Then to
generate a term, decrement the timer; if still positive return a term 0.
Otherwise return (-1)^k, and if lower holds set the timer i:=k else (not lower)
increment k and set i to the sum of the old and new values of k; also invert
lower in all productive cases. The code below is a bit slicker and clearer.

e.g., |substitute ([0,1,1].extend_0)(ones)| gives series 1/(1-X-X^2)

e.g., compositional_inverse([0,1,-1].extend_0) solves $f-f^2=X$