
Just a quick announce: the stream fusion library for lists, that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year is now available on Hackage as a standalone package: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.1... As described in the recent paper: "Stream Fusion: From Lists to Streams to Nothing at All" Duncan Coutts, Roman Leshchinskiy and Don Stewart. ICFP 2007 This is a drop-in replacement for Data.List. Haddocks here, http://code.haskell.org/~dons/doc/stream-fusion/ (but note the interface is exactly the same as the Data.List library) You might expect some small percent performance improvement for list heavy programs, using ghc 6.8 and this list library with -O2 (use -ddump-simpl-stats and look for: STREAM stream/unstream fusion messages, indicating your intermediate lists are getting removed. To get an idea of what is happening, consider this list program: foo :: Int -> Int foo n = sum (replicate n 1) Compiled with ghc-6.8.1 -O2 -ddump-simpl Normally, as sum is a left fold, an intermediate lazy list is allocated between the call to sum and replicate, as GHC currently does: foo :: Int# -> Int# foo n = Data.List.sum (case <=# n 0 of False -> go n True -> []) where go :: Int# -> [Int] -- intermediate list! go n = case <=# n 1 of False -> 1 : (go (n -# 1)) True -> [1] By using Data.List.Stream instead, you get a strict fused loop instead, with no intermediate structure allocated: loop_sum :: Int# -> Int# -> Int# loop_sum k n = case <=# n 0 of False -> loop_sum (k +# 1) (n -# 1) True -> k foo :: Int# -> Int# foo n = loop_sum 0 n This is a the halfway mark before porting other sequence types -- especially Data.ByteString -- over to the full stream fusion model (in particular, strict bytestrings will benefit a lot, due to the O(n) cost of intermediate bytestrings being removed). The stream fusion types and combinators are also available in stripped down form in the mlton sml compiler's extended prelude. Enjoy. -- Don