First experience with monads (Haskell)

Question

I apologize for the subject being unclear. I'm doing Haskell 99 as a beginner, and have encountered the concept of monad first time in my life in the solution to 67A. The part of the problem I'm struggling with is to define a function stringToTree that translates sequences like a(b,c) to a Tree: Branch a (Branch b Empty Empty) (Branch c Empty Empty).

I have tried several "soft" introductions to monads, and failed like many others. I hope by understanding this solution will finally lead me in-door, so I decided to give it a shot here.

Questions

1. Would anyone briefly explain what the function stringToTree :: (Monad m) => String -> m (Tree Char) defined in the solution? To make this question self-contained, I copied the code from there

stringToTree :: (Monad m) => String -> m (Tree Char)
stringToTree "" = return Empty
stringToTree [x] = return $ Branch x Empty Empty
stringToTree str = tfs str >>= \ ("", t) -> return t
 where tfs a@(x:xs) | x == ',' || x == ')' = return (a, Empty)
 tfs (x:y:xs)
 | y == ',' || y == ')' = return (y:xs, Branch x Empty Empty)
 | y == '(' = do (',':xs', l) <- tfs xs
 (')':xs'', r) <- tfs xs'
 return $ (xs'', Branch x l r)
 tfs _ = fail "bad parse"

2. Why is monad useful here? I hope to see how monads largely reduce the difficulties, of course only after one understands it, while defining this function.

• luqui: It looks like they are mainly using Monad for fail (which is being moved to its own class anyhow). My personal preference would be to use the signature stringToTree :: String -> Maybe (Tree Char) which I find more informative in its concreteness. Thankfully Maybe is a monad so there is no change to the code necessary.
• chepner: @luqui Is fail even meant to be used explicitly? I thought it was primarily use in desugaring do blocks to handle pattern-match failures. Are Except (and/or Lift?) preferred for reporting errors?
• leftaroundabout: This is a bad example for monads. fail isn't actually in the monad class anymore. The correct class-constrained signature would be Alternative m => String -> m (Tree Char) (but then you need to either turn on the -XApplicativeDo extension or reformulate the do block to applicative operators yourself). But I agree with Luke that concrete Maybe makes more sense as the result monad.

Answer 1

In short, the definition lets the caller choose which monad to use. This lets us customize how we deal with failure. For example, we can use Maybe:

>>> stringToTree "" :: Maybe (Tree Char)
Just Empty
>>> stringToTree "9 +" :: Maybe (Tree Char)
Nothing

or []:

>>> stringToTree "" :: [Tree Char]
[Empty]
>>> stringToTree "9 +" :: [Tree Char]
[]

The code itself makes no assumptions about which monad is used; it only uses >>=, return, and fail for working with the results of recursive calls.

Making the type String -> Tree Char would indicate that failure simply cannot happen; every string has to produce a valid Tree Char value (or we raise a runtime error, which is something you should strive to avoid in Haskell).

Note, though, that not all monads provide a definition of fail that avoids runtime errors.

>>> stringToTree "" :: Either () (Tree Char)
Right Empty
>>> stringToTree "9 +" :: Either () (Tree Char)
*** Exception: bad parse

• Student: The answer is .. still overwhelming. I'm actually following this post. Maybe I should get back after I finish reading the 14th chapter of "Real World Haskell". That being said, at least I understood something in your answer: the use of monads here is to return an error if needed.
• Student: Wait.. probably not exactly. I remembered doing lots of exercise where I included a function e.g. factorial :: Int -> Int and something like factorial (-1) = error "input number should be positive" works! I did not use any monads here..
• chepner: error produces a run-time error, rather than signaling in your code that the operation failed. We call a function that can raise a run-time error a partial function, since it isn't really defined for all its arguments; factorial (-1) isn't defined, since it doesn't actually return an Int. factorial' :: Int -> Maybe Int, however, can be defined for all Int values; e.g., factorial' 5 == Just 120, and factorial' (-1) == Nothing. This forces you, the programmer to acknowledge and deal with possible errors, rather than letting your program fail when run.

Answer 2

Why monads are useful? Some broader context.

Monads are a unification of several things that traditionally have been handled by different language mechanisms. Among them are

• Sequencing (like in IO or State)

• Non-determinism (like in the list monad)

• Failure and exceptions (like in Maybe)

• Saving and resuming computations (the Cont monad, which you will encounter in the future)

• Atomic transactions (the STM monad)

• Parsing (Parsec and its relatives)

By "unification" I mean the kind of thing that Newton did when he unified the laws of physics for things on Earth and things in the sky, or when Maxwell unified electricity and magnetism into the electromagnetic field; its a deeper underlying theory which yields all of the above as special cases and shows how you can create new things along the same lines.

In monads the type of the "bind" function (>>=) is the central equation in the theory; it describes how one step in the computation can be daisy-chained on to the next. return is the primitive null step. This is something you get used to in Haskell; everything has some kind of zero or null or identity value. fail is a step that doesn't work, which (as @chepner says in a comment elsewhere) is needed for partial functions.

• Student: Thank you so much! I am very excited to get there (to be able to fully understand and appreciate) soon.