I think that mono-traversable doesn’t get enough love; it is in roughly the same position that Semigroup was in, before the Monoid hierarchy was corrected, or more recently, Functor and Bifunctor themselves.
I am suggesting that we do the same hierarchy unification / cleanup with Monofunctor, and make it a superclass of Functor. My justification is that every functor is capable of performing all of the functions of a monomorphic functor, simply by not changing the element type during map. My understanding is that, unifying Monofunctor and Functor is difficult mostly because we are dealing with higher-order types, so we have to pull out some heavy hammers.
I also propose that we give Monofunctor and friends some slightly better terminology, because it will help onboard new users. The awkward naming and lack of presence in the base libraries makes discoverability hard, and if you don’t know what monomorphic and traversable mean, you’ll probably end up reaching for a full functor when a monofunctor would have sufficed - not unlike how people used to use monoids and monads but now we have semigroups and arrows too.
Lets begin:
{-# LANGUAGE ConstraintKinds
, KindSignatures
, QuantifiedConstraints
, TypeFamilies
#-}
-- Yeah, we needed a few "fun" things
To make things easier, we’ll define some shorthand for types:
type Value = Type
type Function = Type -> Type
Monofunctor is really all about the Elem type family, and its best to keep this at the top level, because both Mappable and Reducible need it, but they do not share a common superclass:
type family Elem (mono :: Value)
Monofunctor becomes Mappable
I propose we rename Monofunctor to Mappable, which is just as accurate but far more friendly, as well as being established nomenclature in other languages:
class Mappable m where
map :: (Elem m -> Elem m) -> m -> m
We do need a shim type, because even with QuantifiedConstraints and friends, since GHC doesn’t allow constraint tuples (even though it is logically sound
):
class (Mappable (f a), Elem (f a) ~ a) => MappableFunction f a
MappableFunction is just an empty class so instances are free, and if we use UndecidableInstances, we can implement it for free in a way that is always valid:
-- Needs UndecidableInstances, but it is safe in this instance
instance (Mappable (f a), Elem (f a) ~ a) => MappableFunction f a
This in turn allows us to finally make Functor a subclass of Mappable, with our MappableFunction shim in between:
-- Yay quantified constraints!
class (forall a . MappableFunction f a) => Functor (f :: Function) where
fmap :: (a -> b) -> f a -> f b
Monofoldable becomes Reducible
We can do the same thing with monofoldable - we have three functions instead of one, but again, we give them names accurate to well-established use in other languages.
class Reducible m where
reduce :: (a -> Elem m -> a) -> a -> m -> a -- Left fold
accumulate :: (Elem m -> a -> a) -> a -> m -> a -- Right fold
reduceMap :: Monoid a => (Elem m -> a) -> m -> a -- Fold map aka mapReduce
-- Same shim
class (Reducible (f a), Elem (f a) ~ a) => ReducibleFunction f a
-- And we use it to make Reducible a superclass of Foldable
class (forall a . ReducibleFunction t a) => Foldable (t :: Function) where
foldl :: (b -> a -> b) -> b -> t a -> b
foldr :: (a -> b -> b) -> b -> t a -> b
foldMap :: Monoid m => (a -> m) -> t a -> m
Monotraversable becomes Visitable
Lets go for thirds, shall we? Traversable is different from Functor and Foldable - it has both as superclasses, so we don’t even need a shim class anymore, we just define Visitable:
class (Mappable m, Reducible m) => Visitable m where
visit :: Applicative f => (Elem m -> f (Elem m)) -> m -> f m -- otraverse
-- Omitting omapM, is just otraverse
-- We don't even need to modify Traversable, it inherits the changes automatically.
-- But we still need the shim if we want to enforce the link to Visitable
class (Visitable (f a), Elem (f a) ~ a) => VisitableFunction f a
class (Functor t, Foldable t, forall a . VisitableFunction t a) => Traversable (t :: Function) where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
In the end we have these nice friendly classes:
class Mappable m where
map :: (Elem m -> Elem m) -> m -> m
class Reducible m where
reduce :: (a -> Elem m -> a) -> a -> m -> a
accumulate :: (Elem m -> a -> a) -> a -> m -> a
reduceMap :: Monoid a => (Elem m -> a) -> m -> a
class (Mappable m, Reducible m) => Visitable m where
visit :: Applicative f => (Elem m -> f (Elem m)) -> m -> f m
I feel like I’m far more likely to use these, instead of having to remember and parse omap and ofoldl and otraverse. Obviously, it needs a few default implementations to make converting easier because suddenly functor has a superclass, but I didn’t want to clutter the proposal.