[Haskell-cafe] Re: OCaml list sees abysmal Language Shootoutresults

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
[1] cell would be changes (the 'left' pointer is changed from null to point to
the [9] 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 mailing list