Making Monofunctor and Monofoldable superclasses of Functor and Foldable

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 :melting_face:):

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.

3 Likes

Monofunctor lacks parametricity of Functor and thus does not guarantee a unique lawful implementation. E. g., omap = const id is a valid implementation for every container.

8 Likes

An excellent reason to exclude the undecidable shim instances, which I was already feeling was unnecessary - best leave it up to choice. *adds to notes*

I do not think this inhibits Mappable / Monofunctor from becoming a superclass of Functor though, the lawfulness / guarantee remains the responsibility of Functor, and so only Mappable / Monofunctors that satisfy it should be made into functor.

Otherwise, the multiplicity of instances and decision of whether there is one true special ‘The’ instance isnt too much unlike the situation that Semigroup and Monoid are in, often having multiple concurrently valid instances.

Instances of Functor are commonly autoderived by GHC. What would happen to this under your proposal? I guess GHC could also autoderive Monofunctor, but that entails autodefining Elem (f a) somehow, which seems to go beyond the scope of the mechanism.

5 Likes

I will not claim to have thought this far per dealing with GHC, but I am carrying out these experiments in my own compiler and so I have some notions.

You are absolutely correct - we cannot necessarily assume that we can derive Monofunctor or Elem. Easy counterexample:

type Counted a = (Int, a)
type CountedInt = Counted Int

In CountedInt, fst and snd are both Int, but they are not the same. One is always Int, the other is Int only by happenstance. Trying to derive Elem or Monofunctor for CountedInt would risk capturing the wrong fields.

So, deriving Elem or Monofunctor on its own, doesn’t work - but this isn’t unexpected, we need to consider them as sort of like fulfilling your root / base cases. However, that isn’t to say that there aren’t any cases where it is possible.

When we have a parametric type that is a functor, we know that we can use the functor definition to choose an element and to choose a map implementation. So, in all cases where we can already derive functor, we can also derive a valid instance of elem and monofunctor, if there isn’t one already.

The real problem is that GHC doesn’t allow inferring superclass instances even if the inference would be valid - which is understandable because its not solvable in general potentially due to there being multiple valid solutions, but sometimes I can define a unique superclass implementation from the subclass, and it would be nice to be able to intentionally allow it in those cases and not need a million empty class / instance declarations. I feel like this issue isn’t unique to Functor, either.

This is one of the reasons I have actually gone and started my own compiler, to experiment with solutions.

Barring that, default implementations using data and type families really goes a long way with deriving via to at least make things easier, but also the type-level magic starts getting sufficiently thick that it isn’t approachable for beginners, and I really want people to not be scared away so I really do want to find a proper solution.

There is an elegance to Functor and Monoid. “Elegance” is mostly subjective, but we can still point out concrete characteristics relevant to API design:

  1. Functor and Monoid are expressible in basic Haskell. There is value in doing things in simpler languages.
  2. Functor, Monoid (and Semigroup to a slightly lesser extent) are well-studied fundamental structures in theoretical computer science, which have proved quite versatile in practice as well. Monofunctor is occasionally useful but nowhere near the same utility.
2 Likes

Perhaps I didn’t get your exact meaning. Are you suggesting we do it now in GHC or in some hypothetical future in a hypothetical compiler? I initially thought that it’s the former, but your other messages suggest the latter.

My point is that currently it is extremely common to write

data Foo a = Foo Int a a deriving (Functor, Foldable, Traversable)

What does it become under your proposal? It could not be

data Foo a = Foo Int a a 
  deriving (Monofunctor, Functor, Monofoldable, Foldable, Monotraversable, Traversable)

because Monofunctor instance is not uniquely defined to be autoderived. Even if GHC is magically taught how to define Monofunctor if there is a Functor as well, there is an obstacle of Elem (Foo a). Who defines it and where?

1 Like

