CODEWITHSUNDEEP
haskellmonads
meto
meto

Reputation: 3719

Define bind without join for the list monad in Haskell

I understand the definition of >>= in term of join

xs >>= f = join (fmap f xs)

which also tells us that fmap + join yields >>=

I was wondering if for the List monad it's possible to define without join, as we do for example for Maybe:

>>= m f = case m of
    Nothing -> Nothing
    Just x  -> f x

Upvotes: 1

Views: 195

Answers (1)

K. A. Buhr
K. A. Buhr

Reputation: 50829

Sure. The actual definition in GHC/Base.hs is in terms of the equivalent list comprehension:

instance Monad []  where
    xs >>= f             = [y | x <- xs, y <- f x]

Alternatively, you could try the following method of working it out from scratch from the type:

(>>=) :: [a] -> (a -> [b]) -> [b]

We need to handle two cases:

[] >>= f = ???
(x:xs) >>= f = ???

The first is easy. We have no elements of type a, so we can't apply f. The only thing we can do is return an empty list:

[] >>= f = []

For the second, x is a value of type a, so we can apply f giving us a value of f x of type [b]. That's the beginning of our list, and we can concatenate it with the rest of the list generated by a recursive call:

(x:xs) >>= f = f x ++ (xs >>= f)

Upvotes: 6

Related Questions