# # Foldable

`Foldable`

is the class of types `t :: * -> *`

which admit a **folding** operation. A fold aggregates the elements of a structure in a well-defined order, using a combining function.

## # An instance of Foldable for a binary tree

To instantiate `Foldable`

you need to provide a definition for at least `foldMap`

or `foldr`

.

```
data Tree a = Leaf
| Node (Tree a) a (Tree a)
instance Foldable Tree where
foldMap f Leaf = mempty
foldMap f (Node l x r) = foldMap f l `mappend` f x `mappend` foldMap f r
foldr f acc Leaf = acc
foldr f acc (Node l x r) = foldr f (f x (foldr f acc r)) l
```

This implementation performs an in-order traversal (opens new window) of the tree.

```
ghci> let myTree = Node (Node Leaf 'a' Leaf) 'b' (Node Leaf 'c' Leaf)
-- +--'b'--+
-- | |
-- +-'a'-+ +-'c'-+
-- | | | |
-- * * * *
ghci> toList myTree
"abc"
```

The `DeriveFoldable`

extension allows GHC to generate `Foldable`

instances based on the structure of the type. We can vary the order of the machine-written traversal by adjusting the layout of the `Node`

constructor.

```
data Inorder a = ILeaf
| INode (Inorder a) a (Inorder a) -- as before
deriving Foldable
data Preorder a = PrLeaf
| PrNode a (Preorder a) (Preorder a)
deriving Foldable
data Postorder a = PoLeaf
| PoNode (Postorder a) (Postorder a) a
deriving Foldable
-- injections from the earlier Tree type
inorder :: Tree a -> Inorder a
inorder Leaf = ILeaf
inorder (Node l x r) = INode (inorder l) x (inorder r)
preorder :: Tree a -> Preorder a
preorder Leaf = PrLeaf
preorder (Node l x r) = PrNode x (preorder l) (preorder r)
postorder :: Tree a -> Postorder a
postorder Leaf = PoLeaf
postorder (Node l x r) = PoNode (postorder l) (postorder r) x
ghci> toList (inorder myTree)
"abc"
ghci> toList (preorder myTree)
"bac"
ghci> toList (postorder myTree)
"acb"
```

## # Definition of Foldable

```
class Foldable t where
{-# MINIMAL foldMap | foldr #-}
foldMap :: Monoid m => (a -> m) -> t a -> m
foldMap f = foldr (mappend . f) mempty
foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo #. f) t) z
-- and a number of optional methods
```

Intuitively (though not technically), `Foldable`

structures are containers of elements `a`

which allow access to their elements in a well-defined order. The `foldMap`

operation maps each element of the container to a `Monoid`

(opens new window) and collapses them using the `Monoid`

structure.

## # Counting the elements of a Foldable structure

`length`

counts the occurences of elements `a`

in a foldable structure `t a`

.

```
ghci> length [7, 2, 9] -- t ~ []
3
ghci> length (Right 'a') -- t ~ Either e
1 -- 'Either e a' may contain zero or one 'a'
ghci> length (Left "foo") -- t ~ Either String
0
ghci> length (3, True) -- t ~ (,) Int
1 -- '(c, a)' always contains exactly one 'a'
```

`length`

is defined as being equivalent to:

```
class Foldable t where
-- ...
length :: t a -> Int
length = foldl' (\c _ -> c+1) 0
```

Note that this return type `Int`

restricts the operations that can be performed on values obtained by calls to the `length`

function. `fromIntegral`

is a useful function that allows us to deal with this problem.

## # Folding a structure in reverse

Any fold can be run in the opposite direction with the help of the `Dual`

monoid (opens new window), which flips an existing monoid so that aggregation goes backwards.

```
newtype Dual a = Dual { getDual :: a }
instance Monoid m => Monoid (Dual m) where
mempty = Dual mempty
(Dual x) `mappend` (Dual y) = Dual (y `mappend` x)
```

When the underlying monoid of a `foldMap`

call is flipped with `Dual`

, the fold runs backwards; the following `Reverse`

type is defined in `Data.Functor.Reverse`

(opens new window):

