porges

Dan Piponi’s latest post “Beyond Monads” has prompted some wonderment (and forehead-slapping). For example:

How did we all miss that before?

—Peaker

The answer (of course!) is that while we might have, they didn’t. For example, Edward Kmett’s category-extras package has had Control.Monad.Indexed available for use in Haskell since early last year, while the concept for its implementation in Haskell has been around since at least 2005 (see the paper “Monadic Augment and Generalised Short Cut Fusion”). Needless to say, Oleg has been there too.

For me, this prompted a vaguely-related revelation. Say that we have a Category class:

class Category (⤳) where
	id ∷ a ⤳ a
	(∘) ∷ (b ⤳ c) → (a ⤳ b) → (a ⤳ c)

I had recently been wondering how categories other than (→), such as graphs (and even the trivial category) fit into this model. Now that I have figured it out, the answer is simple; it is a matter of arity. Graphs and other datastructure-related categories don’t have the extra type arguments (unless you’re working in a dependently-typed language), and so can’t fit into this. What we want to do is fake the extra arguments, by having some extra ones that we can just ignore (the name, FF, is short for FakeFake, i.e. two fake arguments).

newtype FF f a b = FF { unFF :: f }

Now we can define the trivial category!

class Category (FF ()) where
	id = FF ()
	f ∘ g = FF ()

Viewed in this light, it is obvious why (as Dan notes in the original post) Monoids give rise to Monads and Categories give rise to ParametrizedMonads, as we have:

class Monoid m ⇒ Category (FF m) where
	id = FF mempty
	(FF f) ∘ (FF g) = FF (mappend f g)

Next, we want to write implementations for all our old Monads in the new PMonad class. We might do it like this (with a new newtype for the different arguments of this datatype, RealFakeFakeReal):

newtype RFFR f x y a = RFFR { unRFFR ∷ (f a) }
 
class PMonad m where
	(>>=) ∷ m s1 s2 a → (a → m s2 s3 b) → m s1 s3 b
	return ∷ a → m s s a
 
instance (Old.Monad m) ⇒ PMonad (RFFR m) where
	(RFFR x) >>= f = RFFR (x Old.>>= unRFFR ∘ f)
	return x = RFFR (Old.return x)

There is a big issue that this highlights. It is hard to work with types of different arities in Haskell. (This is noted in the ‘quantified contexts’ proposal.)

As an example, since we now know that every Monoid is a Category, we might think to drop Monoids and just use Categories everywhere (I should note that this is actually a silly idea !). Unfortunately, we can’t just do this as we’ll have to use FF wrappers/unwrappers everywhere:

x = unFF $ FF [1,2,3] ∘ FF [4,5,6]

I have not yet found a workaround for this. Help would be nice