Abhay Parvate wrote:

I somehow thought it would be easy to talk about complexity of calculating individual elements in an infinite list should be sufficient, but that seems to be involved, and my over-generalization doesn't seem to work. Thanks for the link; particularly it has reference to Wadler's papers exactly on this problem.

## Advertising

`Note however that Wadler's and similar formalisms are still a`

`unsatisfactory in that they are quite clumsy to work with, it's quite`

`tedious/impossible to analyze examples with a lot of lazy evaluation.`

`But they are a good guideline.`

`In his book about purely functional data structures [1], Okasaki takes a`

`different approach; each node of a data structure is given a debit, a`

`cost to evaluate it. For instance, consider`

xs = x1 : x2 : x3 : ... : xn : [] 1 1 1 ... 1 1 0 ys = y1 : y2 : y3 : ... : ym : [] 1 1 1 ... 1 1 0

`The numbers below indicate the time it takes to evaluate the node to`

`weak head normal form. For demonstration purposes, I arbitrarily chose 1`

`for each (:) here.`

The combined list will then have debits like xs ++ ys = x1 : x2 : x3 : ... : xn : y1 : y2 : y3 : ... : ym : [] 2 2 2 ... 2 2 1 1 1 ... 1 1 0

`In other words, the ys list is copied verbatim but each element of xs`

`incurs an additional cost of 1, corresponding to one step in the`

`evaluation of the concatenation with (++).`

`In order to force/inspect a constructor/node, you have to pay off its`

`debits first. In the above example, head (xs ++ ys) would have to pay`

`2 units of time (one unit for head xs and one for the (++)). Now, the`

`thing about debits is that we can relocate them to the top and only`

`overestimate the total running time if we do that. For instance, we`

`could push all debits to the top`

xs ++ ys = x1 : x2 : x3 : ... : xn : y1 : y2 : y3 : ... : ym : [] 2n+m 0 0 ... 0 0 0 0 0 ... 0 0 0

`so that evaluating head (xs ++ ys) is now estimated to cost (2n+m)`

`units of time while the rest is free/fully evaluated.`

The above example is rather useless, but consider the case n == m and xs = x1 : x2 : x3 : ... : xn : [] 0 0 0 ... 0 0 0 ys = y1 : y2 : y3 : ... : yn : [] 0 0 0 ... 0 0 0 i.e. two fully evaluated lists of the same length. Then, we have xs ++ reverse ys = x1 : x2 : x3 : ... : xn : yn : y{n-1} : ... : y1 : [] 1 1 1 ... 1 1 n 0 ... 0 0 0

`because reversing the list ys is "monolithic", i.e. looking at its head`

`already forces the tail of the list. But now, we can distribute the`

`debits upwards`

xs ++ reverse ys = x1 : x2 : x3 : ... : xn : yn : y{n-1} : ... : y1 : [] 2 2 2 ... 2 2 0 0 ... 0 0 0

`and thereby amortize the cost of reversing the second lists over the n`

`elements of the first list. This is used in the implementation of purely`

`functional queues, see also Okasaki's book.`

[1]: Chris Okasaki. Purely Function Data Structures. http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf (This is the thesis on which the book is based.) Regards, apfelmus _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe