It's not a monad, but what is it?

Question

According to the Haskell wikibook, a Monad called m is a Functor with two additional operations:

unit :: a -> m a
join :: m (m a) -> m a

That's nice, but I have something slightly different. Glossing over the gory details, I have a type that has good unit and join functions, but its fmap is not well behaved (fmap g . fmap f is not necessarily fmap (g.f)). Because of this, it cannot be made an instance of Monad. Nonetheless, I'd like to give it as much generic functionality as possible.

So my question is, what category theoretic structures are similar to monads in that they have a unit and join?

I realize that on some level, the above question is ill-defined. For monads the unit and join definitions only make sense in terms of the fmap definition. Without fmap, you can't define any of the monad laws, so any definitions of unit/join would be equally "valid." So I'm looking for functions other than fmap that it might make sense to define some "not-monad" laws on these unit and join functions.

Can you describe more about the structure you have, and what in particular causes it to fail the fusion law for fmap? — luqui
I suppose you specifically "tweaked" fmap in a way so that join fulfills the 2nd monad law? Normally, you almost always get fmap g . fmap f ≡ fmap $ f.g just automatically. — leftaroundabout
@luqui I'm more interested in general than just this specific case, but it's a normal distribution. If you think about fmap as applying a function to every point in a distribution, then fmap only obeys the Functor laws for addition and multiplication. unit is training on a single data point, and join is merging a "normal distribution of normal distributions" into a single normal distribution. Obviously, this requires some constraints on the parameters, so it can't be done at all using the Base type classes and I'be been using ConstraintKinds to play around with it. — Mike Izbicki
As is well-known by now, "monads are just monoids in the category of endofunctors". So you're looking for a monoid, just in a different category. I'm not sure what category would correspond to normal distributions, but I'm a bit suspicious. My intuition (which is frequently wrong FWIW) is that the only structure imposed by a normal distribution is isomorphic to a List. — John L
Your normal-distribution application sounds quite similar to what I tried as an uncertainty-propagation type. I think I checked it does obey the functor law, if you obtain the result width with differentiation laws! Certainly when the distribution widths remain small enough that you can neglect higher-order Taylor summands; otherwise the whole approach doesn't seem very useful anyway. — leftaroundabout

Dan Burton Dan Burton · Accepted Answer · 2013-06-27T17:11:13

Well here's one law you should have with just unit and join. Given x :: m a,

join (unit x) = x

To show that this didn't just come from nowhere, let's start with an existing monad law:

return x >>= f = f x

Given that m >>= f = join (fmap f m)

join (fmap f (return x)) = f x

Select f = id

join (fmap id (return x)) = id x

Use the functor law that fmap id = id

join (id (return x)) = id x

Use the obvious id a = a

join (return x) = x

It's not a monad, but what is it?

1 Answers