Is there anything we lose with MonoFoldable?

Question

MonoFoldable in the mono-traversable package seems to be able to implement all of the usual Foldable containers and more, for example, things like Bytestring and homogeneous tuples can be made MonoFoldable but not Foldable. My question is, do we lose anything from MonoFoldable that we don't have in Foldable, aside from requiring some advanced GHC features, making it slightly more tricky for instance writers and perhaps getting uglier error messages?

For example, is there some code which when using Foldable compiles but with MonoFoldable types are not inferred for example? Or anything else that makes client (not instance writer code) significantly simpler with Foldable than MonoFoldable?

Answer 1

You lose parametricity.

A type (Foldable f) => f a -> [a] provides significantly different guarantees than (MonoFoldable c) => c -> [Element c].

You can play with a free theorem generator to get some ideas of the properties, but as a simple example the former type provides the property that any element in the output must occur in the input. This property is in no way guaranteed by the latter type.

Answer 2

The biggest thing you lose is polymorphic recursion. Consider Okasaki's catenable lists:

data Cat q a = Empty | Cat a (q (Cat q a))

We can write

instance Foldable q => Foldable (Cat q) where
   foldMap _ Empty = mempty
   foldMap f (Cat a q) = f a <> foldMap (foldMap f) q

But if we try to use just MonoFoldable, we're stuck. The necessary instance constraint on q, forall x . (MonoFoldable (q x), Element (q x) ~ x), can't be expressed in any usual fashion. It's probably possible to work around that with Data.Constraint.Forall, but it gets pretty ugly.

---

A smaller problem is that code may get more complex type signatures. For example,

osum :: (MonoFoldable c, Num (Element c)) => c -> Element c

strikes me as inferior to

sum :: (Foldable f, Num n) => f n -> n

The fix is easy: change the definition of MonoFoldable to

class (a ~ Element c) => MonoFoldable' a c where ...

which would give you

osum' :: (MonoFoldable' n c, Num n) => c -> n

Alternatively, scrap Element altogether, and use

class MonoFoldable'' a c | c -> a

which gives a similarly simplified signature.

Unfortunately, Michael Snoyman disagrees with me on this point. I may write my own wrapper package some time to expose my preferred API.

---

Update: now that we have the QuantifiedConstraints language extension, it's actually possible to express Foldable in terms of MonoFoldable!