Foldable and Traversable vs. FunctorM

Henning Thielemann lemming at
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 
Traversable instance.

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 
added element).

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 mailing list