• Choose a category
• All
• Classic-Fiction

By Root 504 0

doing a normal foldl, we do a foldM. The result of that foldM should be a Maybe value that contains a list (that’s our final stack), and that list should have only one value. We use a do expression to get that value, and we call it result. In case the foldM returns a Nothing, the whole thing will be a Nothing, because that’s how Maybe works. Also notice that we pattern match in the do expression, so if the list has more than one value or none at all, the pattern match fails, and a Nothing is produced. In the last line, we just call return result to present the result of the RPN calculation as the result of the final Maybe value.

Let’s give it a shot:

ghci> solveRPN "1 2 * 4 +"

Just 6.0

ghci> solveRPN "1 2 * 4 + 5 *"

Just 30.0

ghci> solveRPN "1 2 * 4"

Nothing ghci> solveRPN "1 8 wharglbllargh"

Nothing

The first failure happens because the final stack isn’t a list with one element in it, so the pattern matching in the do expression fails. The second failure happens because readMaybe returns a Nothing.

Composing Monadic Functions

When we were talking about the monad laws in Chapter 13, you learned that the <=< function is just like composition, but instead of working for normal functions like a -> b, it works for monadic functions like a -> m b. Here is an example:

ghci> let f = (+1) . (*100)

ghci> f 4

401

ghci> let g = (\x -> return (x+1)) <=< (\x -> return (x*100))

ghci> Just 4 >>= g

Just 401

In this example, we first composed two normal functions, applied the resulting function to 4, and then composed two monadic functions and fed Just 4 to the resulting function with >>=.

If you have a bunch of functions in a list, you can compose them all into one big function just by using id as the starting accumulator and the . function as the binary function. Here’s an example:

ghci> let f = foldr (.) id [(+1),(*100),(+1)]

ghci> f 1

201

The function f takes a number and then adds 1 to it, multiplies the result by 100, and then adds 1 to that.

We can compose monadic functions in the same way, but instead of normal composition, we use <=<, and instead of id, we use return. We don’t need to use a foldM over a foldr or anything like that, because the <=< function makes sure that composition happens in a monadic fashion.

When you were introduced to the list monad in Chapter 13, we used it to figure out if a knight can go from one position on a chessboard to another in exactly three moves. We created a function called moveKnight, which takes the knight’s position on the board and returns all the possible moves that he can make next. Then, to generate all the possible positions that he can have after taking three moves, we made the following function:

in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight

And to check if he can go from start to end in three moves, we did the following:

canReachIn3 :: KnightPos -> KnightPos -> Bool

canReachIn3 start end = end `elem` in3 start

Using monadic function composition, we can make a function like in3, except instead of generating all the positions that the knight can have after making three moves, we can do it for an arbitrary number of moves. If you look at in3, you’ll see that we used our moveKnight three times, and each time, we used >>= to feed it all the possible previous positions. So now, let’s make it more general. Here’s how:

import Data.List

inMany :: Int -> KnightPos -> [KnightPos]

inMany x start = return start >>= foldr (<=<) return (replicate x moveKnight)

First, we use replicate to make a list that contains x copies of the function moveKnight. Then we monadically compose all those functions into one, which gives us a function that takes a starting position and nondeterministically moves the knight x times. Then we just make the starting position into a singleton list with return and feed it to the function.

Now, we can change our canReachIn3 function to be more general as well:

canReachIn :: Int -> KnightPos -> KnightPos -> Bool

canReachIn x start end = end `elem` inMany x start

Making Monads

In this section, we’re going