Geek Answers Handbook

Is there something we lose with MonoFoldable?

MonoFoldable in a mono-traversable package seems to be able to implement all the usual folding containers, etc., for example, things like Bytestring and uniform tuples can be made MonoFoldable , but not Foldable . My question is that we are losing something from MonoFoldable that we don’t have in Foldable , with the exception of the need for some advanced GHC functions, which makes it a little more complicated, for example, for writers and possibly for getting uglier error messages?

For example, is there some kind of code that when using Foldable compiles, but with MonoFoldable types MonoFoldable not output, for example? Or is there anything else that makes the client (and not the instance script code) significantly easier with Foldable than MonoFoldable ?

+5
source share
2 answers

You lose parametricity.

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

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

+2
source

The biggest thing you lose is polymorphic recursion. View the okasaki list:

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

We can write

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

But if we try to use only MonoFoldable , we are stuck. Necessary instance restriction on q , forall x . (MonoFoldable (qx), Element (qx) ~ x) forall x . (MonoFoldable (qx), Element (qx) ~ x) cannot be expressed in any usual way. It is probably possible to get around this with Data.Constraint.Forall , but it gets pretty ugly.

A smaller problem is that the code can get more complex type signatures. For instance,

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

amazes me as below

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

Easy MonoFoldable : change MonoFoldable definition to

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

which will give you

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

Alternatively, scrap Element in general and use

 class MonoFoldable'' ac | c -> a

which gives a similarly simplified signature.

Unfortunately, Michael Snoyman does not agree with me on this issue. I can write my own wrapper package for a while to open my preferred API.

+2
source

More articles:


All Articles