Is `data PoE a = Empty | Pair a a` a monad?
functional-programming, haskell, monads
Solution
Apparently, it is not a monad. One of the monad "`join`" laws is
join . join = join . fmap join
Hence, according to the law above, these two outputs should be equal, but they are not.
main :: IO ()
main = do
let x = Pair (Pair (Pair 1 2) Empty) (Pair Empty (Pair 7 8))
print (join . join $ x)
-- output: Pair 1 8
print (join . fmap join $ x)
-- output: Empty
The problem is that
join x = Pair (Pair 1 2) (Pair 7 8)
fmap join x = Pair Empty Empty
Performing an additional `join` on those does not make them equal.
how to find that out systematically?
`join . join` has type `m (m (m a)) -> m (m a)`, so I started with a triple-nested `Pair`-of-`Pair`-of-`Pair`, using numbers `1..8`. That worked fine. Then, I tried to insert some `Empty` inside, and quickly found the counterexample above.
This approach was possible since a `m (m (m Int))` only contains a finite amount of integers inside, and we only have constructors `Pair` and `Empty` to try.
For these checks, I find the `join` law easier to test than, say, associativity of `>>=`.
Problem
This question comes from this answer in example of a functor that is Applicative but not a Monad: It is claimed that the ``` data PoE a = Empty | Pair a a deriving (Functor,Eq) ``` cannot have a monad instance, but I fail to see that with: ``` instance Applicative PoE where pure x = Pair x x Pair f g <*> Pair x y = Pair (f x) (g y) _ <*> _ = Empty instance Monad PoE where Empty >>= _ = Empty Pair x y >>= f = case (f x, f y) of (Pair x' _,Pair _ y') -> Pair x' y' _ -> Empty ``` The actual reason why I believe this to be a monad is that it is isomorphic to `Maybe (Pair a)` with `Pair a = P a a`. They are both monads, both traversables so their composition should form a monad, too. Oh, I just found out not always. Which counter-example failes which monad law? (and how to find that out systematically?) edit: I did not expect such an interest in this question. Now I have to make up my mind if I accept the best example or the best answer to the "systematically" part. Meanwhile, I want to visualize how `join` works for the simpler `Pair a = P a a`: ``` P ________/ \________ / \ P P / \ / \ 1 2 3 4 ``` it always take the outer path, yielding `P 1 4`, more commonly known as a diagonal in a matrix representation. For monad associativy I need three dimensions, a tree visualization works better. Taken from chi's answer, this is the failing example for join, and how I can comprehend it. ``` Pair _________/\_________ / \ Pair Pair /\ /\ / \ / \ Pair Empty Empty Pair /\ /\ 1 2 3 4 ``` Now you do the `join . fmap join` by collapsing the lower levels first, for `join . join` collapse from the root.