I think the entire MonoFoo hierarchy has outlived its usefulness, as the problems that it solves are much better solved by lens. omap is not necessary when you can provide a Traversal' Text Char or whatever and then use normal lens operators to work with it, and the learning of lens pays off for all the other data structures and operations you can use the lens vocabulary with. mono-traversable strikes me as an evolutionary dead-end at this point, and I would not endorse baking it into the class hierarchy at this point. Especially not when we don’t have a good story for introducing superclasses without forcing the universe to update their code; if we had that, I’d rather see semigroupoids’s classes enter the standard hierarchy.

10 Likes

@Bodigrim

I am moreso posting about what I am exploring currently with my own compiler, with the intent of opening a dialogue about the implications it has in general, than suggesting that we make these changes to GHC now - but with desire to talk about whether it is desireable or worth making it possible.

So the latter, but this discussion is exactly what I wanted - it helps me understand the roadblocks that GHC faces on a technical level as well as on a user level, and to figure out what were choices and what were tradeoffs.

Even if GHC is magically taught how to define Monofunctor if there is a Functor as well, there is an obstacle of Elem (Foo a). Who defines it and where?

Emphasis mine. In the case that we do decide to, somehow, define a Monofunctor instance from Functor, shouldn’t it always then be the case that Elem (Foo a) ~ a? As in, there are potentially other valid monofunctor instance and elements, but in the specific case of the functor instance, the functor always tells you the element. And in the case that we are not deriving Monofunctor from Functor, the question is moot.

@Lysxia

Monofunctor is occasionally useful but nowhere near the same utility.

@jackdk

I think the entire MonoFoo hierarchy has outlived its usefulness

I would beg to differ, and argue that it is underused, in the same way arrows would suffice for many applications that monads get used for - yet we don’t say arrows should be removed.

I think that high-level haskell gets more use out of functor, so its understandable to think it has little to no use, but I am finding monofunctors to crop up fairly often when working with low-level / memory / unlifted code.

A functor allows you to change its element type, which in the memory world might change the size of its allocation, which changes the structure which is a no-go - but a monofunctor actually works perfectly fine because it guarantees that the same memory can hold the transformed object, and so monofunctors allow you to perform in-place mutation which is a feature worth implementing and having some typeclass support for.

It makes more sense at the lower level, and honestly, you could make the case that this is an implementation detail that could and maybe even should be hidden from lifted haskell - I do quite strongly agree with @Lysxia 's statement:

There is value in doing things in simpler languages.

So my own statement is, I want to simplify the language for describing memory in unlifted haskell, even if it does mean considering unlifted haskell to be distinct from lifted haskell - and maybe thats what happens.

@jackdk

rather see semigroupoids’s classes enter the standard hierarchy

Oh aiming right at my heart are we? You’ll be quite pleased to hear then that my compiler will be including them in its base.

3 Likes

If you do work out how to add deriving superclassses to GHC, please let me know!

4 Likes

In an ideal world in which

  • all this is in base
  • with the whole semi-groupoid hierarchy, and their monomorphic couterparts
  • where you can do deriving Monad and you get the entire fine-grained hierarchy above derived

In such an ideal world, I love the idea. But, also in this ideal world, I strongly dislike the renaming. What would be the new names for the semi-groupoid hierarchy ?

I do not want to have to remember that visit is the monomorphic version of traverse, which itself could have been named mapA. So, in my dreams, I would pick

  • mapF instead of fmap
  • mapA intead of traverse
  • mapM is already a dream come true !
  • mapO instead of omap
  • mapAO instead of otraverse
  • mapMO instead of omapM

I want to keep my brainspace to remember things more interesting than names for various flavours of the same concept.

3 Likes

The problem I see here is that we historically have not had a great track record with typeclasses that generalise data structures because it’s really difficult to do so that and ensure that non-specialised polymorphic functions retain predictable performance over all lawful instances. The most prominent example of this is Foldable, and its different performance characteristics for different instances. Whereas the more “control”-ish abstractions like Applicative and Monad usually behave somewhat predictably in practice, though of course there are edge cases like the different cost of chained binds in naive free monads.

