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

Robert Dockins robdockins at fastmail.fm
Fri Oct 8 08:35:40 EDT 2004

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?


Simon Marlow wrote:

> On 07 October 2004 18:23, Ketil Malde wrote:
>>Couldn't readFile et al. provide the standard interface, but use
>>hGetBuf tricks (e.g. from your 'wc' entry) behind the curtains?
> readFile does do buffering behind the scenes, that's not the problem.
> The problem is doing the computation on a [Char] instead of a raw buffer
> of bytes.
> There are various known techniques that could be used to speed up GHC's
> implementation of lists, none of which we've ever tried.  This might be
> a good area for experimentation, if anyone's looking for something to do
> in GHC.
> Cheers,
> 	Simon
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

More information about the Haskell-Cafe mailing list