```
newtype Reverse t a = Reverse { getReverse :: t a }
instance Foldable t => Foldable (Reverse t) where
foldMap f = getDual . foldMap (Dual . f) . getReverse
```

We can use this machinery to write a terse `reverse`

for lists:

```
reverse :: [a] -> [a]
reverse = toList . Reverse
```

## # Flattening a Foldable structure into a list

`toList`

flattens a `Foldable`

structure `t a`

into a list of `a`

s.

```
ghci> toList [7, 2, 9] -- t ~ []
[7, 2, 9]
ghci> toList (Right 'a') -- t ~ Either e
"a"
ghci> toList (Left "foo") -- t ~ Either String
[]
ghci> toList (3, True) -- t ~ (,) Int
[True]
```

`toList`

is defined as being equivalent to:

```
class Foldable t where
-- ...
toList :: t a -> [a]
toList = foldr (:) []
```

## # Performing a side-effect for each element of a Foldable structure

`traverse_`

executes an `Applicative`

action for every element in a `Foldable`

structure. It ignores the action's result, keeping only the side-effects. (For a version which doesn't discard results, use `Traversable`

(opens new window).)

```
-- using the Writer applicative functor (and the Sum monoid)
ghci> runWriter $ traverse_ (\x -> tell (Sum x)) [1,2,3]
((),Sum {getSum = 6})
-- using the IO applicative functor
ghci> traverse_ putStrLn (Right "traversing")
traversing
ghci> traverse_ putStrLn (Left False)
-- nothing printed
```

`for_`

is `traverse_`

with the arguments flipped. It resembles a `foreach`

loop in an imperative language.

```
ghci> let greetings = ["Hello", "Bonjour", "Hola"]
ghci> :{
ghci| for_ greetings $ \greeting -> do
ghci| print (greeting ++ " Stack Overflow!")
ghci| :}
"Hello Stack Overflow!"
"Bonjour Stack Overflow!"
"Hola Stack Overflow!"
```

`sequenceA_`

collapses a `Foldable`

full of `Applicative`

actions into a single action, ignoring the result.

```
ghci> let actions = [putStrLn "one", putStLn "two"]
ghci> sequenceA_ actions
one
two
```

`traverse_`

is defined as being equivalent to:

```
traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()
traverse_ f = foldr (\x action -> f x *> action) (pure ())
```

`sequenceA_`

is defined as:

```
sequenceA_ :: (Foldable t, Applicative f) -> t (f a) -> f ()
sequenceA_ = traverse_ id
```

Moreover, when the `Foldable`

is also a `Functor`

, `traverse_`

and `sequenceA_`

have the following relationship:

```
traverse_ f = sequenceA_ . fmap f
```

## # Flattening a Foldable structure into a Monoid

`foldMap`

maps each element of the Foldable structure to a `Monoid`

(opens new window), and then combines them into a single value.

`foldMap`

and `foldr`

can be defined in terms of one another, which means that instances of `Foldable`

need only give a definition for one of them.

```
class Foldable t where
foldMap :: Monoid m => (a -> m) -> t a -> m
foldMap f = foldr (mappend . f) mempty
```

Example usage with the `Product`

monoid (opens new window):

```
product :: (Num n, Foldable t) => t n -> n
product = getProduct . foldMap Product
```

## # Checking if a Foldable structure is empty

`null`

returns `True`

if there are no elements `a`

in a foldable structure `t a`

, and `False`

if there is one or more. Structures for which `null`

is `True`

have a `length`

(opens new window) of 0.

```
ghci> null []
True
ghci> null [14, 29]
False
ghci> null Nothing
True
ghci> null (Right 'a')
False
ghci> null ('x', 3)
False
```

`null`

is defined as being equivalent to:

```
class Foldable t where
-- ...
null :: t a -> Bool
null = foldr (\_ _ -> False) True
```

#### # Remarks

If `t`

is `Foldable`

it means that for any value `t a`

we know how to access all of the elements of `a`

from "inside" of `t a`

in a fixed linear order. This is the meaning of `foldMap :: Monoid m => (a -> m) -> (t a -> m)`

: we "visit" each element with a summary function and smash all the summaries together. `Monoid`

s respect order (but are invariant to different groupings).