Haskell: Understanding the bind operator (>>=) for Monads

Question

I have the following function:

parse :: String -> Maybe Token

And I am trying to implement the following function:

maketokenlist :: String -> Maybe [Token]

The function returns Nothing if there is a token that was not able to be parsed (i.e. parse returns Nothing if the token is not an integer or an arithmetic operator), otherwise it returns a list of Tokens.

As Maybe is an instance of the Monad type class, I have the following approach:

maketokenlist str =  return (words str) >>= parse

I convert the string into a list of individual tokens (e.g. "2 3 +" becomes ["2","3","+"] , and then map the parse function over each string in the list.

Since the Monad instance for lists is defined as:

instance Monad [] where
   return x = [x] 
   xs >>= f = concat (map f xs)
   fail _ = []

However, say that I had the list of strings [2, 3, "+", "a"] and after mapping parse over each element using >>= I get [Just 2, Just 3, Just (+), Nothing], as "a" cannot be parsed. Is there a way to make the function maketokenlist return Nothing using just the >>= operator? Any insights are appreciated.

[2, 3, "+", "a"], This is neither a list, nor any construct that makes any sense in Haskell. A list must be made of a single type like so, [a]. So you could have [2,3] or ["+","a"]. Rethink the problem, and try again. — Michael Litchard
return wraps its argument in a monad, and >>= immediately unwraps it. So return (words str) >>= parse is equivalent to parse (words str). Is there a reason you need to use >>=, instead of, say, maketokenlist str = map parse (words str)? — DarthFennec

Daniel Wagner Daniel Wagner · Accepted Answer · 2019-07-15T21:17:23

If parse :: String -> Maybe Token, then:

traverse parse :: [String] -> Maybe [Token]

This version of traverse (which I have specialized to act on lists as the Traversable instance and Maybe as the Applicative instance) may indeed be implemented using (>>=):

listMaybeTraverse parse [] = pure []
listMaybeTraverse parse (s:ss) =
    parse s >>= \token ->
    listMaybeTraverse parse ss >>= \tokens ->
    pure (token:tokens)

I have chosen the names parse, s, and token to show the correspondence with your planned usage, but of course it will work for any appropriately-typed functions, not just parse.

The instance of Monad for lists does not make an appearance in this code.

Haskell: Understanding the bind operator (>>=) for Monads

1 Answers