# gtraverse vs. gfoldl

Published on

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.

## gtraverse through gfoldl

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

```
= gfoldl g pure
gtraverse f where
= acc <*> f x g acc 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 `<*>`

.

## gfoldl through gtraverse

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
Pure x) = z x
foldAp f z (Ap (I x) k) = (foldAp f z k) `f` x foldAp f z (
```

`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

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

Nice!

## Consequences

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.

## Remaining issues

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.