Chapter 4. Patterns of Folding and Traversing

In this chapter, we'll focus on two fundamental patterns of recursion—folding and mapping. The more primitive forms of these patterns are to be found in the Prelude, the "old part" of Haskell.

With the introduction of the Applicative type­class came more powerful mapping (traversal), which opened the door to typelevel folding and mapping in Haskell. First, we look at how the Prelude's list fold is generalized to all Foldable containers. Then, we follow the generalization of the list map to all Traversable containers.

Our exploration of fold and map culminates with the Lens library, which raises Foldable and Traversable to an even higher level of abstraction.

In this chapter, we will cover the following:

  • Folding with monoids
  • Foldable
  • Mapping over lists
  • Traversable
  • Modernizing Haskell
  • Lenses

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 0 [2, 3, 5, 7]

To write this as a left-fold, we use the foldM function:

doSumStrict' = foldM doPlus
  where
    doPlus acc x = do
      putStrLn $ " + " ++ (show x)
                       ++ " = " ++ (show acc')
      return acc'
      where acc' = acc + x

main = doSumStrict' 0 [2, 3, 5, 7]

The foldl, foldr and foldM functions all describe folding over lists:

  foldM :: Monad m => (b -> a -> m b) -> b -> [a] -> m b
  foldl ::            (b -> a -> b)   -> b -> [a] -> b

For foldM, the fold function is monadic and the result accumulates inside the Monad class.

Folding with Monoid

Folding allows us to express all manner of accumulations:

sum' = foldr (+) 0
product' = foldr (*) 1
concatS' = foldr (++) ""
concatL' = foldr (++) []

any' = foldr (||) False
all' = foldr (&&) True

main = do
  print $ sum'     [2, 3, 5, 7]
  print $ product' [2, 3, 5, 7]
  print $ concatS' ["2", "3", "5", "7"]
  print $ concatL' [["2"], ["3"], ["5"], ["7"]]
  print $ any'     [False, False, True, False]
  print $ all'     [True, True, True, True]

These functions differ only in the accumulation function and initial value. In each case, the initial value is also the identity for the corresponding operator:

0      +    x = x
1      *    x = x
""     ++   x = x
[]     ++   x = x
False  ||   x = x
True   &&   x = x

The Monoid type­class describes exactly this, an associative operator with an identity value:

class Monoid a where
    mempty  :: a
    mappend :: a -> a -> a
    mconcat :: [a] -> a
    mconcat = foldr mappend mempty

The mconcat function is a generic version of our accumulation functions.

Numbers are monoidal under addition and multiplication:

  newtype Sum' a = Sum' {getSum' :: a} deriving (Show)
  instance Num a => Monoid (Sum' a) where
      mempty = Sum' 0
      Sum' x 'mappend' Sum' y = Sum' (x + y)

  newtype Product' a = Product' {getProduct' :: a} 
  instance Num a => Monoid (Product' a) where
      mempty = Product' 1
      Product' x 'mappend' Product' y = Product' (x * y)

These are already defined in Data.Monoid as Sum and Product.

This allows us to express + and * as a monoidal accumulation:

-- 10 + 7
(Sum 10) `mappend` (Sum 7)
-- Sum {getSum = 17}

-- 10 * 7
(Product 10) `mappend` (Product 7)
-- Product {getProduct = 70}

Similarly, Bool is a Monoid under the (||) and (&&) operators (corresponding to Any, All). The List instance is a Monoid under (++) and [], and String is a list. This means that we can rewrite our earlier folds in monoidal form:

-- import Data.Monoid
main = do
  print $ mconcat [Sum 2, Sum 3, Sum 5]
  print $ mconcat [Product 2, Product 3, Product 5]
  print $ mconcat ["2", "3", "5"]
  print $ mconcat [["2"], ["3"], ["5"]]
  print $ mconcat [Any False, Any False, Any True]
  print $ mconcat [All True, All True, All True]

Folding accumulates and monoids are the datatype for accumulation. This is why the generalization of fold, described by the Foldable library, rests on Monoid.

Foldable

We can fold over lists with regular (foldl/r) and monadic functions (foldM), but this doesn't help us with folding over any other data structures, for example:

data Tree a = Node a (Tree a) (Tree a)
            | Leaf a
 deriving Show

If we constrain the inner type of Tree to be a Monoid, we can fold over Tree:

foldT :: Monoid a => Tree a ­> a
foldT (Leaf x) = x
foldT (Node x lTree rTree)
   = (foldT lTree) `mappend` x `mappend` (foldT rTree)
   -- using the underlying type's `mappend`.
main = do
   print . foldT $ Node (Sum 2) (Leaf (Sum 3))
                                (Leaf (Sum 5))
   -- Sum {getSum = 1 0}
   print . foldT $ Node (Product 2) (Leaf (Product 3))
                                    (Leaf (Product 5))
   -- Product {getProduct = 30}

It's a pain to inject Sum and Product into the Tree structure. We can simplify things by passing in a function that will raise the elements being folded over Monoid:

  foldT' :: Monoid a => (t -> a) -> Tree t -> a
  foldT' toMonoid (Leaf x) = toMonoid x
  foldT' toMonoid (Node x lTree rTree)
    = (foldT' toMonoid lTree) 
      'mappend' (toMonoid x)
      'mappend' (foldT' toMonoid rTree)

main = do
   print $ foldT' Sum aTree
   print $ foldT' Product aTree
   print $ foldT' (Any . (==5)) aTree
   print $ foldT' (All . (>0)) aTree
      where aTree = Node 2 (Leaf 3) (Leaf 5)

The Foldable type-class describes a more general interface for folding:

class Foldable (t :: * ­> *) where
   -- implement foldMap or foldr
   foldMap :: Monoid m => (a ­> m) ­> t a ­> m
   foldr ::               (a ­> b ­> b) ­> b ­> t a ­> b
   -- get these for free:
   -- fold, foldl, fold, foldr', foldl', foldr1 , foldl1

The foldMap function generalizes our foldT' instance:

  foldT'  :: Monoid m => (a -> m) -> Tree a -> m
  foldMap :: Monoid m => (a -> m) -> t a    -> m
  fold    :: Monoid m =>             t m    -> m

Also, fold assumes that the elements are already of type Monoid:

  fold = foldmap id

Let's make our Tree a Foldable instance:

import Data.Monoid
import qualified Data.Foldable as F
import qualified Control.Monad as M

instance F.Foldable Tree where 
  foldMap toMonoid (Leaf x) = toMonoid x
  foldMap toMonoid (Node x lTree rTree)
    = (F.foldMap toMonoid lTree) 
      'mappend' (toMonoid x)
      'mappend' (F.foldMap toMonoid rTree)

main = do 
print $ F.foldMap Sum             aTree
print $ F.foldMap Product         aTree
print $ F.foldMap (Any . (==5))   aTree
print $ F.foldMap (All . (>0))    aTree
   where aTree = Node 2 (Leaf 3) (Leaf 5)

Instead of just implementing fold for Tree, we turned Tree into a Foldable container. The Data.Foldable instance comes with many convenience functions that generalize the corresponding Prelude functions:

main = do
  print $ F.sum aTree
  print $ F.product aTree
  print $ F.any (==5) aTree
  print $ F.all (>0) aTree
  print $ F.maximum aTree
  where aTree = Node 2 (Leaf 3) (Leaf 5)

The following type signatures show the regular list sum function being generalized to all Foldable containers: 

sum    ::  Num a             => [a] ­> a
F.sum :: (Foldable t, Num a) => t a ­> a

In the same way, Foldable.foldM generalizes monadic folding from lists to all Foldable containers:

foldM  :: Monad m  => 
    (b -> a -> m b) -> b -> [a] -> m b

F.foldrM :: (Foldable t, Monad m) => 
    (a -> b -> m b) -> b -> t a -> m b

as in

doSum = F.foldrM doPlus
  where 
    doPlus acc x = do
      putStrLn $ (show x) ++ " = " ++ (show acc) 
      return (acc + x)

main = doSum 0 aTree

All Foldable types can be expressed as lists by folding the (:) function over the Foldable data structure, for example:

main = do
  print $ F.toList aTree
  -- same as
  print $ F.foldr (:) [] aTree

This example shows that not all folding accumulates destructively. Fold accumulates the input structure into a single Monoid value, but that single value might be a composite structure. In general, fold transforms a data structure (often radically).

However, both map and filter are special cases of fold, which makes fold the fundamental function of structured recursion.

Foldable generalizes folding from lists to arbitrary data structures.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset