Published on March 29, 2013; tags: Haskell, GTraversable

In Generalizing generic fold, I introduced the `gtraverse`

function as an alternative to `gfoldl`

for generic programming.

To remind the important points:

`gtraverse`

allows more instances to be written, being more flexible about which elements can be treated as being on the same level;- on the other hand, everything that is possible to do with
`gfoldl`

seems to be possible to do with`gtraverse`

, too.

It turns out that my intuition was wrong. There is a beautiful correspondence between `gfoldl`

and `gtraverse`

which shows that they are, in fact, equivalent in power. Read on to find out why, and what this means for practical generic programming.

As a quick warm-up, let’s implement `gtraverse`

through `gfoldl`

.

For simplicity, let’s assume that `gfoldl`

and `gtraverse`

are both methods of the same class, `Data`

:

```
{-# LANGUAGE RankNTypes, GADTs, NoMonoLocalBinds #-}
class Data a where
gfoldl
:: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g)
-> a -> c a
gtraverse
:: Applicative w
=> (forall d . Data d => d -> w d)
-> a -> w a
```

Then

```
gtraverse f = gfoldl g pure
where
g acc x = acc <*> f x
```

In plain English, when folding, we inject each element into `c`

using the supplied function `f`

, and then combine it with the accumulator using `<*>`

.

It turns out that `gfoldl`

can also be interpreted as an applicative traversal for a particular functor — namely, the *free applicative functor*. We’ll use the one from the free package for now.

If we run `gtraverse`

with `liftAp Identity`

(where `Identity`

wraps its element into a trivial applicative functor), we’ll get a *list* rather than a *tree*, which can be easily folded in a `gfoldl`

-like fashion.

One minor issue is that `Identity`

has to capture the `Data`

dictionary of the elements. We can easily achieve that using a GADT

`data I a where I :: forall a . Data a => a -> I a`

Now, `gtraverse (liftAp . I)`

has type `Data a => a -> Ap I a`

. It transforms any value for which `gtraverse`

is defined to a (heterogeneous) list `Ap I a`

, which contains all immediate children of that value, together with their `Data`

dictionaries.

The next step is to fold that list:

```
foldAp
:: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g)
-> Ap I a -> c a
foldAp f z (Pure x) = z x
foldAp f z (Ap (I x) k) = (foldAp f z k) `f` x
```

`foldAp`

takes the same two functional arguments as `gfoldl`

. But instead of working on the original value, it works on the flattened `Ap`

-list.

After gluing the two steps together, we get

`gfoldl f z = foldAp f z . gtraverse (liftAp . I)`

Nice!

So, what does this mean? Do you not need `gtraverse`

since `gfoldl`

can do all the same things?

No!

It is much easier to write instances for your data types using `gtraverse`

, especially when you want to present an alternative view on the type from what is directly implied by its definition. (If you doubt it, you can still try to encode the uniform `Data`

instance for lists and compare it with the `gtraverse`

-based one.)

On the other hand, it is nice to know that we don’t really lose any power by adopting `gtraverse`

instead of `gfoldl`

.

You can try it out right now: I’ve just uploaded the first version of traverse-with-class on hackage.

There are a couple of issues in our `gfoldl`

implementation above^{1}:

- Because of the free applicative functor usage, it has the same quadratic complexity problems as free monads.
- Because of the way this free applicative works, our
`gfoldl`

is really a`gfoldr`

: it traverses the elements in the reverse order.

I’ll talk more about these in subsequent articles.

to make it clear, there are no such issues in the library, because it doesn’t provide a

`gfoldl`

function. It provides unrelated functions`gfoldl'`

and`gfoldr`

with different types.↩