In Generalizing generic fold, I introduced the
gtraverse function as an alternative to
gfoldl for generic programming.
To remind the important points:
gtraverseallows 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
gfoldlseems to be possible to do with
It turns out that my intuition was wrong. There is a beautiful correspondence between
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
For simplicity, let’s assume that
gtraverse are both methods of the same class,
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
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
One minor issue is that
Identity has to capture the
Data dictionary of the elements. We can easily achieve that using a GADT
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
The next step is to fold that list:
foldAp takes the same two functional arguments as
gfoldl. But instead of working on the original value, it works on the flattened
After gluing the two steps together, we get
So, what does this mean? Do you not need
gfoldl can do all the same things?
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
On the other hand, it is nice to know that we don’t really lose any power by adopting
gtraverse instead of
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 above1:
- 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
gfoldlis 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
gfoldlfunction. It provides unrelated functions
gfoldrwith different types.↩