Folding over lists

Recall the following from Chapter 1, Functional Patterns – the Building Blocks:

  sumLazy [] = 0
  sumLazy (x:xs) = x + sumLazy xs

Lazy recursion is captured by foldr:

  sumLazy' = foldr (+) 0

On the other hand, foldl captures tail recursion, for example consider a strict recursive sum:

  sumStrict acc [] = acc
  sumStrict acc (x:xs) = sumStrict (acc + x) xs

This is captured by the iterative process foldl:

sumStrict' = foldl (+)

The foldl function is tail recursive and strict in the accumulator. The foldr function is non-tail recursive and lazy. In fact, foldl is a special case of foldr (https://wiki.haskell.org/Foldl_as_foldr).

Folding with monadic functions

Let's write a tail-recursive sum that does some IO at each accumulation step:

  doSumStrict :: (Show a, Num a) => a -> [a] -> IO a

  doSumStrict acc [] = return acc
  doSumStrict acc (x:xs) = do 
    putStrLn $ " + " ++ (show x) ++ " = " ++ (show acc') 
    doSumStrict acc' xs
    where acc' = acc + x

  main = doSumStrict...