[Haskell-cafe] Re: appending an element to a list

[apfelmus]

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.

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