9

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.

Mike Izbicki
  • 6,286
  • 1
  • 23
  • 53
  • 6
    Can you describe more about the structure you have, and what in particular causes it to fail the fusion law for `fmap`? – luqui Jun 10 '13 at 23:35
  • 2
    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 Jun 10 '13 at 23:47
  • @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 Jun 11 '13 at 00:36
  • Show us the code if you want an informed answer – Gabriella Gonzalez Jun 11 '13 at 02:42
  • 6
    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 Jun 11 '13 at 04:40
  • small addendum: my previous comment is assuming that your normal distribution is parametric WRT the data. If you restrict the allowed types such that any function `f` is monotonic, then you would have a valid (restricted) Functor and Monad. – John L Jun 11 '13 at 04:50
  • I'm trying to stay away from the specific example of a normal distribution, and just trying to understand the basic concept. I had forgotten that `unit`/`join` define a monoid, and I just have to think of different categories. I think this is the intuition I was looking for. – Mike Izbicki Jun 11 '13 at 05:48
  • @JohnL: that would probably be the category of affine spaces (over R?). – n. m. could be an AI Jun 11 '13 at 06:05
  • 3
    Your normal-distribution application sounds quite similar to what I tried as [an uncertainty-propagation type](https://github.com/leftaroundabout/uncertainly-haskell/blob/master/Data/Uncertain.hs). 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 Jun 11 '13 at 13:56

1 Answers1

3

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
Dan Burton
  • 53,238
  • 27
  • 117
  • 198