This makes me favour abstracting over control structures rather than over data structures in typeclasses, which I think also informs my preference for adding semigroupoids classes to the hierarchy while not really believing in mono-traversable classes. A function like Applicative f => (Char -> f Char) -> Text -> f Text interfaces well with the lens library and with any other Applicative people might want to bring to it. And because it’s a standalone binding its performance characteristics can be documented at the definition site, it can specialise better, etc.

2 Likes

I don’t disagree in practice, its a thorny problem and the current state of things makes a very reasonable trade-off, if you stick to the usual lazy Haskell that completely abstracts away the runtime. I wouldn’t throw away that benefit for nothing.

But that trade-off comes at a steeper cost if you actually do want to interact with it (and I do). For example, Applicative and Monad and Traversable get a lot more complicated when dealing with memory, because of the need to allocate new memory, or handle types with different memory layouts. In this memory world, I don’t necessarily have access to Applicative or lenses.

So its not that I disagree, but am trying to find ways to open up classes are more useful when dealing with memory. The GHC runtime is nice, but saying that it runs in the browser is being kind, its too big, and that’s not going to change any time soon. I find more use with monofunctor and friends because it grants me everything that I want from functor, while obeying our restriction on changing the memory layout - which is just like a slightly stricter version of functor’s restriction preventing fmap from altering the structure - memory aware functors only can allow mapping between data types that can fit in the memory layout. This is why abstracting the runtime is so important to regular Haskell - since everything is a pointer, and the runtime allocates everything, everything fits in the same data slot, and functors are much easier to build.

The problem is, it makes functors useless outside of that scope, rendering most of Haskell unavailable by accident - you are locked into the managed runtime, and the lack of investment in low-level support is so bad that it ends up being a sort of learned helplessness in that nobody can write any low-level tools, because there are no low-level tools. Even my own memory monofunctor classes actually diverge because of their mention of allocators, making them not the same as regular monofunctors or functors.

In some important ways, unifying monofunctor and functor is a precursor step in placing memory functors alongside them (at least, theoretically). It would be nice to avoid repeating the same code in multiple places, and to ease the promotion and lifting of memory structures - think of how ByteString has been through the wringer to make it efficient, and imagine you could make that kind of memory support first class in general.

But I’ll admit, I think you are probably right that they shouldn’t be unified in general for performance and ergonomic reasons, even as I feel strongly that the connection shouldn’t be ignored, either. I do like to explore hard problems, and I am still pleased with the output of this experiment.

Ah, we are opposites :slight_smile: I have a large vocabulary but trouble reading acronyms and abbreviations, so I personally prefer clearly distinct terms (I dislike operators for similar reasons) even if it is more verbose. Though, I must say I do like the consistency of mapF if we were going this route.

Sometimes I wish Haskell had module functors and stuff just so I could surface different named interfaces for the same module - then I could surface ‘visit’ to beginner Haskellers, and leave mapA0 for the pros.

2 Likes

I guess people’s brains are different :slight_smile:

I know that in my case, if someone had told me “you know that traverse is just an effectful map, right ?”, it would have saved me some headaches (that’s why teachers are so necessary !)

Another example : the massive misunderstanding around the return function. This case is even worse because it has the same name as “return” in C. If I were to teach monads I would say “think of it as if it was called idM” : it’s the identity function with no side effects. All of the sudden, the confusion disappears, as well as every expectations about return one can have when they come from imperative programming.

My belief is that if from the begining we give similar names to similar things (id and idM), we can avoid oceans of confusion afterwards.

3 Likes

This is why I always line up the types of the various type classes vertically when teaching a new Haskeller :grin: there’s a website that does this but i can never remember the name so google always fails me.

1 Like

Yeah, naming can really help with understanding, and mapA would be a massive improvement over traverse. I’ve never thought of idM before. Interesting idea! (idA probably makes more sense though, given that it doesn’t actually need Monad.)

Ah yes, that’s true! I did not think of this.

In my mind, pure is idAand return is idM. But since return has no reason to exist at all, I agree with you.

1 Like