# Fantas, Eel, and Specification 11: Foldable

01 May 2017Welcome back, Fantasists! This week has been **hectic**, so I haven’t caught up the companion repository as I’d hoped to. However, I should have some time to devote to it this week, so watch this space! Anyway, why don’t we have some **down time** before we get onto the **really grizzly** parts of the spec? Let’s take a look at `Foldable`

.

Wouldn’t you know it, this one comes with a **new function** to add to our repertoire, and it’s one that might look a bit *familiar* to some readers:

```
reduce :: Foldable f =>
f a ~> ((b, a) -> b, b) -> b
```

Do we already know of any `Foldable`

types? I’ll suggest one:

```
Array.prototype.reduce ::
[a] ~> ((b, a) -> b, b) -> b
```

Straight away, `Array`

is a valid `Foldable`

type. In fact, Fantasy Land’s `Foldable`

was *deliberately* modelled after `Array`

. Why? Because this structure **generalises** `Array.reduce`

. **Bam**. With that in mind, let’s look at its law:

```
const toArray xs => xs.reduce(
(acc, x) => acc.concat([x]), []
)
u.reduce(f) === toArray(u).reduce(f)
```

This is a **really** weird law because it’s not very… rigorous. You’re unlikely to write a `Foldable`

and get this wrong, because the `reduce`

in `toArray`

probably works in the exact same way as the `reduce`

outside. In fact, it’s probably best to look at this more as a **behaviour** than a **law**. *You still have to obey it, though!*

There’s a *lot* of space for interpretation here, which isn’t necessarily a good thing. **On the other hand**, it makes it really easy to give some examples!

```
// reduce :: Maybe a
// ~> ((b, a) -> b, b) -> b
Maybe.prototype.reduce =
function (f, acc) {
return this.cata({
// Call the function...
Just: x => f(acc, x),
// ... or don't!
Nothing: () => acc
})
}
// reduce :: Either e a
// ~> ((b, a) -> b, b) -> b
Either.prototype.reduce =
function (f, acc) {
return this.cata({
// Call the function...
Right: x => f(acc, x),
// Or don't!
Left: _ => acc
})
}
```

Because `Nothing`

and `Left`

represent **failure**, we just return the accumulator. Otherwise, we can use our `f`

function once. These examples really just highlight that you don’t *need* a structure with (potentially) multiple values in order to write a `Foldable`

instance. However, it’s definitely **most useful** when that’s the case. For example, let’s build a **binary tree**:

```
// BTree a
const BTree = daggy.taggedSum({
// Recursion!
// Node (BTree a) a (BTree a)
Node: ['left', 'x', 'right'],
// Leaf
Leaf: []
})
```

So, `Node`

s represent “branch points” of the tree with values, and `Leaf`

s represent the ends of branches. Because `left`

and `right`

are also `BTree`

instances, this gives us a recursive tree construction:

```
const { Node, Leaf } = BTree
// 3
// / \
// 1 5
// /| |\
// X 2 4 X
// /| |\
// X X X X
const MyTree =
Node(
Node(
Leaf,
1,
Node(
Leaf,
2,
Leaf ) ),
3,
Node(
Node(
Leaf,
4,
Leaf ),
5,
Leaf ) )
```

*I’m too ashamed to say how long I spent drawing that tree.* Now, `Array.reduce`

combines all our values together (*if your Semigroup or Monoid klaxon just sounded, then I’m super proud ♥*) from left to right, so that’s probably what we want to imitate with this tree. How do we do that? With

**magical recursion**:

```
BTree.prototype.reduce =
function (f, acc) {
return this.cata({
Node: (l, x, r) => {
// Reduce the tree on the left...
const left = l.reduce(f, acc)
// Plus the middle element...
const leftAndMiddle = f(left, x)
// And then the right tree...
return r.reduce(f, leftAndMiddle)
},
// Return what we started with!
Leaf: () => acc
})
}
MyTree.reduce((x, y) => x + y, 0) // 15
```

**Woo**! We reduce the tree starting from the **left-most** element and work across. Whenever we hit a `Node`

, we just **recurse** and do the same thing!

We saw at the end of the last snippet that we can find the **sum** of all the elements, and we could just as easily write `min`

, `max`

, `product`

, or whatever. In fact, you can do anything with `Array.reduce`

and generalise it to all `Foldable`

types immediately! Whether we then have a `Maybe`

, an `Array`

, or even a `BTree`

, our functions will **Just Work™**!

`Product`

? `Min`

? `Max`

? This really does sound like `Monoid`

again, doesn’t it? Well, there are **no coincidences** in Fantasy Land. Back in the `Monoid`

post, we wrote the `fold`

function:

```
// A friendly neighbourhood monoid fold.
// fold :: Monoid m => (a -> m) -> [a] -> m
const fold = M => xs => xs.reduce(
(acc, x) => acc.concat(M(x)),
M.empty())
```

With our new-found `Foldable`

knowledge, we now know that this type signature is **too specific**. Let’s fix it:

```
fold :: (Foldable f, Monoid m)
=> (a -> m) -> f a -> m
```

Yes, this function will in fact work with **any** `Foldable`

structure and **any** `Monoid`

- you’ll never need to write `reduce`

again! Get comfortable with using `Monoid`

for reductions; it’s definitely a good way to make your code more **declarative**, and hence more **readable**. I know you’re probably *sick* of hearing about monoids, but they really are **everywhere**!

It turns out that *many* of your favourite `Functor`

types have sensible implementations for `reduce`

. However, there are **exceptions**:

We can’t `reduce`

the `Task`

type because we don’t know what the inner values are going to be! It’s the same with `Function`

: we don’t know what the return value is going to be until we give it an **argument**. Remember: **functors’ inner values aren’t always reachable**.

Incidentally, if a

`Functor`

doeshave an always-reachable inner value, we can call it a`Copointed`

functor. Remember how`Applicative`

’s`of`

is a function of`Pointed`

functors? Think about the relationship between`Pointed`

and`Copointed`

. There areno coincidencesin Fantasy Land!

This week, why not make a `Foldable`

**Rose Tree**? Or **Set**? There are plenty of opportunities to practise here. Before we go, some of you may have noticed that you can `reduce`

most things by just returning the **initial value** given to you:

```
MyType.prototype.reduce = (f, acc) => acc
```

It satisfies the “law”, right? This is what I mean: this law is **not a good’un**, and leaves too much room for interpretation. Still, there’s no point in *moaning*: we’ll see next time that `Traversable`

(my **all-time favourite** part of the Fantasy Land spec!) saves the day! From now on, Fantasists, the excitement is **non-stop**.

♥