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 withgtraverse
, 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 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
gfoldl
is really agfoldr
: it traverses the elements in the reverse order.
I’ll talk more about these in subsequent articles.