• Choose a category
• All
• Classic-Fiction

ghci> [1..50] >>= (\x -> guard ('7' `elem` show x) >> return x)

[7,17,27,37,47]

The result here is the same as the result of our previous list comprehension. How does guard achieve this? Let’s first see how guard functions in conjunction with >>:

ghci> guard (5 > 2) >> return "cool" :: [String]

["cool"]

ghci> guard (1 > 2) >> return "cool" :: [String]

[]

If guard succeeds, the result contained within it is an empty tuple. So then we use >> to ignore that empty tuple and present something else as the result. However, if guard fails, then so will the return later on, because feeding an empty list to a function with >>= always results in an empty list. guard basically says, “If this Boolean is False, then produce a failure right here. Otherwise, make a successful value that has a dummy result of () inside it.” All this does is to allow the computation to continue.

Here’s the previous example rewritten in do notation:

sevensOnly :: [Int]

sevensOnly = do

x <- [1..50]

guard ('7' `elem` show x)

return x

Had we forgotten to present x as the final result by using return, the resulting list would just be a list of empty tuples. Here’s this again in the form of a list comprehension:

ghci> [ x | x <- [1..50], '7' `elem` show x ]

[7,17,27,37,47]

So filtering in list comprehensions is the same as using guard.

A Knight's Quest

Here’s a problem that really lends itself to being solved with nondeterminism. Say we have a chessboard and only one knight piece on it. We want to find out if the knight can reach a certain position in three moves. We’ll just use a pair of numbers to represent the knight’s position on the chessboard. The first number will determine the column he is in, and the second number will determine the row.

Let’s make a type synonym for the knight’s current position on the chessboard:

type KnightPos = (Int, Int)

Now suppose that the knight starts at (6, 2). Can he get to (6, 1) in exactly three moves? What’s the best move to make next from his current position? I know—how about all of them! We have nondeterminism at our disposal, so instead of picking one move, let’s pick all of them at once. Here is a function that takes the knight’s position and returns all of his next moves:

moveKnight :: KnightPos -> [KnightPos]

moveKnight (c,r) = do

(c', r') <- [(c+2,r-1),(c+2,r+1),(c-2,r-1),(c-2,r+1)

,(c+1,r-2),(c+1,r+2),(c-1,r-2),(c-1,r+2)

]

guard (c' `elem` [1..8] && r' `elem` [1..8])

return (c', r')

The knight can always take one step horizontally or vertically and two steps horizontally or vertically, but his movement must be both horizontal and vertical. (c', r') takes on every value from the list of movements and then guard makes sure that the new move, (c', r'), is still on the board. If it’s not, it produces an empty list, which causes a failure and return (c', r') isn’t carried out for that position.

This function can also be written without the use of lists as monads. Here is how to write it using filter:

moveKnight :: KnightPos -> [KnightPos]

moveKnight (c, r) = filter onBoard

[(c+2,r-1),(c+2,r+1),(c-2,r-1),(c-2,r+1)

,(c+1,r-2),(c+1,r+2),(c-1,r-2),(c-1,r+2)

]

where onBoard (c, r) = c `elem` [1..8] && r `elem` [1..8]

Both of these versions do the same thing, so pick the one that looks nicer to you. Let’s give it a whirl:

ghci> moveKnight (6, 2)

[(8,1),(8,3),(4,1),(4,3),(7,4),(5,4)]

ghci> moveKnight (8, 1)

[(6,2),(7,3)]

Works like a charm! We take one position, and we just carry out all the possible moves at once, so to speak.

So now that we have a nondeterministic next position, we just use >>= to feed it to moveKnight. Here’s a function that takes a position and returns all the positions that you can reach from it in three moves:

in3 :: KnightPos -> [KnightPos]

in3 start = do

first <- moveKnight start

second <- moveKnight first

moveKnight second

If you pass it (6, 2), the resulting list is quite big. This is because if there are several ways to reach some position in three moves, the move crops up in the list several times.

Here