-9

Monads in category theory is defined by triples T, unit, flat⟩.

class Monad t where
  map :: (a -> b) -> (t a -> t b) -- functorial action
  unit :: a -> t a
  flat :: t (t a) -> t a

class KleisliTriple t where
  unit :: a -> t a
  flatMap :: t a -> (a -> t b) -> t b

KleisliTriple flats the structure by the operator: flatMap (or bind in Haskell) that is composition of map and flat.

However, I always think it's much simpler and easier to understand and implement the Monad conept in functional programming to compose functions by flatten the structure with the object such as flatUnit that is composition of unit and flat.

In this case, flatUnit(flatUnit(x)) = flatUnit(x). I actually implemented in this manner in JavaScript, and with flatUnit and map (just a legacy functor operator), all the benefit of Monad seems to be obtained.

So, here's my question.

I have kept looking for documents about the kind of flatUnit formalization in functional programming, but never found it. I understand there's a historical context that Eugenio Moggi who first discovered the relevance of monads in functional programming, and in his paper that happened to be KleisliTriple application, but since Monads are not limited to Kleisli Category and considering the simplicity of flatUnit, to me it's very strange.

Why is that? and what do I miss?

EDIT:code is removed.

1 Answers1

10

In this answer, I won't dwell on flatUnit. As others have pointed out, join . return = id for any monad (it is one of the monad laws), and so there isn't much to talk about it in and of itself. Instead, I will discuss some of the surrounding themes raised in the discussion here.

Quoting a comment:

in other words, functor with a flat structure, it's a monad.

This, I believe, is the heart of the question. A monad need not be a functor with a flat structure, but a functor whose values can be flattened (with join) in a way that follows certain laws ("a monoid in the category of endofunctors", as the saying goes). It isn't required for the flattening to be a lossless operation (i.e. for join to be an isomorphism).

Monads whose join is an isomorphism are called, in category theory parlance, idempotent monads 1. For a Haskell Monad to be idempotent, though, the monadic values must have no extra structure. That means most monads of immediate interest to a programmer won't be idempotent (in fact, I'm having trouble to think of idempotent Haskell Monads that aren't Identity or identity-like). One example already raised in the comments was that of lists:

join [[1,2],[3,4,5]] = [1,2,3,4,5] -- Grouping information discarded

The function/reader monad gives what I'd say is an even more dramatic illustration:

join (+) = \x -> x + x

This recent question gives an interesting illustration involving Maybe. The OP there had a function with signature...

appFunc :: Integer -> Integer -> Bool -> Maybe (Integer,Integer)

... and used it like this...

appFunc <$> u <*> v <*> w

... thus obtaining a Maybe (Maybe (Integer, Integer)) result. The two layers of Maybe correspond to two different ways of failing: if u, v or w are Nothing, we get Nothing; if the three of them are Just-values but appFunc results in Nothing, we get Just Nothing; finally, if everything succeeds we get a Just-value within a Just. Now, it might be the case that we, like the author of that question, didn't care about which layer of Maybe led to the failure; in that case, we would discard that information, either by using join on the result or by rewriting it as u >>= \x -> v >>= \y -> w >>= \b -> appFunc x y b. In any case, the information is there for us to use or discard.


