On Fri, Oct 08, 2004 at 08:35:40AM -0400, 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?
Ugh, lousy cache properties... try rank-ordered B+ trees. There are probably better choices than that even. It's probably best Simon point us to references to what's actually useful here. -- wli _______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
