[Haskell-cafe] "no-coding" functional data structures via lazyness

[Isaac Dupree]

Dave Bayer wrote:
> The code is very fast for its size; I haven't seen Haskell code posted 
> on the web that comes close, and it is faster than any of my other tries 
> (I posted this code to 
> http://www.haskell.org/haskellwiki/Prime_numbers). Effectively, it 
> steals a heap data structure out of thin air by exploiting the 
> implementation of lazy evaluation. It would seem that GHC's core data 
> structures are coded closer to the machine that anything I can write 
> _in_ Haskell. So much for studying how to explicitly write a good heap!

Indeed, it was irritating that I could not make an explicit 
efficiently-catenable-list data that was nearly as fast as the dlist 
technique ([a] -> [a]), or even the similarly-performing (forall b. (a 
-> b -> b) -> b -> b) that does not really take advantage of the heavily 
optimized [] type.  Although, I did not try too hard since the implicit 
version works just fine.

Isaac