Mapping over lists

The map function is a specialization of fold since we can write map in terms of fold: 

  map f = foldr ((:).f) []

Just as with fold, we can map over lists with regular or monadic functions:

doF n = do print n; return (n * 2)
main = do
    print $ map (* 2) [2, 3, 5, 7]
    mapM  doF [2, 3, 5, 7] >>= print
    mapM_ doF [2, 3, 5, 7]

The type signatures are very informative:

   map   :: (a -> b)   -> [a] -> [b]
   mapM  :: (a -> m b) -> [a] -> m [b]
   mapM_ :: (a -> m b) -> [a] -> m ()

In Chapter 3, Patterns of Composition, we wrote mapM in terms of sequence and sequenceA (the Monad and Applicative forms respectively). When we use sequenceA, we get a function that maps over Applicative:

  mapA :: Applicative f => (a -> f t) -> [a] -> f [t]
  mapA f = sequenceA' . (map f)
  
  sequenceA' :: Applicative f => [f t] -> f [t]
  sequenceA' [] = pure []
  sequenceA' (x:xs) = (:) <$> x <*> (sequenceA' xs)

  -- import Control.Applicative
  main = mapA doF [2, 3, 5, 7] >>= print

This evaluates as:

  sequenceA' . (map doF) [2, 3, 5, 7]
  (:) <$> (doF 2) <*> sequenceA' . (map doF) [3, 5, 7]
  (4:)  (:) <$> (doF 3) <*> sequenceA' . (map doF) [5, 7]
  ...
  (4:6:10:14:[])

Even though evaluation is lazy, each list element is being visited twice:

  • The mapA instance traverses the list and applies f to each traversed list element
  • sequenceA performs the resulting actions and re-assembles the results as a list

However, if we define mapA in the following way, we will have a single traversal:

  mapA' f [] = pure []
  mapA' f (x:xs) = (:) <$> f x <*> (mapA' f xs)

  main = mapA' doF [2, 3, 5, 7] >>= print

Given mapA, we can define sequenceA in terms of it:

  sequenceA = mapA id

This means that mapA and sequenceA can be defined interdependently:

  mapA f = sequenceA . (map f)
  sequenceA = mapA id

Applicative the map and sequence method are at the heart of the Traversable type-class.

Traversable

As with the Prelude.foldM, mapM fails us beyond lists, for example, we cannot mapM over our Tree from earlier:

  main = mapM doF aTree >>= print
  -- INVALID

The Traversable type-class relates to map in the same manner as Foldable relates to fold:

-- required: traverse or sequenceA
class (Functor t, Foldable t) => Traversable (t :: * -> *) where
  -- APPLICATIVE form
  traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)
  sequenceA :: Applicative f => t (f a) -> f (t a)
  
  -- MONADIC form (redundant)
  mapM      :: Monad m    => (a -> m b) -> t a -> m (t b)
  sequence  :: Monad m    => t (m a) -> m (t a)

The traverse function generalizes our mapA function, which was written for lists, to all Traversable containers. Similarly, Traversable.mapM is a more general version of Prelude.mapM for lists:

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

The Traversable type-class was introduced along with Applicative:

 

"We introduce the type class Traversable, capturing functorial data structures through which we can thread an Applicative computation"

 
 --McBride and Paterson, Applicative Programming with Effects

A Traversable Tree

Let's make our Tree an instance of Traversable; we'll start with the difficult way:

instance Functor Tree where
   fmap f (Leaf x) = Leaf (f x)
   fmap f (Node x lTree rTree)
      = (Node (f x)
              (fmap f lTree)
              (fmap f rTree))

instance Foldable Tree where 
  foldMap f (Leaf x) = f x
  foldMap f (Node x lTree rTree)
    = (foldMap f lTree) 
      'mappend' (f x)
      'mappend' (foldMap f rTree)

-- traverse :: Applicative ma => (a ­> ma b) ­> mt a ­> ma (mt b)
instance Traversable Tree where
   traverse g (Leaf x) = Leaf <$> (g x)
   traverse g (Node x ltree rtree)
      = Node <$> (g x)
             <*> (traverse g ltree) <*> (traverse g rtree)

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

aTree = Node' 2 (Leaf' 3)
                (Node' 5 (Leaf' 7)
                (Leaf' 11))

-- import Data.Traversable
main = traverse doF aTree
  where doF n = do print n; return (n * 2)

An easier way to do this would be to auto­implement Functor, Foldable and Traversable! (We will see how this magic is done in Chapter 6, Patterns of Generic Programming):

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveTraversable #-}
import Data.Traversable

data Tree a = Node a (Tree a) (Tree a)| Leaf a
  deriving (Show, Functor, Foldable, Traversable)

aTree = Node' 2 (Leaf' 3)
                (Node' 5 (Leaf' 7)
                (Leaf' 11))

main = traverse doF aTree
  where doF n = do print n; return (n * 2)

The traversal and the Iterator pattern

The "Gang of Four" Iterator pattern is concerned with providing a way

 

"To access the elements of an aggregate object sequentially without exposing its underlying representation"

 
 --Gamma et al, "Gang of Four" Design Patterns, 1995

In The Essence of the Iterator Pattern, Jeremy Gibbons shows precisely how the Applicative traversal captures the Iterator pattern.

The Traversable.traverse function is the Applicative version of Traversable.mapM, which means that it is more general than mapM (because Applicative is more general than Monad).

Moreover, because mapM does not rely on the Monad bind chain to communicate between iteration steps, Monad is a superfluous type for mapping with effects (Applicative is sufficient). In other words, traverse in Applicative is superior to the Monadic traversal (mapM).

 

"In addition to being parametrically polymorphic in the collection elements, the generic traverse operation is parameterized along two further dimensions: the datatype being traversed, and the Applicative functor in which the traversal is interpreted"

"the improved compositionality of Applicative functors over monads provides better glue for fusion of traversals, and hence better support for modular programming of iterations"

 
 --Jeremy Gibbons, The Essence of the Iterator Pattern
..................Content has been hidden....................

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