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

[Ketil Malde]

William Lee Irwin III <wli at holomorphy.com> writes:

>> 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.

Uh, I think one of the main problems with the usual IO functions is
that it adds the overhead of cons cells and optionally 32bit chars
(although I think GHC packs them for char values <256) - when you
really want an (unboxed) array of Word8.

>> 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.

I'm as dumb as anybody, but it seems to me that one could read a lazy
chain (list) of buffers as UArray Int Word8, and tack a list-type
interface (head, tail, cons...) interface on top.

-kzm
-- 
If I haven't seen further, it is by standing in the footprints of giants