Re: Continuations and immutable lists (Was: Re: Handler-Bind question...)

[cokasaki+@cs.cmu.edu (Chris Okasaki)]

In article <36hlh7$qgv@larry.rice.edu>,
David Richter <drichter@owlnet.rice.edu> wrote:
>Playing around with this, one comes to the conclusion that
>implementing the continuation is equivalent to implenting
>cons/car/cdr/append for (non-mutable) lists.  The usual representation
>has cons, car, and cdr at O(1), but then append is O(n).  By
>representing lists with trees (figuring that if continuations are
>composed then they will also sometimes be discarded, so we can delay
>flattening the tree until necessary), we can make cons and append O(1)
>and car/cdr O(log n).  We could also push car/cdr to be O(1) (with a
>bigger constant) by having cons/append be O(n) (with a smaller
>constant) by requiring the tree to be never more than x levels deep.
>...
>PS: And if anyone knows a better way to implement immutable lists, I
>(and various others including the authors listed above) would love to
>hear from you.

If the only operations you care about are cons/car/cdr/append, I
believe the best known implementation is found in

  "Confluently Persistent Deques via Data-Structural Bootstrapping"
  Adam Buschsbaum and Robert Tarjan
  SODA '93, pp 155-164 (or Princeton CS-TR-420-93)

They present a data structure that supports O(1) cons/append and
O(log* k) car/cdr.  (Remember that log* is the iterated log, which
for all practical purposes is a small constant.)  Although these bounds
are amortized, they explain that the bounds can be made worst-case by
employing as subroutines a purely functional implementation of constant-time
deques without appeand, such as found in Chuang&Goldberg's FPCA '93 paper [or 
Robert Hood's thesis (Cornell TR 82-503) or Okasaki's JFP paper (to appear, 
ftp-able from loch.mess.cs.cmu.edu in /afs/cs/project/fox/ftp/queue.tar.gz)].

Chris
-- 
-------------------------------------------------------------------------------
| Chris Okasaki       |                          Life is NOT a zero-sum game! |
| cokasaki@cs.cmu.edu |                                                       |
-------------------------------------------------------------------------------