Friday, August 1, 2008

Difference Lists in Haskell!

Oooh! Scrumptious!

I've discovered while exploring one of my Tangents, the Comonad.Reader, that a member of the Galois team, Don Stewart, has developed a Difference List library ... in Haskell. My initial scan of the library is that it is simple, elegant and practical. Three feathers in his cap!

Excuse me while, initially, I replace in my code the 'cons then reverse' list-building pattern with Don's DList. I also can't wait to find other applications for this type.

While I'm away doing that, you can read sigfpe's blog, particularly his clever implementation of the Fibonacci series as a comonad.

3 comments:

Neil Mitchell said...

Do you realise DList's are likely to be slower? In my benchmarking they are between 30% and 60% slower.

sigfpe said...

Co*algebra* :-)

geophf said...

@neil, DList slower? That was not what I was lead to believe from the Comonad.Reader report that DList was significantly faster than 'cons then reverse' (which is very much faster than repeated appends). My experience from Prolog was that 'cons then reverse' was 2n time and difference lists were 1n time. I will heed your warning and run profiles to see which is quicker.

But where speed is not vital, DList wins hands down for clarity in my book, because the 'cons then reverse' always ends piling up, and then it becomes a chore to place the reverses in the right places.