[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: info-mcl@cambridge.apple.com*Subject*: Re: Continuations and immutable lists (Was: Re: Handler-Bind question...)*From*: cokasaki+@cs.cmu.edu (Chris Okasaki)*Date*: 30 Sep 1994 19:50:51 GMT*Organization*: School of Computer Science, Carnegie Mellon*References*: <36esve$afu@kernighan.cs.umass.edu>, <36hlh7$qgv@larry.rice.edu>*Sender*: owner-info-mcl@cambridge.apple.com

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 | | -------------------------------------------------------------------------------

**References**:**Handler-Bind question...***From:*schmill@earhart.NOT.SET (Matt Schmill)

**Continuations and immutable lists (Was: Re: Handler-Bind question...)***From:*drichter@owlnet.rice.edu (David Richter)

- Prev by Date:
**Re: Damaged literals?** - Next by Date:
**TCP problems only on *some* macintoshes...?** - Previous by thread:
**Continuations and immutable lists (Was: Re: Handler-Bind question...)** - Next by thread:
**Re: Handler-Bind question...** - Index(es):