[Haskell-cafe] Is fusion overrated?
roma at ro-che.info
Wed May 18 07:55:21 CEST 2011
If one thinks about Haskell data structures as of ordinary data
structures, fusion seems a great deal -- instead of producing
intermediate lists and possibly running out of memory, we just run a
loop and use constant amount of space.
But Haskell data structures are quite different -- they are produced as
demanded. Consider the example from the Stream Fusion paper:
f :: Int → Int
f n = sum [ k ∗ m | k ← [1..n], m ← [1..k ] ]
Assuming the sum is a strict left fold, it consumes elements of lists
one-by-one and runs in constant space.
The list part can be transformed to
foldr (++)  $ map (\k -> map (\m -> k*m) [1..k]) [1..n]
which is capable of producing elements one-by-one. So the whole thing
probably should run in constant space as well.
Of course I don't claim that fusion is useless -- just trying to
understand the problem it solves. Are we saving a few closures and cons
 Stream Fusion. From Lists to Streams to Nothing at All.
Duncan Coutts, Roman Leshchinskiy, Don Stewart.
Roman I. Cheplyaka :: http://ro-che.info/
Don't worry what people think, they don't do it very often.
More information about the Haskell-Cafe