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
_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
