gtraverse vs. gfoldl

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

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 <*>.

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
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!

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.
2. 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.