Foldable and Traversable vs. FunctorM
lemming at henning-thielemann.de
Thu Feb 26 17:53:35 EST 2009
After writing some FunctorM instance for GHC-6.4, then converting them to
Traversable instances for GHC-6.8, I found that most of the time, if not
always, I actually needed a FunctorM instance (i.e. fmapM method), not a
Defining a Traversable instance requires me to also define a Foldable
instance, i.e. a foldMap function. I had trees, lists and singletons
extended by additional information, e.g.
data PositionList a = PositionList [(Position, a)]
data AsyncException e a = AsyncException (Maybe e) a
However 'foldMap' cannot utilize the additional information, namely
Position and (Maybe e), respectively. In the first case this is sad, in
the second case I consider this bad, since it is too easy to throw away
and thus ignore the exception (Maybe e). Some kind of fold is always
useful on these structures, but 'foldMap' is too limited.
For Traversable there is always both sequence and mapM (and their
Applicative counterparts), although you need to define only one of them.
However 'sequence' works on interim data structures that are not very
natural. Imagine a data structure with a 'string' parameter that is
intended for instantiation by String or ByteString. Now 'sequence'
requires instantiations like (IO String) or (State s ByteString) which do
not share common properties of String and ByteString, e.g. having a
'length' function. Although possible, those interim types look
inappropriate to me.
Even more, consider a data structure like StorableVector which requires
certain properties of its elements. StorableVector is intended for Int,
Double and other Storable types, but you cannot store (IO Double) values.
This example is not practical, because the Storable restriction disallows
to define both Traversable and FunctorM instances. However you see, that
one cannot even imagine 'sequence' on StorableVector, whereas 'mapM' is
possible, yet very inefficient (needs copying the entire vector for each
My conclusion is, that FunctorM was better than its reputation, and that
Traversable as it is, is not what I need most of the time. What are the
experiences of other Traversable users?
More information about the Libraries