How is `join` implemented in Maybe/List monad?

Question

join can be defined implemented in terms of >>=:

join :: Monad m => m (m a) -> m a
join m = m >>= id

Specifically, how is it implemented in a Maybe and a List monad?

Is it in Maybe monad:

join Nothing = Nothing
join (Just (Just x)) = Just x

and in List monad:

join [] = []
join [[xs]] = [xs]

?

Thanks.

Exactly the sam way, with `m >>= id`. – Willem Van Onsem Jul 26 '19 at 11:21 — Willem Van Onsem, Jul 26 '19 at 11:21

score 5 · Answer 1 · answered Jul 26 '19 at 11:27

join is implemented exactly once, and it works for all types that are Monads.

The very point of the Monad abstraction is to enable working on different types in the same way. Once you provide >>= (and return) for your type, and make sure they follow the Monad laws, any code that is generic enough to only use those operations will work on your type correctly.

score 4 · Answer 2 · answered Jul 26 '19 at 13:49

join is just a regular function, implemented in terms of the preexisting (>>=) function. You don't have to worry about which monad is used; (>>=) takes care of that.

Conversely, Monad could have been defined in a way closer to its mathematical definition:

class Monad' m where
    return :: a -> m a
    join :: m (m a) -> m a

with

(>>=) :: Monad' m => m a -> (a -> m b) -> m b
x >>= f = join (fmap f x)

as the regular function. Then the list-specific definition of join would just be concat :: [[a]] -> [a]:

instance Monad' [] where
    return x = [x]
    join = concat

[BTW](https://ryanglscott.github.io/2018/03/04/how-quantifiedconstraints-can-let-us-put-join-back-in-monad/). — Will Ness, Jul 26 '19 at 14:11

Willem Van Onsem · Answer 3 · 2019-07-26T14:16:38.317

3

join is just implemented as [src]:

join              :: (Monad m) => m (m a) -> m a
join x            =  x >>= id

If we take a look at the monad instances of [] [src] and Maybe [src], we see:

instance Monad []  where
    {-# INLINE (>>=) #-}
    xs >>= f             = [y | x <- xs, y <- f x]
    {-# INLINE (>>) #-}
    (>>) = (*>)
    {-# INLINE fail #-}
    fail _               = []

instance  Monad Maybe  where
    (Just x) >>= k      = k x
    Nothing  >>= _      = Nothing

    (>>) = (*>)

    fail _              = Nothing

So that means that for lists, join is equivalent to:

-- for lists
   join xs
-> xs >>= id
-> [ y | x <- xs, y <- id x ]
-> concatMap id xs
-> concat xs

so for lists, the equivalent implementation is:

join_list :: [[a]] -> [a]
join_list = concat

For Maybe we can do case-analysis: the input is a Maybe (Maybe a) so there are basically three possibilities here:

-- (1)
   join Nothing
-> Nothing >>= id
-> Nothing

-- (2)
   join (Just Nothing)
-> Just Nothing >>= id
-> id Nothing
-> Nothing

-- (3)
   join (Just (Just x))
-> Just (Just x) >>= id
-> id (Just x)
-> Just x

So that means that for Maybes the equivalent implementation is:

join_maybe :: Maybe (Maybe a) -> Maybe a
join_maybe (Just x) = x
join_maybe Nothing = Nothing

join is thus not reimplemented for list or Maybe monads, it simply uses the implementation for (>>=) for lists and Maybes, and since these differ, the behavior of join is of course different.

edited Jul 26 '19 at 14:16

answered Jul 26 '19 at 11:30

Willem Van Onsem

443,496
30
428
555

@join: well it is not implemented per monad instance. The definition is each time the same. It is the ad-hoc polymorphism of `(>>)` that here ensures the behaviour is different. – Willem Van Onsem Jul 26 '19 at 14:15
[someone was *wrong* on the internets](https://xkcd.com/386/). all's better now. :) – Will Ness Jul 26 '19 at 14:17
@WillNess: and the best way to get a correct answer, is giving a wrong answer, not asking a question :) – Willem Van Onsem Jul 26 '19 at 14:18
id has type of id :: a -> a, how can it be used in x >>= id ? (>>=) requires a type of (a -> m b), doesn't it ? – user1461328 Sep 27 '19 at 03:24
@user1461328: `id` has type `a -> a`, so it can for example take as specific type `Maybe Int -> Maybe Int`, and thus then it can typecheck when using it with `>>=`. – Willem Van Onsem Sep 27 '19 at 05:35
@WillemVanOnsem: `Maybe Int -> Maybe Int` is still basically`a -> a`, not `a -> m a`. Could you please explain how this is applied to `Nothing `, like `join Nothing` ? – user1461328 Sep 30 '19 at 02:23
@user1461328: it is, note that it is `a -> m b`, and thus `id :: c -> c` (note that the variables are different ones, so we better do not use `a` twice) can unfiy with `a ~ Maybe Int`, `m ~ Maybe` and `b ~ Int`. – Willem Van Onsem Sep 30 '19 at 05:54
@user1461328: it is key that it is a `b` in `a -> m b`, that thus means that `a` can be monadic, and `m b` as well. – Willem Van Onsem Sep 30 '19 at 06:03
@WillemVanOnsem, thanks a lot for answering my stupid questions. I think I got your point now. – user1461328 Oct 03 '19 at 09:00

How is `join` implemented in Maybe/List monad?

3 Answers3