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.

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

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.