How to define a Monad instance to types with multiple values?

Question

By multiple values I mean something like so: ``` data Foo a = Bar a | Baz a a ``` I can't think of a clear way to define `>>=` for `Baz`: ``` instance Monad Foo where Bar x >>= f = f x -- Great, that works perfectly! Baz x y >>= f = ??? -- What the heck do I even put here? ```

Accepted Answer

Perhaps:

```
frst (Bar a) = a
frst (Baz a a') = a

scnd (Bar a) = a
scnd (Baz a a') = a'

instance Monad Foo where
    return = Bar
    Bar x >>= f = f x
    Baz x y >>= f = Baz (frst (f x)) (scnd (f y))
```

This definition is inspired by the definition of `(>>=)` for `(Bool ->)`. Ask me if it's not clear how.

Let's check the laws. The "`return` is unit" laws are pretty straightforward:

```
  return x >>= f
= Bar x >>= f
= f x

m >>= return
= case m of
      Bar x -> return x
      Baz x y -> Baz (frst (return x)) (scnd (return y))
= case m of
      Bar x -> Bar x
      Baz x y -> Baz x y
= m
```

I believe I've convinced myself of the "`(>>=)` is associative" law, too, but I'm sure this proof is completely unreadable to anybody else... I encourage you to try proving it yourself, and refer to my calculations as a cheat-sheet if you get stuck.

```
  m >>= (\v -> f v >>= g)
= case m of
      Bar x -> (\v -> f v >>= g) x
      Baz x y -> Baz (frst ((\v -> f v >>= g) x))
                     (scnd ((\v -> f v >>= g) y))
= case m of
      Bar x -> f x >>= g
      Baz x y -> Baz (frst (f x >>= g)) (scnd (f y >>= g))
= case m of
      Bar x -> case f x of
          Bar y -> g y
          Baz a b -> Baz (frst (g a)) (scnd (g b))
      Baz x y -> Baz (frst l) (scnd r) where
          l = case f x of
                  Bar a -> g a
                  Baz a b -> Baz (frst (g a)) (scnd (g b))
          r = case f y of
                  Bar a -> g a
                  Baz a b -> Baz (frst (g a)) (scnd (g b))
= case m of
      Bar x -> case f x of
          Bar y -> g y
          Baz a b -> Baz (frst (g a)) (scnd (g b))
      Baz x y -> Baz (frst (g (frst (f x))))
                     (scnd (g (scnd (f y))))
= case m of
      Bar a -> case f a of
          Bar x -> g x
          Baz x y -> Baz (frst (g x)) (scnd (g y))
      Baz a b -> case Baz (frst (f a)) (scnd (f b)) of
          Bar x -> g x
          Baz x y -> Baz (frst (g x)) (scnd (g y))
= case v of
      Bar x -> g x
      Baz x y -> Baz (frst (g x)) (scnd (g y))
  where v = case m of
                Bar a -> f a
                Baz a b -> Baz (frst (f a)) (scnd (f b))
= case m >>= f of
      Bar x -> g x
      Baz x y -> Baz (frst (g x)) (scnd (g y))
= (m >>= f) >>= g
```

edit Okay, I decided to write a short explanation of how this is inspired by `(Bool ->)` even though nobody asked. So, recall:

```
instance Monad (e ->) where
    m >>= f = \e -> f (m e) e
```

Now we're going to define

```
data Pair a = Pair a a
```

and observe that `Bool -> a` and `Pair a` are very similar:

```
to :: Pair a -> (Bool -> a)
to (Pair false true) = \bool -> case bool of
    False -> false
    True  -> true

from :: (Bool -> a) -> Pair a
from f = Pair (f False) (f True)
```

It turns out that `from` and `to` are an isomorphism. In other words: you can alternately think of `Bool -> a` as a "two-element container". Well, what happens if we try to translate the `(e ->)` instance for `Monad` into the `Pair` type? It certainly ought to be possible, since they're isomorphic. In fact, let's start with the isomorphism:

```
instance Monad Pair where
    return x = from (return x)
    m >>= f = from (to m >>= to . f)
```

Now we can "just turn the crank":

```
  return x
= from (return x)
= from (\e -> x)
= Pair ((\e -> x) False) ((\e -> x) True)
= Pair x x
```

and:

```
  m@(Pair false true) >>= f
= from (to m >>= to . f)
= from (\e -> (to . f) (to m e) e)
= from (\e -> to (f (to m e)) e)
= Pair (g False) (g True) where
      g = \e -> to (f (to m e)) e
= Pair (to (f (to m False)) False) (to (f (to m True)) True)
= Pair (case f (to m False) of Pair false true -> false)
       (case f (to m True ) of Pair false true -> true )
= Pair (case f false of Pair false true -> false)
       (case f true  of Pair false true -> true )
```

So we can now rewrite the instance without relying on `(Bool ->)` by just copying and pasting the first and last line of the above calculations:

```
frstPair (Pair false true) = false
scndPair (Pair false true) = true

instance Monad Pair where
    return x = Pair x x
    Pair false true >>= f = Pair (frstPair (f false)) (scndPair (f true))
```

Hopefully you can recognize how similar this is to the definition of `(>>=)` I gave above for `Foo`.

edit 2 Another (different!) monad for this is possible. Check out the behavior of the isomorphic type from base:

```
type Foo = Product Identity Maybe
```

See the docs for `Product`. Written without the isomorphism, it would be:

```
instance Monad Foo where
    return x = Baz x x
    Bar x >>= f = Bar (frst (f x))
    Baz x y >>= f = case f y of
        Bar a -> Bar (frst (f x))
        Baz a b -> Baz (frst (f x)) b
```

In a sense, my original proposal "expands" the number of results as you add more monadic actions -- starting with a `Bar` in `return` and converting `Bar`s irrevocably to `Baz`s in the bind -- while this instance "contracts" the number of results possible as you add more monadic actions -- s…

How to define a Monad instance to types with multiple values?

Solution

Problem

Related problems