Note 1: In Combining Monads by King and Wadler (one of Wadler's papers about monads), the authors introduce a different, and largely unrelated, meaning for "idempotent monad". In their sense, an idempotent monad is one for which (in applicative notation) f <$> u <*> u = (\x -> f x x) <$> u -- one example would be Maybe.

duplode
  • 33,731
  • 7
  • 79
  • 150
  • I believe an idempotent monad in Wadler's sense can be expressed even more compactly: `u *> u = u`. I don't (yet) have a proof that this is sufficient, but I'm quite confident it follows from the `Applicative` laws. – dfeuer Oct 25 '18 at 16:40
  • Thanks. Firstly, reading your answer, I misunderstood that idempotent monads was what I was talking about, but since it appears to be IdentiyMonad, I think this is not what I mention here. –  Oct 26 '18 at 01:17
  • However, idempotent is the word I will keep using. Identity monad is idempotent for the value, but what I mention here is idempotent for the monadic type, and the monadic value can be changed according to the functors. –  Oct 26 '18 at 01:22
  • @bayesian-study (1) Glass half-empty view: if by "`T` is an idempotent functor" you'd mean "`TT` and `T` are the same", a question arises about what "the same" would mean. If we are working in **Hask**, I think any useful notion of sameness will end up referring to the value level (e.g. "being the same means being isomorphic"). (2) Glass half-full view: if we give up on sameness, I don't think you need to repurpose "idempotent" to express this idea, because "monoid" will do just fine. It seems, "a monad is a monoid in the category of endofunctors" captures the gist of what you're aiming at. – duplode Oct 26 '18 at 02:52
  • @dfeuer I have figured out an almost-proof of that. I say "almost" because it relies on `u *> u = u` and `u <* u = u` being equivalent. This feels like it should be an evident truth, but I'm finding it surprisingly troublesome to properly justify it. Maybe I'm missing something obvious... if you have any suggestions, I'm all ears! – duplode Oct 26 '18 at 20:54
  • If there's a proof, it must involve the `Applicative` composition law, since that's the only one that's not trivial. But no, I don't really know how to do it. – dfeuer Oct 26 '18 at 21:07
  • @duplode Thanks for your comments again, and I would like to ask further. Isn't a free-monad idempotent? According to your mention:"It isn't required for the flattening to be a lossless operation (i.e. for join to be an isomorphism).", join can be designed to be not an isomorpohism, but from my understanding, free-monad includes join(probably isomorphism) already, and any monads are derived from the free-monad by designing a functor that is out of territory of the built-in join. –  Oct 30 '18 at 22:58
  • @bayesian-study Not really. For a counterexample, `Free (Const ())` is `Maybe` (they are isomorphic, and the instances match), whose `join` is not an isomorphism. I feel there is something to your intuition (the `join` of a free monad, in a sense, does as little as necessary -- cf. the answers to [*What are free monads?*](https://stackoverflow.com/q/13352205/2751851)), but it isn't idempotency in that sense. Also note that not all monads are free monads -- cf. [this Haskell Cafe message](https://mail.haskell.org/pipermail/haskell-cafe/2017-January/126026.html). – duplode Oct 31 '18 at 13:04
  • @duplode Thanks. My intuition is, 1. Functors/Monads are Objects that have binary operations between a value and a function: `a * f * f * f.....` where `*` as any binary operator(like wild-card) to be defined. 2. This generalization is is called as Free Functors/Free Monads. –  Oct 31 '18 at 15:18
  • So, I feel something wrong about `join` that should be built-in structure in a free monad should be defines for each cases because all we care about to define the feature of free monad is the "wild-card" part that is the binary operator. –  Oct 31 '18 at 15:23
  • However, like the HaskellCafe post you've introduced, I've heard that the list monad is not a free monad, so which means my intuition: "Monads are Objects that have binary operations between a value and a function: `a * f * f * f.....`" is not even generalization of Monads. This is truly confusing. –  Oct 31 '18 at 15:31
  • 1
    @dfeuer I found a counterexample to the `u *> u = u` conjecture. I wrote a little about it [here](https://duplode.github.io/posts/idempotent-applicatives-parametricity-and-a-puzzle.html) (the actual counterexample is down in the "Something twisted" section). Over at r/haskell, Li-yao Xia also noted [a related example](https://www.reddit.com/r/haskell/comments/b7xsp1/idempotent_applicatives_parametricity_and_a_puzzle/ejvvtln/). – duplode Apr 06 '19 at 17:52
  • That's certainly interesting, but I don't think it disproves my conjecture. You've shown that an idempotent *element* in the weak sense is not necessarily am idempotent element in the strong sense. But `Evil x y *> Evil x y` is not generally `Evil x y`, so `Twisted` is not an idempotent *monad* in the weak sense. – dfeuer Apr 06 '19 at 19:34
  • @dfeuer "But `Evil x y *> Evil x y` is not generally `Evil x y`" -- `Evil x y *> Evil x y ` is `snd <$> fzip (Evil x y, Evil x y)`, which is `snd <$> Evil (x, x) (x, y)`, which is `Evil x y`. (The one that doesn't hold is `Evil x y <* Evil x y = Evil x y`.) – duplode Apr 06 '19 at 19:45
  • Oh, I must've missed something. I'll have to look again. – dfeuer Apr 06 '19 at 19:51