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

[William Lee Irwin III]

At some point in the past, someone wrote:
>> Actually, I've been wondering about this.  If my understanding is 
>> correct, Haskell lists are basicly singly-linked lists of cons cells (is 
>> that correct?)  A simple (I think) thing to do would be to make the 
>> lists doubly-linked and circular.  That would let us do nice things like 
>> have O(1) primops for reverse, tail, (++) and other things that access 
>> lists at the end.  However, I'm still pretty new to FP in general, so I 
>> don't know if there are any theoretical reasons why something like this 
>> couldn't work.

On Fri, Oct 08, 2004 at 02:42:28PM +0100, Keith Wansbrough wrote:
> x = [3,5,7]
> primes = 2:x
> odds = 1:x
> You can't do sharing like this if your lists are doubly-linked; lots
> of cool algorithms depend on this sharing.

That constraint makes various other things painful. I suppose there is
no one-size-fits-all solution.


-- wli