How to use Stream fusion to optimize lists in Haskell?
Suppose we have a series of composed functions acting on a list
ls = unwords $ map show . map (+1) . filter (!== 0) $ [1..10000]
At each step of the way we need to build up intermediate lists:
1st list generated here
filter (!== 0) $ [1..10000]
2nd list generated here
map(+1) . filter (!== 0) $ [1..10000]
And so on.
As a result, we allocate 4 times when running the expression.
To optimize this,
We want to convert lists which are a recursive structure into a non-recursive costructure,.
The reason is that filter, map and other common functions list functions are all recursive in nature. This is a result of list being recursively defined, requiring us to recurse to traverse the list.
filter :: (a -> Bool) -> [a] -> [a] filter _  =  filter pred (x:xs) | pred x = x : filter pred xs | otherwise = filter pred xs
Hence these functions consume the entire list each time they are applied.
On the other hand,functions are not recursive (since streams are not recursively defined). Hence they not have to traverse the entire list:
filter :: (a -> Bool) -> Stream a -> Stream a filter pred (Stream next st) = Stream next' st where next' s = case next s of Done -> Done Skip s' -> Skip s' Yield x s' | p x -> Yield x s' | otherwise -> Skip s'
References / Further reading: