7

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?

duplode
  • 33,731
  • 7
  • 79
  • 150
Clinton
  • 22,361
  • 15
  • 67
  • 163
  • It requires `TypeFamilies` while `Foldable` doesn't for one? – Cubic Sep 22 '16 at 09:31
  • 4
    Not directly an answer, but `MonoFoldable`'s cousin [`MonoFunctor`](https://hackage.haskell.org/package/mono-traversable-1.0.0.1/docs/Data-MonoTraversable.html#t:MonoFunctor) is inferior to `Functor` in that you can't change the type of the things inside it. Same goes for `MonoTraversable` – Benjamin Hodgson Sep 22 '16 at 09:36
  • 5
    I believe `MonoFoldable` fully generalizes `Foldable`, with the caveats around error messages and type extensions you mentioned. As @BenjaminHodgson mentions, the other classes in the hierarchy don't fulfill this. I'd be interested if someone has a counter-example to this, as I have no proof that this belief is correct. – Michael Snoyman Sep 22 '16 at 10:56
  • @MichaelSnoyman, see my answer regarding polymorphic recursion. – dfeuer Sep 30 '16 at 19:37

2 Answers2

4

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.

Derek Elkins left SE
  • 2,079
  • 12
  • 14
4

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!

dfeuer
  • 48,079
  • 5
  • 63
  • 167