In this chapter we will meet some more typeclasses that abstract common coding patterns for dealing with data.

Learning Outcomes

  • Understand that the “reduce” function we met for arrays and other data structures in JavaScript is referred to as “folding” in Haskell and there are two variants foldl and foldr for left and right folds respectively.
  • Understand that the Monoid typeclass for things that have a predefined rule for aggregation (concatenation), making containers of Monoid values trivial to fold
  • Understand that Foldable generalises containers that may be folded (or reduced) into values
  • Understand that Traversable generalises containers over which we can traverse applying a function with an Applicative effect

Folds

Recall the “reduce” function that is a member of JavaScript’s Array type, and which we implemented ourselves for linked and cons lists, was a way to generalise loops over enumerable types. In Haskell, this concept is once again generalised with a typeclass called Foldable – the class of things which can be “folded” over to produce a single value.
We will come back to the Foldable typeclass, but first let’s limit our conversation to the familiar Foldable instance, basic lists.
Although in JavaScript reduce always associates elements from left to right, Haskell’s Foldable typeclass offers both foldl (which folds left-to-right) and foldr (which folds right-to-left):

Prelude> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

Prelude> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

In the following the examples the Foldable t instance is a list. Here’s how we right-fold over a list to sum its elements:

Left Fold

While the lambda above makes it explicit which parameter is the accumulator and which is the list element, this is a classic example where point-free coding style makes this expression very succinct:

Prelude> foldr (+) 0 [5,8,3,1,7,6,2]

32

Here’s a left fold with a picture of the fold:

Left Fold

Note that since the (+) operator is associative – a+(b+c) = (a+b)+c – foldr and foldl return the same result. For functions that are not associative, however, this is not necessarily the case.


Exercises

  • Predict what the results of a left- and right-fold will be for (-) folded over [1,2,3,4] with initial value 0.
  • What is the result of foldr (:) [] applied to any list?
  • Implement map using foldr.

Monoid

In the example fold above, we provide the (+) function to tell foldl how to aggregate elements of the list. There is also a typeclass for things that are “automatically aggregatable” or “concatenatable” called Monoid which declares a general function for mappend combining two Monoids into one, a mempty value such that any Monoid mappended with mempty is itself, and a concatenation function for lists of Monoid called mconcat.

Prelude> :i Monoid
class Semigroup a => Monoid a where
  mempty :: a
  mappend :: a -> a -> a
  mconcat :: [a] -> a
  {-# MINIMAL mempty #-}
...

In the Data.Monoid library there are some interesting instances of Monoid. For example Sum is an instance of Monoid which wraps a Num, such that lists of Sum can be mconcated:

Prelude> import Data.Monoid
Data.Monoid> mconcat $ Sum <$> [5,8,3,1,7,6,2]

Sum {getSum = 32}

So a sum is a data type with an accessor function getSum that we can use to get back the value:

Prelude Data.Monoid> getSum $ mconcat $ Sum <$> [5,8,3,1,7,6,2]

32

We make a data type aggregatable by instancing Monoid and providing definitions for the functions mappend and mempty. For Sum these will be (+) and 0 respectively. Lists are also themselves Monoidal, with mappend defined as an alias for list concatenation (++), and mempty as []. Thus, we can:

Prelude Data.Monoid> mconcat [[1,2],[3,4],[5,6]]
[1,2,3,4,5,6]

Which has a simple alias concat defined in the Prelude:

Prelude> concat [[1,2],[3,4],[5,6]]
[1,2,3,4,5,6]

There is also an operator for mappend called (<>), such the following are equivalent:

Data.Monoid> mappend (Sum 1) (Sum 2)
Sum {getSum = 3}

Data.Monoid> (Sum 1) <> (Sum 2)
Sum {getSum = 3}

And for lists (and String) we have:

> mappend [1,2] [3,4]
[1,2,3,4]

> [1,2] <> [3,4]
[1,2,3,4]

> [1,2] ++ [3,4]
[1,2,3,4]

Foldable

So now we’ve already been introduced to foldl and foldr for lists, and we’ve also seen the Monoid typeclass, let’s take a look at the general class of things that are Foldable. As always, your best friend for exploring a new typeclass in Haskell is GHCi’s :i command:

Prelude> :i Foldable
class Foldable (t :: * -> *) where
  foldr :: (a -> b -> b) -> b -> t a -> b -- as described previously, but notice foldr and foldl
  foldl :: (b -> a -> b) -> b -> t a -> b -- are for any Foldable t, not only lists
  length :: t a -> Int -- number of items stored in the Foldable
  null :: t a -> Bool -- True if empty
  elem :: Eq a => a -> t a -> Bool -- True if the a is an element of the t of a
  maximum :: Ord a => t a -> a -- biggest element in the Foldable
  minimum :: Ord a => t a -> a -- smallest element
  sum :: Num a => t a -> a -- compute the sum of a Foldable of Num
  product :: Num a => t a -> a -- compute the product of a Foldable of Num
  Data.Foldable.fold :: Monoid m => t m -> m -- if the elements of t are Monoids then we don't need an operator to aggregate them
  foldMap :: Monoid m => (a -> m) -> t a -> m -- uses the specified function to convert elements to Monoid and then folds them
  Data.Foldable.toList :: t a -> [a] -- convert any Foldable things to a list
  {-# MINIMAL foldMap | foldr #-}
        -- Defined in `Data.Foldable'
instance Foldable [] -- Defined in `Data.Foldable'
instance Foldable Maybe -- Defined in `Data.Foldable'
instance Foldable (Either a) -- Defined in `Data.Foldable'
instance Foldable ((,) a) -- Defined in `Data.Foldable'

Note that I’ve reordered the list of functions to the order we want to discuss them, removed a few things we’re not interested in at the moment and the comments are mine. However, once you get used to reading types the :info for this class is pretty self explanatory. Most of these functions are also familiar from their use with lists. The surprise (OK, not really) is that lots of other things can be Foldable as well.

Prelude> foldr (-) 1 (Just 3)
2
Prelude> foldl (-) 1 (Just 3)
-2
Prelude> foldr (+) 1 (Nothing)
1
Prelude> length (Just 3)
1
Prelude> length Nothing
0
-- etc

If we import the Data.Foldable namespace we also get fold and foldMap, which we can use with Monoid types which know how to aggregate themselves (with mappend):

Prelude> import Data.Foldable

Prelude Data.Foldable> fold [[1,2],[3,4]] -- since lists are also Monoids
[1,2,3,4]

The fun really starts though now that we can make new Foldable things:

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

tree = Node (Node (Leaf 1) 2 (Leaf 3)) 4 (Node (Leaf 5) 6 (Leaf 7))

Which produces a tree with this structure:

Tree

We make this type of binary tree an instance of foldable by implementing either of the minimum defining functions, foldMap or foldr:

instance Foldable Tree where
   foldMap :: Monoid m => (a -> m) -> Tree a -> m
   foldMap _ Empty = mempty
   foldMap f (Leaf x) = f x
   foldMap f (Node l x r) = foldMap f l <> f x <> foldMap f r

> length tree
7
> foldr (:) [] tree
[1,2,3,4,5,6,7]

We can use foldMap to map the values stored in the tree to an instance of Monoid and then concatenate these Monoids. For example, we could map and concatenate them as a Sum:

> getSum $ foldMap Sum tree
28

Or we can compute the same conversion to a list as the above foldr, by providing foldMap with a function that places the values into singleton lists, e.g.:

> (:[]) 1 -- cons 1 with an empty list, same as 1:[]
[1]

Since list is an instance of Monoid, foldMap will concatenate these singleton lists together:

> foldMap (:[]) tree
[1,2,3,4,5,6,7]

Exercises

  • Make an instance of Foldable for Tree in terms of foldr instead of foldMap.

Traversable

Traversable extends both Foldable and Functor, in a typeclass for things that we can traverse a function with an Applicative effect over. Here’s a sneak peak of what this lets us do:

Prelude> traverse putStrLn ["tim","was","here"]
tim
was
here
[(),(),()]

The first three lines are the strings printed to the terminal (the side effect). The result reported by GHCi is a list [(),(),()] as discussed below.

Here, as usual, is what GHCi :i tells us about the Traversable type class:

Prelude> :i Traversable
class (Functor t, Foldable t) => Traversable (t :: * -> *) where
  traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
  sequenceA :: Applicative f => t (f a) -> f (t a)
  ... -- some other functions
  {-# MINIMAL traverse | sequenceA #-}
        -- Defined in `Data.Traversable'
instance Traversable [] -- Defined in `Data.Traversable'
instance Traversable Maybe -- Defined in `Data.Traversable'
instance Traversable (Either a) -- Defined in `Data.Traversable'
instance Traversable ((,) a) -- Defined in `Data.Traversable'

The following map shows how all of these typeclasses are starting to come together to offer some real power:

Traversable Typeclasses

So what does the traverse function do? By way of example, remember our safe modulo function this we used to experiment with Functor:

safeMod :: Integral a => a-> a-> Maybe a
safeMod _ 0 = Nothing
safeMod numerator divisor = Just $ mod numerator divisor 

It lets us map over a list of numbers without throwing divide-by-zero exceptions:

> map (safeMod 3) [1,2,0,2]
[Just 0,Just 1,Nothing,Just 1]

But what if 0s in the list really are indicative of disaster so that we should bail rather than proceeding? The traverse function of the Traversable type-class gives us this kind of “all or nothing” capability:

> traverse (safeMod 3) [1,2,0,2]
Nothing
> traverse (safeMod 3) [1,2,2]
Just [0,1,1]

So mapping a function with an Applicative effect over the values in a list gives us back a list with each of those values wrapped in the effect. However, traverseing such a function over a list gives us back the list of unwrapped values, with the whole list wrapped in the effect.

Traverse applies a function with a result in an Applicative context (i.e. an Applicative effect) to the contents of a Traversable thing.

Prelude> :t traverse
traverse
  :: (Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b) 

What are some other functions with Applicative effects? Lots! E.g.:

  • Any constructor of a data type that instances Applicative: e.g. Just :: a -> Maybe a
  • Anything that creates a list: (take 5 $ repeat 1) :: Num a => [a]
  • IO is Applicative, so a function like print :: Show a => a -> IO ()
  • etc…

The print function converts values to strings (using show if available from an instance of Show) and sends them to standard-out. The print function wraps this effect (there is an effect on the state of the console) in an IO computational context:

Prelude> :t print
print :: Show a => a -> IO ()

The () is like void in TypeScript – it’s a type with exactly one value (), and hence is called “Unit”. There is no return value from print, only the IO effect, and hence the return type is (). IO is also an instance of Applicative. This means we can use traverse to print out the contents of a list:

Prelude> traverse print [1,2,3]
1
2
3
[(),(),()]

Here 1,2,3 are printed to the console each on their own line (which is print’s IO effect), and [(),(),()] is the return value reported by GHCi – a list of Unit.

Prelude> :t traverse print [1,2,3]
traverse print [1,2,3] :: IO [()]

When we ran this at the REPL, GHCi consumed the IO effect (because it runs all commands inside the IO Monad). However, inside a pure function there is no easy way to get rid of this IO return type – which protects you from creating IO effects unintentionally.

A related function defined in Traversable is sequenceA which allows us to convert directly from Traversables of Applicatives, to Applicatives of Traversables:

> :t sequenceA
sequenceA :: (Applicative f, Traversable t) => t (f a) -> f (t a)
Prelude> sequenceA [Just 0,Just 1,Just 1]
Just [0,1,1]
Prelude> sequenceA [Just 0,Just 1,Nothing,Just 1]
Nothing

The default sequenceA is defined very simply in terms of traverse (recall id is just \x->x):

sequenceA = traverse id

A bit more fun with sequenceA, a list of functions:

> :t [(+3),(*2),(+6)]
[(+3),(*2),(+6)] :: Num a => [a -> a]

is also a list of Applicative, because function (->)r is an instance of Applicative. Therefore, we can apply sequenceA to a list of functions to make a single function that applies every function in the list to a given value and return a list of the results:

> :t sequenceA [(+3),(*2),(+6)]
sequenceA [(+3),(*2),(+6)] :: Num a => a -> [a]
> sequenceA [(+3),(*2),(+6)] 2
[5,4,8]

To create our own instance of Traversable we need to implement fmap to make it a Functor and then either foldMap or foldr to make it Foldable and finally, either traverse or sequenceA. So for our Tree type above, which we already made Foldable we add:

instance Functor Tree where
   fmap :: (a -> b) -> Tree a -> Tree b
   fmap _ Empty = Empty
   fmap f (Leaf x) = Leaf $ f x
   fmap f (Node l v r) = Node (fmap f l) (f v) (fmap f r)

instance Traversable Tree where
   traverse :: Applicative f => (a -> f b) -> Tree a -> f (Tree b)
   traverse _ Empty = pure Empty
   traverse f (Leaf a) = Leaf <$> f a
   traverse f (Node l x r) = Node <$> traverse f l <*> f x <*> traverse f r

So now we can traverse a function with an Applicative effect over the tree:

Prelude> traverse print tree
1
2
3
4
5
6
7

And of course, we can sequence a Tree of Maybes into a Maybe Tree:

> treeOfMaybes = Just <$> tree -- a tree of Maybes
> treeOfMaybes
Node (Node (Leaf (Just 1)) (Just 2) (Leaf (Just 3))) (Just 4) (Node (Leaf (Just 5)) (Just 6) (Leaf (Just 7)))
> sequenceA treeOfMaybes
Just (Node (Node (Leaf 1) 2 (Leaf 3)) 4 (Node (Leaf 5) 6 (Leaf 7)))

Applying Functions Over Contexts

Thus far we have seen a variety of functions for applying functions in and over different contexts. It is useful to note the similarities between these, and recognise that they are all doing conceptually the same thing, i.e. function application. The difference is the in the type of context. The simplest function for applying functions is the ($) operator, with just a function (no context), applied directly to a value. Then fmap, just a function, mapped over a Functor context/container. Then Applicative (function also in the context). Then, most recently traverse: the function produces a result in an Applicative context, applied (traversed) over some data structure, and the resulting data structure returned in an Applicative context. Below, I line up all the types so that the similarities and differences are as clear as possible. It’s worth making sure at this stage that you can read such type signatures, as they really do summarise everything that we have discussed.

($)      ::                                      (a -> b) -> a   -> b
(<$>)    :: Functor f                      =>    (a -> b) -> f a -> f b
(<*>)    :: Applicative f                  =>  f (a -> b) -> f a -> f b
traverse :: (Traversable t, Applicative f) =>  (a -> f b) -> t a -> f (t b)

Parsing a String Using Traversable?

What if we want to parse an exact match for a given string, for example, a token in a programming language like the word function. Or, to look for a polite greeting at the start of an email before deciding whether to respond, such as “hello”.

> parse (string "hello") "hello world"
Just (" world", "hello")

> parse (string "hello") "world, hello"
Nothing

So the string “hello” is the prototype for the expected input. How would we do this?

Our parser would have to process characters from the input stream and check if each successive character is the one expected from the prototype. If it is the correct character, we would cons it to our result and than parse the next character.

This can be written using a foldr to parse all the characters while checking with the is parser.

string l = foldr (\c acc -> liftA2 (:) (is c) acc) (pure "") l

Remembering liftA2 is equivalent to f <$> a <*> b.

Our <*> will allow for the seqeuencing of the applicative effect, so this will sequentially parse all characters, making sure they are correct. As soon, as one applicative parser fails, the result of the parsing will fail.

This could also be written as:

string l = foldr cons (pure []) l
  where
    cons c acc = liftA2 (:) (is c) acc

But the title of this section was traverse?

Well, lets consider how we would define a list as an instance of the traversable operator. The traverse function is defined exactly as follows:

instance Traversable [] where
    traverse :: Applicative f => (a -> f b) -> [a] -> f [b]
    traverse f = foldr cons (pure [])
      where cons x ys = liftA2 (:) (f x) ys

This is almost exactly the definition of our string parser using foldr but the function f is exactly the is Parser.

Therefore, we can write string = traverse is

Let’s break down how the string parser using traverse and is works in terms of types:

string :: String -> Parser String
string = traverse is

traverse is a higher-order function with the following type:

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)

t is a traversable data structure, which in our case is a String (since String is a list of characters). a is the element type of the traversable structure, which is Char (the individual characters in the String). f is an applicative functor, which is the Parser type in our case. The function (a -> f b) is the parser for a single character. In our case, it’s the is parser.

So, we will apply the is function to each element in the the traversable t (the list) and store collect the result in to a Parser [Char].

Therefore, traverse is is of type Parser String, which is a parser that attempts to parse the entire String and returns it as a result.

Can we also write this using sequenceA?

string :: String -> Parser String
string str = sequenceA (map is str)

Or in point-free form

string :: String -> Parser String
string = sequenceA . map is

map is str maps the is parser over each character in the input string str. This produces a list of parsers, where each parser checks if the corresponding character in the input matches the character in the target string.

sequenceA is then used to turn the list of parsers into a single parser. This function applies each parser to the input string and collects the results. If all character parsers succeed, it returns a list of characters; otherwise, it returns Nothing.

In fact an equivalent definition of traverse can be written using the sequenceA as follows:

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse f l = sequenceA (f <$> l)

Exercises

  • What would be the definition of sequenceA over a list? (without using traverse)
  • Can you make the Maybe data type an instance of traversable?

Bringing it all together!

We can also parse a tree by traversing a parser over it, the same way we parsed string by traversing a list of Char!

Recall from earlier in this section:

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

instance Traversable Tree where
  --  traverse :: Applicative f => (a -> f b) -> Tree a -> f (Tree b)
   traverse _ Empty = pure Empty
   traverse f (Leaf a) = Leaf <$> f a
   traverse f (Node l x r) = Node <$> traverse f l <*> f x <*> traverse f r

We can write a similar definition for parsing an exact tree compared to parsing a string!

We will consider a Value which is either an integer, or an operator which can combine integers. We will assume the only possible combination operator is + to avoid complexities with ordering expressions.


data Value = Value Int | BinaryPlus 
  deriving (Show)

We can generalize the is parser to satisfy, which will run a given parser p, and make sure the result satisfies a boolean condition.

satisfy :: Parser a -> (a -> Bool) -> Parser a
satisfy p f = Parser $ \i -> case parse p i of 
  Just (r, v) 
      | f v -> Just (r, v)
  _ -> Nothing

From this satisfy, we will use traverse to ensure our string exactly matches a wanted expression Tree.


isValue :: Value -> Parser Value
isValue (Value v) = Value <$> satisfy int (==v)
isValue BinaryPlus = BinaryPlus <$ satisfy char (=='+')

stringTree :: Tree Value -> Parser (Tree Value)
stringTree = traverse isValue

sampleTree :: Tree Value
sampleTree =
  Node
    (Leaf $ Value 3)
    BinaryPlus
    (Node
      (Leaf (Value 5))
      BinaryPlus
      (Leaf (Value 2)))


inputString :: String
inputString = "3+5+2"

parsedResult :: String -> Maybe (String, Tree Value)
parsedResult = parse (stringTree sampleTree) 

The parsedResult will only succeed if the input string exactly matches the desired tree.

To evaluate the parsed expression we can use foldMap and the Sum monoid:

evalTree :: Tree Value -> Int
evalTree tree = getSum $ foldMap toSum tree
  where
    toSum :: Value -> Sum Int
    toSum (Value v) = Sum v
    toSum BinaryPlus = Sum 0 -- For BinaryPlus, we don't need to add anything to the sum

evalResult :: Maybe (String, Int)
evalResult = (evalTree <$>) <$> parsedResult
-- >>> evalResult = Just ("", 10)