Haskell Monad Functions

haskell applicative
haskell state monad
haskell do notation
haskell functor
haskell io monad
monad laws
haskell list monad
maybe monad haskell

I'm going through a Haskell tutorial and am given this piece of code to do with moving a knight in chess:

import Control.Monad

type KnightPos = (Int,Int)

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')

in3 :: KnightPos -> [KnightPos]
in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight

canReachIn3 :: KnightPos -> KnightPos -> Bool
canReachIn3 start end = end `elem` in3 start 

An exercise is to modify the functions so that canReachIn3 tells you what moves you can take to get to the end position if it is possible to get there.

This tutorial has basically no exercises so I'm having trouble with basic stuff like this...I was thinking of changing the return values of all 3 functions to [[KnightPos]] where 1 big list contains a list for every possible ordering of moves. That would probably then involve moveKnight having a [KnightPos] parameter instead of a KnightPos one, which would then defeat the whole point of monads right?

Any help/thoughts would be greatly appreciated, thanks.

It might help to step back from the Monad concept for a bit when thinking about this code, if you find that plain old list operations are more natural for you. So you can rewrite the example code (with a little bit of cleanup for legibility) as:

type KnightPos = (Int,Int)

moveKnight :: KnightPos -> [KnightPos]  
moveKnight (c,r) = filter legal candidates where
    candidates = [(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)]
    legal (c',r') = c' `elem` [1..8] && r' `elem` [1..8]

in3 :: KnightPos -> [KnightPos]
in3 start = concatMap moveKnight (concatMap moveKnight (moveKnight start))

canReachIn3 :: KnightPos -> KnightPos -> Bool
canReachIn3 start end = end `elem` in3 start

The secret sauce is in concatMap. As you probably know already, it's synonymous with >>= in the List monad, but it might be more helpful right now to think of it as mapping a function of type KnightPos -> [KnightPos] over a list [KnightPos] to yield a list of lists [[KnightPos]], and then flattening the result back into a single list.

Okay, so now that we've dispensed with monads for the moment, let's look back at the puzzle... Let's say your initial KnightPos is (4,4), and you want to track all possible sequences of moves from that position. So define another type synonym:

type Sequence = [KnightPos]

Then you'd want moveKnight to operate on these sequences, finding all possible moves from the last position in the sequence:

moveKnight :: Sequence -> [Sequence]

So starting from a sequence [(4,4)], we'd get the list of sequences: [[(4,4), (6,3)], [(4,4), (6,5)], [(4,4), (2,3)], ... ]. Then I think the only change you'd need to make to in3 is to fix its type signature accordingly:

in3 :: Sequence -> [Sequence]

I don't think the actual implementation changes. Finally, you'll want canReachIn3 to look something like:

canReachIn3 :: KnightPos -> KnightPos -> [Sequence]

I'm leaving the implementation detail out here on purpose since I don't want to ruin the puzzle for you entirely, but I'm hoping I've illustrated the point here that there isn't anything particularly "special" about a list, or a list of lists, or whatever. All we've really done is substituted a function of type KnightPos -> [KnightPos] with a new function of type Sequence -> [Sequence] -- pretty much the same shape. So fill in the implementations of each function using whatever style feels natural, and then once you have it working, go back to the monadic style, replacing concatMap with >>= and so on.

Monad, The >> function is used when the function does not need the value produced by the first monadic operator. The precise meaning of binding depends, of course, on  import Control.Monad Monads in Haskell can be thought of as composable computation descriptions.

I would suggest making KnightPos a data structure capable of holding not only the current potion, but also the KnightPos that it came from:

data KnightPos = KnightPos {history :: Maybe KnightPos, position :: (Int,Int) }

You then need to implement the Eq and Show classes, and fix moveKnight so that it returns this structure with its history set appropriately:

