[Haskell-cafe] Algebraic Collections [was: OCaml list sees abysmal...]

[Greg Buchholz]

Robert Dockins 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.  Obviously lazy and infinite lists add some wrinkles, but 
> I think it could be worked through.
> 
> BTW can you give some references to these known techniques?
>

    Don't know if this is exactly what you are looking for, but I found
these articles quite interesting.

    http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/
    http://www.stud.tu-ilmenau.de/~robertw/dessy/fun/democratic/


Greg Buchholz