# lens over tea #3: folds

Okay, the exploration of lens continues. This post is a bit boring because folds are much less interesting than, say, prisms, but hey, I promised shorter posts.

`Fold`

A fold is to a getter what a traversal is to a lens:

```
type Lens s t a b = forall f. Functor f => ...
type Traversal s t a b = forall f. Applicative f => ...
type Getter s a = forall f. (Contravariant f, Functor f) => ...
type Fold s a = forall f. (Contravariant f, Applicative f) => ...
```

(Isn't it cool how each combination of constraints gives us a different useful type?)

So, as you may expect, a fold is simply a getter that can return multiple values. Now let's write one without looking anywhere!

Uhhh... my imagination is broken. I'm going to look at `Control.Lens.Fold`

to choose a fold to reimplement.

[looks]

Meh. Most things there – like `worded`

– are not folds, but traversals or something else in disguise, and other things are more general than folds. We don't have much choice – let's do `folded`

.

`folded :: Foldable t => Fold (t a) a`

(Actually it's an `IndexedFold`

, but I'm still ignoring everything indexed.)

`Foldable`

Just in case you don't know what `Foldable`

is: it's basically a class for things that have elements and from which you can extract said elements (some of the examples are `Maybe`

, `Set`

, lists, trees, etc). A popular definition is “everything that can be turned into a list”, since `toList`

is method of `Foldable`

:

```
class Foldable t where
...
toList :: t a -> [a]
...
```

However, it's a bit misleading, because `toList`

doesn't work well on structures that can be infinite to the left. A snoc list, for instance (“snoc” is “cons” backwards):

`data SList a = Empty | SList a :> a`

An infinite snoc list has a last element, but no *first* element; thus, you can't apply `toList`

to it and get back anything. But you can still apply `foldMap`

– which is the real fundamental method of `Foldable`

– to it and get something back! Here's the type of `foldMap`

:

```
-- Map each element of the structure to a monoid, and combine the results.
foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m
```

I've no idea whether it's easy to understand what it does or not so easy, but the best way to understand is probably just to look at the implementation for trees:

```
data Tree a = Leaf a | Branch (Tree a) a (Tree a)
instance Foldable Tree where
-- Only 1 element – apply the function to it.
foldMap f (Leaf a) = f a
-- Several elements – combine everything that can be combined.
foldMap f (Branch left x right) = foldMap f left <> f x <> foldMap f right
```

Well, actually the best way is to write your own implementation for various types, but I don't expect you to write anything, because this is a post and posts are meant to be read and not... whatever. Back to snoc lists, here's an instance for them as well:

```
instance Foldable SList where
foldMap f Empty = mempty
foldMap f (xs :> x) = foldMap f xs <> f x
```

And an example of a left-infinite list:

```
enumS :: Int -> SList Int
enumS n = enumS (n+1) :> n
-- A left-infinite list.
inf :: SList Int
inf = enumS 0
```

And a demonstration of how `foldMap`

works on it, using the `Last`

monoid:

```
> foldMap (Last . Just) inf
Last {getLast = Just 0}
```

If you want to read more about `Foldable`

, there's no good place to do it, because `Foldable`

is simple and boring. All knowledge you need is here:

`Foldable`

documentation.- The story about how and why
`Foldable`

got so many extra methods in GHC 7.10 (which, by the way, means that all`Foldable`

tutorials are out of date now) and also why lots of functions in`Prelude`

mention`Foldable`

now when previously they were just operating on lists. - A post about that thing with snoc lists and how
`Foldable`

isn't merely the`toList`

class.

`folded`

Okay, yeah, right, back to `folded`

. First, the signature (which I got just by expanding the definition of `Fold`

):

```
-- folded :: Foldable t => Fold (t a) a
folded :: (Contravariant f, Applicative f, Foldable t) =>
(a -> f a) -> t a -> f (t a)
```

At this point it would be helpful to recall the idea of getters *once again*.

(And at this point I also wonder: if I'm writing this whole thing and it takes me more than a dozen repetitions to understand what I'm doing, could it be a clue that something isn't right with my brain? To rephrase: am I dumb?)

The idea is as follows:

- The getter is given a function which hides an
`a`

in the functor. For instance,`Const`

. - This function is applied to the target element.
- The type of the result,
`f a`

, is changed to match the type we need to get –`f s`

(but the`a`

is still stored in the functor). - That's all, the
`a`

has been safely carried out and can then be extracted from the result.

With folds, it becomes a bit more interesting. Instead of applying the function to one element, we apply it to every element we need to carry out – and then we *combine* resulting functors. It's not something we could actually do with functors, but that's exactly why `Fold`

has an `Applicative`

constraint instead – unlike ordinary functors, applicative functors can be combined.

If this isn't very clear, it'll become clearer in a moment.

`folded f s = ...`

Okay, so we have `f :: a -> f a`

and `s :: t a`

. The only thing to do is to apply one to the other, which is something that `foldMap`

does:

`foldMap f s :: f a`

(The reason the result is `f a`

is that each function returns an `f a`

and then those are simply combined into a single `f a`

.)

Finally, the type has to be changed from `f a`

to `f (t a)`

, and that's what `coerce`

does. Thus, the definition of `folded`

is:

`folded f s = coerce $ foldMap f s`

Except that it's not, because if you try to compile it, you would get this type error:

```
Could not deduce (Data.Monoid.Monoid (f a)) …
arising from a use of ‘foldMap’
from the context (Contravariant f, Applicative f, Foldable t)
bound by the type signature for
folded :: (Contravariant f, Applicative f, Foldable t) =>
(a -> f a) -> t a -> f (t a)
```

How so? Well, apparently there's no instance of `Monoid`

for `f a`

, even if we know that if `f`

is `Contravariant`

and `Applicative`

, `f a`

*has* to be a `Monoid`

. No problem, we'll just make a newtype and write our own instance.

`newtype Folding f a = Folding { getFolding :: f a }`

(It's tempting to just write an instance like `(...) => Monoid (f a)`

without bothering with newtypes, but then you're going to have a huge problem with overlapping instances because – remember – GHC doesn't look at the constraints when resolving instances, so it would overlap with everything else from `[a]`

to `Maybe a`

.)

Here goes:

`instance (Contravariant f, Applicative f) => Monoid (Folding f a) where`

To make it easier, just pretend that `f`

is `Const`

here. Do you remember the discussion of monoids and applicative functors from the previous part, where we used the `Monoid r => Applicative (Const r)`

instance? Well, now we go backwards from that – if something is `Const`

-like and also `Applicative`

, we assume that it hides a monoid inside.

`pure`

for `Applicative (Const r)`

:

`pure _ = Const mempty`

`mempty`

for `Folding`

:

`mempty = Folding (coerce $ pure ())`

`<*>`

for `Applicative (Const r)`

:

`Const f <*> Const v = Const (f `mappend` v)`

`mappend`

for `Folding`

:

`mappend (Folding fa) (Folding fb) = Folding (fa *> fb)`

The resulting instance again because I'm not sure that the mess I wrote before is understandable:

```
instance (Contravariant f, Applicative f) => Monoid (Folding f a) where
mempty = Folding (coerce $ pure ())
mappend (Folding fa) (Folding fb) = Folding (fa *> fb)
```

And `folded`

itself, with newtype wrapping and unwrapping:

`folded f s = coerce . getFolding $ foldMap (Folding . f) s`

And a demonstration:

```
> Just True ^.. folded
[True]
```

## The `Monoid`

formulation of `Fold`

If you have looked at `Control.Lens.Fold`

, you could've noticed this alternative explanation of `Fold`

at the top:

A

`Fold s a`

is a generalization of something`Foldable`

. It allows you to extract multiple results from a container. A`Foldable`

container can be characterized by the behavior of`foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m`

Since we want to be able to work with monomorphic containers, we could generalize this signature to

`forall m. Monoid m => (a -> m) -> s -> m`

and then decorate it with

`Const`

to obtain`type Fold s a = forall m. Monoid m => Getting m s a`

Every

`Getter`

is a valid`Fold`

that simply doesn't use the`Monoid`

it is passed.In practice the type we use is slightly more complicated to allow for better error messages and for it to be transformed by certain

`Applicative`

transformers.

It's a pretty clear explanation, and I don't really have anything to add to it.

`both`

This one is an exercise, which is much simpler than `folded`

and so should be really trivial if it has clicked for you.

```
bothF :: Fold (a, a) a
bothF f s = ...
```

```
> (1,2) ^.. bothF
[1,2]
```

If you did it right, your code should be simpler than the code for actual `both`

.

Also, by the way, write actual `both :: Traversal' (a, a) a`

as well.

Also, using `both`

in the definition of `bothF`

is prohibited.

Also, I have said before that I don't expect you to write anything, but come on, this one is *really* simple. If you don't write it or at least spell mentally in your head, you're a chicken.

`replicated`

Yet another fold to reimplement because reimplementing things is *so* fun.

Fine, not really.

Whatever.

```
> 5 ^.. replicated 3
[5,5,5]
```

It'd be as easy as `bothF`

if we had `replicateA`

, but we only have `replicateM`

and that one is for monads and not applicatives, so we have to write it ourselves with `sequenceA`

and `replicate`

:

```
replicated :: Int -> Fold a a
replicated n f s = coerce $ sequenceA (replicate n (f s))
```

## Combining folds

There's a somewhat not very well-known trick for combining folds. Say, we want to make a fold that would combine elements from several folds – how could we do it?

Pretty easy, actually. Just get the result from one fold, from another fold, and combine them with `*>`

:

```
foldCombine :: Fold s a -> Fold s a -> Fold s a
foldCombine fa fb = \l s -> fa l s *> fb l s
```

```
> (1,2) ^.. foldCombine _2 _1
[2,1]
```

However, for common usage – when you're going to apply `^..`

or something like that straight away – there's a much simpler way. Just use `<>`

:

```
> (1,2,3) ^.. (_3 <> _1 <> _2)
[3,1,2]
```

Why does it work? There are 2 pieces to the puzzle:

Due to an existing instance of

`Monoid b => Monoid (a -> b)`

, all functions with*any*amount of arguments – provided that the result is a monoid – are monoids themselves.Usually the functor used in place of

`f`

would be`Const`

, and it's a monoid already without the need for`Folding`

and our additional instance.

(If it's still not clear, then I guess it's going to be another exercise.)

`Fold1`

An ordinary `Fold`

can easily return 0 elements. Can we write a type for folds that *have* to return 1 or more elements?

With the monoid formulation, it'd be pretty easy – just replace `Monoid`

with `Semigroup`

. (A semigroup is a monoid without `mempty`

, and we might get them in base soon, or we might not. Currently they live in the semigroups package, and it has more dependencies than I would like. Actually, I don't use lens itself for the same reason.) Anyway, since a fold with a `Semigroup m`

constraint would have to work on *anything* that is a semigroup, and a non-empty list is a semigroup, there'd be no way for it to return an empty list. Ha.

However, we use the `Contravariant f, Applicative f`

formulation. Here, the analog of `mempty`

is `pure`

– so, to get rid of empty folds, we have to get rid of `pure`

. Is there some class which gives us composition without `pure`

?..

Yep. It's called `Apply`

, it lives in Edward's semigroupoids package, and its sole operation is `<.>`

(`.>`

and `<.`

don't count). With it, we can declare `Fold1`

:

```
type Fold1 s a = forall f. (Contravariant f, Apply f) =>
(a -> f a) -> s -> f s
```

And with `.>`

, we can write non-empty folds. Such as `iterated`

, for instance:

```
> 3 ^.. takingWhile (<100000000) (iterated (^2))
[3,9,81,6561,43046721]
> 3 ^.. iterated (^2)
[3,9,81,6561,43046721,...
```

```
iterated :: (a -> a) -> Fold1 a a
iterated f g a = go a
where go a = g a .> go (f a)
```

**Open question:** `iterated`

doesn't actually use `Contravariant`

, so its real type signature is

```
Apply f => (a -> a) -> (a -> f a) -> a -> f a
Apply f => (a -> a) -> LensLike' f a a
```

and if you tried to apply `set`

or `over`

to it, everything would typecheck. Can this less restricted `iterated`

can be used in any way in which our `iterated`

can't?

Oh, and by the way: the same trick gives us `Traversal1`

, which traverses 1 or more values. Another name for it is “relevant traversal”.

Some googling revealed that nobody ever uses `Traversal1`

or `Fold1`

(in public..?), so I can't say when they are useful.

`Fold`

by itself is probably not very useful either, because most things that are folds are actually more than folds, the same way most instances of `Foldable`

are also functors.

Such is life.

The most used functions from `Control.Lens.Fold`

are `*Of`

functions, but I don't like them. Besides, they aren't really related to folds, they just take everything that is *at least* a fold, which is pretty much everything.