[Haskell-cafe] Re: OCaml list sees abysmal Language
MR K P SCHUPKE
k.schupke at imperial.ac.uk
Fri Oct 8 12:49:02 EDT 2004
Doubly linked lists do not work very well in functional languages.#
when you have a list [1,2,3] and you prepend a value [9,1,2,3] the language
relies on the fact that the list tail [1,2,3] is not chainged by this operation.
This means the list can be "prepended-in-place". With a doubly linked list the
 cell would be changes (the 'left' pointer is changed from null to point to
the  cell)... The result of this is that with a doubly linked list the
_whole_ list must be copied when prepending a single value. In other words
in a functional language, a doubly linked list will make ':' as hard as '++'
and not the other way round!
More information about the Haskell-Cafe