[Haskell-cafe] Reference for technique wanted

[Stephen Tetley]

On 2 November 2010 04:18, Richard O'Keefe <ok at cs.otago.ac.nz> wrote:
[SNIP]

> SML/NJ MLton
>  0.899 0.244    boring old plain list
>  5.481 1.244    build a "raum" using raums
>  8.186 1.380    build a raum then convert it to a list
> 12.581 4.449    build a "dlist" using dlists
> 16.209 5.096    build a dlist then convert it to a list
>
> Times were measured on an Intel Core 2 Duo Mac running
> Mac OS X 10.6.4, SSML/NJ v110.70 [built: Wed Jun 17 16:24:00 2009]
> MLton MLTONVERSION (built Mon Jun 15 11:10:01 CDT 2009 on fenrir.uchicago.edu)
>
> Building a list using dlists is 16 (SML/NJ) or 20 (MLton) times
> slower than using a plain list.
>
> Caveat:  because raums handle reverse in O(1) time as well as
> concatenation, for a fair comparison I made dlists do the same,

Och, adding reverse or even head and tail to a Dlist / Hughes list
seems out of spirit with the idea - build as a Hughes list (enjoying
cheap concat) - convert to a list and manipulate thereafter. I know
the version on Hackage has head, tail, fmap etc. their existence is
one of the reasons I avoid it and roll my own.

Interestingly what was the test doing for boring old plain list to do
so well? More than just cons I hope.

Best wishes

Stephen