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, Haskell Streams .

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, Haskell Streams 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: