Foldable

Foldable represents data structure type class that

  • provides a generalisation of list folding (foldr and friends).
  • provides operations derived from list foldings to arbitrary data structures

You can use a Foldable where you would have to traverse a dataset and reduce it to a single result.

  • Get the product of a list
  • Get the max path value in a tree

In short, fold can be understood as function to reduce a large structure into a single result.

Foldable Class

class Foldable t where
    foldMap 	:: Monoid m => (a -> m) -> t a -> m
    fold 	:: Monoid m => t m -> m

    -- following have default implementations:
    foldr 	:: (a -> b -> b) -> b -> t a -> b
    foldr' 	:: (a -> b -> b) -> b -> t a -> b
    foldl 	:: (b -> a -> b) -> b -> t a -> b
    foldl' 	:: (b -> a -> b) -> b -> t a -> b
    foldr1 	:: (a -> a -> a) -> t a -> a
    foldl1 	:: (a -> a -> a) -> t a -> a

    toList 	:: t a -> [a]
    null 	:: t a -> Bool
    length 	:: t a -> Int
    elem 	:: Eq a => a -> t a -> Bool
    maximum 	:: Ord a => t a -> a
    minimum 	:: Ord a => t a -> a
    sum 	:: Num a => t a -> a
    product 	:: Num a => t a -> a

Foldable is a great example of how monoids can help formulating good abstractions as we can see fold and foldMap require the elements of the Foldable to be Monoids.

Monoids simply define a zero element via mempty and an associative operation mappend for combining two Monoids into one. mconcat makes use of mappend and mempty in it’s default implementation.

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

---
mconcat :: [a] -> a
mconcat = foldr mappend mempty

Let’s look at some examples :

> length [1..10]
6

-- sum all elements of the list

-- just using map, without Foldable.
> summ xs = let ys = 0 : map (\(a,b)->a+b) (zip xs ys) in last ys
> summ [1..10]
55

-- using foldr
> foldr (+) 0 [1..10]
55

-- using sum
> sum [1..10]
55

-- check if element exists
> elem 4 [1..10]
True

Instead of thinking of sum as a function which is fmapped across a list and accumulating its elements with (+), Foldable and foldMap help us think of it as function which queries each element for its value and summarises the results using Sum monoid.

Monoidal summary perspective is important while using folds as it separates the details of data structure from the expected results.

fold and foldMap

Foldable has no laws of its own and they are mostly general-purpose, however, fold and foldMap use monoid homomorphism.

In the example above tList was a list of integers [Int] , where the [] is a Foldable. Int is not a Monoid. So as long as we do not use any function from Foldable that requires Monoid, it will work fine. But if you try to use fold or foldMap on tList, it will throw an error.

> foldr1 (+) [1..10]
55

> fold [1..10]
<interactive>:1:1:
    No instance for (Monoid a0) arising from a use of ‘it’

In order to solve this problem, we can wrap the integers in a Monoid, such as Sum or Product, and fold them.

And for that, we can use foldMap

> foldMap Sum [1..10]
Sum {getSum = 55}

Thus, fold can be implemented in terms of foldMap, since while using foldMap, we need to provide a function to convert each item in list to a Monoid.

fold :: Monoid m => t m -> m
fold xs = foldMap id xs

toList - List like folds

Any Foldable data structure can be converted to List using

toList :: Foldable t => t a -> [a]

.. which is a part of Foldable. If you use toList , folding the resulting list will produce the same result than folding the original structure directly. We can use foldMap to define toList.

toList = foldMap (\x -> [x])

Also, lists are free monoid for Haskell types. This means, any value can be given to the monoid such that the information is neither added nor erased from the original data.

-- Given a list xs :: [a]

xsFoldMap :: Monoid m => (a -> m) -> m
xsFoldMap = \f -> foldMap f xs

Since lists are free monoid, we can recover the original list xs by supplying (\x->[x]) to xsFoldMap.

Since we know folding with Foldable operations will cause in some loss of information if the data structure is complex, using toList to implement folds make it possible to reconstruct the original structure.

Examples

> import qualified Data.Set as S

> let testSet = S.fromList [1..10]
> testSet
fromList [1,2,3,4,5,6,7,8,9,10]

-- using toList to define data structure as free monoid
> import Data.Foldable
> toList testSet
[1,2,3,4,5,6,7,8,9,10]

-- using foldMap on list above result
> foldMap show testSet
"12345678910"

> foldMap Sum tSet
55

Traversable

Derivation

Consider the following Functor and Foldable instances for lists:

instance Functor [] where
    fmap _ []     = []
    fmap f (x:xs) = f x : fmap f xs

instance Foldable [] where
    foldMap _ []     = mempty
    foldMap f (x:xs) = f x <> foldMap f xs

Both fmap f and foldMap f walks across the list and apply f to each element. However, fmap f collects the result by rebuilding the list, and foldMap f collects the result by combining them with mappend.

But if we have to add a condition to our traversal, we can add it as a Maybe:

deleteTens :: (Num a, Ord a) => a -> Maybe a
deleteTens x = if (mod x 10 == 0) then Nothing else Just x

-- ghci
-- Here, fmap is the Functor, and deleteTens is our foldable
-- This results in [Maybe a]
> fmap deleteTens [0..20]

Why can’t we use a direct Foldable ? Because Foldable would replace the structure of the original list with that of whatever Monoid we pick for folding, and we will not be able to get back the original list.

But now we need a way to convert Maybe to list. To do that, we can combine the Maybe contexts of the values and recreate the list structure withing the combined context.

To do that, we make use of a type class which combines Functor context : Applicatives . This leads us to

-- sequenceA :: Applicative f => [f a] -> f [a]
instance Traversable [] where
    sequenceA []     = pure []
    sequenceA (u:us) = (:) <$> u <*> sequenceA us

-- equivalently:
instance Traversable [] where
    sequenceA us = foldr (\u v -> (:) <$> u <*> v) (pure []) us
  • Traversable is to Applicative contexts what Foldable is to Monoid values.
  • Similary, sequenceA is analogous to fold as it creates a summary of context within a structure, and rebuild structure with new context.

So how do we get the original list type back from fmap deleteTens [0..20]

> let seqWithoutTens = sequenceA . fmap deleteTens
> :t seqWithoutTens
seqWithoutTens
  :: (Num a, Ord a, Traversable t) => t a -> Maybe (t a)

> seqWithoutTens [0..10]
Nothing

> rejectWithNegatives [0..5]
Just [0,1,2,3,4,5]

Traversable class

Traversable is another type classes in the Prelude that can be used for data structure manipulation. A Traversable represents data structure which can be traversed, collecting results at each stop.

However, Traversable does not provide us with a way to change the data.

Let’s look at the typeclass

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)

    -- These methods have default definitions.
    -- They are merely specialised versions of the other two.
    mapM      :: Monad m => (a -> m b) -> t a -> m (t b)
    sequence  :: Monad m => t (m a) -> m (t a)

We will pretty much be using traverse and sequenceA for most of our operations.

And so, rewriting our Traversable instance to incorporate traverse and sequenceA :

instance Traversable [] where
	-- traverse
    traverse _ []     = pure []
	traverse f (x:xs) = (:) <$> f x <*> traverse f xs

	-- sequenceA
	sequenceA [] = pure []
	sequenceA (x:xs) = (:) <$> x <*> sequenceA xs

And if sequenceA is analogous to fold, traverse is analogous to foldMap. They can be defined in terms of each other, and therefore a minimal implementation of Traversable would look like:

class (Functor t, Foldable t) => Traversable t where
    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
    traverse f = sequenceA . fmap f

    sequenceA :: Applicative f => t (f a) -> f (t a)
    sequenceA = traverse id

sequenceA

> sequenceA [["a", "b"], ["c", "d"]]
[["a","c"],["a","d"],["b","c"],["b","d"]]

sequenceA works similar to sequence :: Monad m => [m a] -> m [a] from Control.Monad , it just additionally takes the applicative effects, runs them on the list, and then gives us the result.

In above example, our resultant list is of 4 elements, each consisting of 2 elements, which is exactly the kind of output you would expect from combinging with (<*>) by combining a 2x2 list.

sequence :: Monad m => [m a] -> m [a] from Control.Monad and sequenceA are doing the same thing. It simply takes the Applicative effects, runs them and pulls them out of the list.

traverse

The type of traverse, along with an example :

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

-- ghci

> traverse (\x -> Just (x + 1)) [0..4]
Just [1,2,3,4,5]

traverse type resembles mapping functions. traverse allows traversals which add an extra layer of context on top of the structure. It is a slightly modified version of (>>=) . The structure below new layer matches the original original structure, but the values are changed obviously.

As you can see in example above, the result maintains the structure of [0..4]

Conclusive Properties

This enables us to define a few properties of lens :

  • Traversals traverse all elements and each element is traversed only once
  • Traversals do not involve any skips or repetitions
  • the structure of the original structure is retained, though the values may change

Traversable Laws

Identity Law

Traversing with Identity constructor wraps the structure with Indentity, which changes nothing and the original structure can be recovered by runIdentity . Thus, Identity constructor is the identity traversal.

newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
    fmap f (Identity x) = Identity (f x)

instance Applicative Identity where
    pure x = Identity x
    Identity f <*> Identity x = Identity (f x)

-- formulating
traverse Identity = Identity
sequenceA . fmap Identity = Identity

Composition Law

Compose is used to form composition of functors, but if we compose two Applicatives, we get an Applicative as result.

As per composition law, it does not matter whether the two traversals are performed separately or if they are composed in order to walk the structure only once.

The composition law is stated in terms of the Compose functor:

newtype Compose f g a = Compose { getCompose :: f (g a) }

instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose x) = Compose (fmap (fmap f) x)

instance (Applicative f, Applicative g) => Applicative (Compose f g) where
    pure x = Compose (pure (pure x))
    Compose f <*> Compose x = Compose ((<*>) <$> f <*> x)

-- formulating
traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f
sequenceA . fmap Compose = Compose . fmap sequenceA . sequenceA

Applicative Homomorphism Law

An applicative homomorphism is analogoues to Monoid homomorphisms, and it is a function which preserves the Applicative operations, such that:

-- Given a choice of f and g, and for any a,
t :: (Applicative f, Applicative g) => f a -> g a

t (pure x) = pure x
t (x <*> y) = t x <*> t y

-- formulating
t . traverse f = traverse (t . f)
t . sequenceA = sequenceA . fmap t

Implementation for Foldable using Traversable

Traversable allows us to define Functor and Foldable, i.e. implement both fmap and foldMap using traverse as long as Traversable instance follows the laws.

fmap

Comparing fmap with traverse :

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

In traverse the function that is passed returns a value wrapped in Applicative context, and the result obtained from traverse is also wrapped.

We can Identity functor to wrap the value after we apply the functor and then unwrap it at the end (using runIdentity :: Identity a -> a), to get the exact same type as fmap. Thus, using Idenity to make traversal out of an arbitrary function, we get :

fmap f = runIdentity . traverse (Identity . f)

foldMap

Comparing foldMap with traverse :

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

We need a way to convert each element of Traversable to a Monoid. To do this, we will use Const from Control.Applicative.

Const is a constant functor such that, the value of type Const a b holds value a which is unaffected by fmap . To define foldMap , a value would be an Applicative, such that :

instance Monoid a => Applicative (Const a) where
    pure _ = Const mempty
    Const x <*> Const y = Const (x `mappend` y)

-- (<*>) combines the values in each context with mappend

In order to make a traversal out of any Monoid m => a -> m function, we can define foldMap as :

foldMap f = getConst . traverse (Const . f)

Foldable

After defining fmap and foldMap, we can use them to define a Functor and a Foldable instance for any Traversable.

For example, let’s take a simple list type :

-- our definitions

fmap' f    = runIdentity . traverse (Identity . f)
foldMap' f = getConst . traverse (Const . f)

-- defining Functor and Foldable instance for List

data List a = Nil
            | Cons a (List a)
            deriving Show

instance Functor List where
    fmap = fmap'

instance Foldable List where
    foldMap = foldMap'

instance Traversable List where
    traverse _ Nil = pure Nil
    traverse f (Cons x xs) = fmap Cons (f x) <*> traverse f xs

Checking how it works on ghci :

> traverse (\x -> Just (x + 1)) (Cons 1 (Cons 2 (Cons 3 Nil)))
Just (Cons 2 (Cons 3 (Cons 4 Nil)))

> fold (Cons "hello" (Cons "haskell" Nil))
"hellohaskell"

> fmap (+1) (Cons 1 (Cons 2 (Cons 3 Nil)))
Cons 2 (Cons 3 (Cons 4 Nil))