moveKnight :: KnightPos -> [KnightPos]  
moveKnight p@KnightPos{position = (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 $ KnightPos (Just p) (c',r') 

Make sure you understand the last line of this function.

The function in3 should now work without modification. I wrote a new function,pathIn3 :: KnightPos -> KnightPos -> [[KinghtPos]] that returns all possible paths from start to end in 3 monadic statements.

Spoiler Alert

pathIn3 :: KnightPos -> KnightPos -> [[KnightPos]] pathIn3 start end = do p <- in3 start guard (p == end) return $ getHistory p

Control.Monad - Hackage, As an applicative functor, it functions similarly. However, applicatives also have the function wrapped. Maybe is an applicative functor in such a way that when we​  A postfix 'M' always stands for a function in the Kleisli category: The monad type constructor m is added to function results (modulo currying) and nowhere else. So, for example, filter :: (a -> Bool) -> [a] -> [a] filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a] A postfix '_' changes the result type from (m a) to (m ()). Thus, for example:

"That would probably then involve moveKnight having a [KnightPos] parameter instead of a KnightPos one..." No, you wouldn't want to do that. Keep the functions as basic as possible.

"...which would then defeat the whole point of monads right?" Well, if you want all orderings of moves, you just don't in every move use the join implied in >>=. You might define a function returning a list of all paths of length n from a given starting point, where we may implement those paths as list of the positions passed, for efficiency reasons in reverse order.

waysFrom :: KnightPos -> Int -> [[KnightPos]]

First for one move (or zero)

waysFrom start 0 = [[start]]
waysFrom start 1 = map (\t -> [t, start]) $ moveKnight start

and then for arbitrary numbers of moves, at which point you can use again use >>= to join the trie-like structure resulting from straightforward recursion to a list of move lists:

waysFrom start n = waysFrom start (n-1) >>= (\w -> [t:w | t<-moveKnight$head w])

there may be a better way to do this, but it wouldn't actually "defeat" the whole point of monads.

A Gentle Introduction to Haskell: About Monads, This post explores how functions in Haskell can be seen as instances of the Functor, Applicative and Monad type classes, with some reflection  monad library. You can think of it as transporting a function from outside the list monad, f, into the list monad in which computations take on multiple values. The monad defined for Maybeis similar to the list monad: the value

I'm reading the tutorial and my solution is a little bit change functions in3 and canReachIn3

in3 :: KnightPos -> [[KnightPos]]
in3 start = do
    first <- moveKnight start
    second <- moveKnight first
    third <- moveKnight second
    return [start, first, second, third]

canReachIn3 :: KnightPos -> KnightPos -> [[KnightPos]]
canReachIn3 start end = filter (elem end) $ in3 start

The result of in3 contains list all possible paths.

A Fistful of Monads, This idea is central to Haskell's IO monad, where an For example, Haskell has several functions for acting on the  The Monadclass defines the basic operations over a monad, a concept from a branch of mathematics known as category theory. From the perspective of a Haskell programmer, however, it is best to think of a monad as an abstract datatypeof actions. Haskell's doexpressions provide a convenient syntax for writing

Haskell functions as functors, applicatives and monads, Or in words: every time you evaluate a function, pass an extra r argument. Within a set of functions the value of this argument stays the same, so it provides a  Looking at the State Monad's wiki, I'm trying to understand the runState and put functions. As I understand runState, it takes a first argument of State, which has a "universe", s, and a value, a.

Monad (functional programming), The >> function is used when the function does not need the value produced by the first monadic operator. The precise meaning of binding depends, of course, on  In Haskell, monads play a central role in the I/O system. It is not essential to understand monads to do I/O in Haskell, but understanding the I/O monad will improve your code and extend your capabilities. For the programmer, monads are useful tools for structuring functional programs. They have three properties that make them especially useful:

Martin's Atelier: Monads in Haskell: ((->) r), These functions are then combined using the bind operator (spelled >>= in Haskell). Since the bind operation combines functions, it can execute them as it sees  A monad is a type class with functions (return, >>=) and laws. To "run" something inside a monad could thus either mean (a) to provide it as argument to return, or (b) to sequence it using >>=. If the monad is of type m a, then in case a) that something must be of type a, to match the type of the return function.

Comments
  • Thanks you gave me enough to let me persist for myself.