In an excellent piece of pedagogy, Gabriel Gonzalez explains how to implement composable streaming (space leak free) folds in Haskell. In this article I’ll explain how to make these composable folds even more composable!

Gabriel’s key idea is captured in his foldl
package, where the notion
of a left fold is abstracted into the `Fold`

datatype.

`data Fold a b = forall x . Fold (x -> a -> x) x (x -> b)`

A `Fold a b`

represents a left fold on a list of `a`

, updating a state
of (existential) type `x`

, and eventually returning a final value of type `b`

.

- The first component (of type
`x -> a -> x`

) reads a value of type`a`

from the list and updates the state`x`

. - The second component (of type
`x`

) is the start state. - The third component (of type
`x -> b`

) maps the final state of type`x`

to a final state of type`b`

.

There is an `Applicative`

instance for `Fold a`

which combines two
separate folds into a single fold that combines their state. In this
way we can avoid space leaks when running two separate folds on the
same list. For example

```
average = (/) <$> L.sum <*> L.genericLength
L.fold average [1..10000000]
```

only walks the list once and does not leak space.

Suppose I have a value of type `[(Bool, Double)]`

and I want to run `and`

on the first component (returns `True`

if all elements are `True`

,
`False`

otherwise), and `average`

(as defined above) on the second
component. The simple approach of projecting out each component and
running the folds separately is flawed.

```
myList :: [(Bool, Double)]
L.fold L.and (map fst myList)
L.fold average (map snd myList)
```

This exhibits exactly the kind of space leaks we are trying to avoid.
The spine of `myList`

is fully forced and kept around between the two
calls to `L.fold`

. There is a solution, and that is to use a
`Profunctor`

instance.

A `Profunctor`

`p`

is like a `Functor`

with two arguments, but the
first is *contravariant* meaning that it acts as a receiver of
values. The class definition for `Profunctor`

is

```
class Profunctor p where
lmap :: (a -> a') -> p a' b -> p a b
rmap :: (b -> b') -> p a b -> p a b'
-- rmap is just like fmap on the right-hand type variable
```

(For a more in-depth look at `Profunctor`

see my 24 Days of Hackage
post on the
subject).

`Fold`

is a `Profunctor`

, because `Fold a b`

*receives* values of type
`a`

and *emits* a value of type `b`

. Using the `Profunctor`

instance
we can combine two `Fold`

s of different argument types into one:

```
(***!) :: (Applicative (p (a, a')), Profunctor p) =>
p a b -> p a' b' -> p (a, a') (b, b')
p ***! p' = (,) <$> lmap fst p <*> lmap snd p'
andWithAverage :: L.Fold (Bool, Double) (Bool, Double)
andWithAverage = L.and ***! average
```

Now we can run `L.fold andWithAverage myList`

*without* space leaks!

One could write a typeclass to capture the essence of what we have just implemented

```
class Profunctor p => ProductProfunctor p where
(***!) :: p a b -> p a' b' -> p (a, a') (b, b')
empty :: p () ()
```

`(***!)`

can be implemented exactly as given above, and `empty`

is
just `pure ()`

. So what is the point of using a typeclass rather than
simply using the `Applicative`

and `Profunctor`

instances? The class
ensures that the `Applicative`

instance for `p a`

is *independent* of
a. I’m not *certain* this is necessary, but it does seem to be a
useful sanity check.

The `Profunctor`

instance for `Fold`

increases the composability of
Gabriel’s composable streaming folds. The `ProductProfunctor`

is an
interesting concept.

The `foldl`

library doesn’t actually supply a `Profunctor`

instance,
but Edward Kmett’s similar `folds`

library does have
`Profunctor`

instances.