Haskell recursion in 'do' notation

Question

I'm reading this tutorial http://learnyouahaskell.com/a-fistful-of-monads and stumbled upon this definition:

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 = do   
    first <- moveKnight start  
    second <- moveKnight first  
    moveKnight second  

I have a question regarding function in3 (which takes a pair of coordinates (Int,Int) on a chessboard and produces a list of fields [(Int,Int)] reachable from that field in exactly 3 moves of a knight).

Is it possible (and if so - how to do it) to remake that function into
inNMoves :: (Num a) => KnightPos -> a -> [KnightPos]
so that it also takes the number of moves as an argument, instead of being bound to exactly 3 jumps?

Answer 1

As this exercise is about the List Monad, try to not think of what you know about lists, but limit yourself to the structure of monads. So that would be

move :: Monad m => Pos -> m Pos

That is, move takes a Pos and gives you back something that is about Pos things in some monadic context m. (In the case of lists, the "context" being "arbitrary multiplicity + ordering". But try not to think about it).

Also, let's not talk about do here which is only syntactic sugar for using (>>=). For the purposes of this explanation, you are required to know how do translates to expressions using (>>=).

(>>=) has signature m a -> (a -> m b) -> m b. The instance which we need being m Pos -> (Pos -> m Pos) -> m Pos. You see we have instanciated both a and b here to Pos. You also can recognize the middle part (Pos -> m Pos) being move's signature here. So using (>>=) and giving it move as second argument, we can make a function of type m Pos -> m Pos.

moveM :: Monad m => m Pos -> m Pos
moveM mp = mp >>= move

Composition of monad endomorphisms

It is clear that m Pos -> m Pos can be executed in sequence as often as you wish since it is a function from a type to itself (I think that can be called monad endomorphism since the type is a monad).

Let's write a function which does two moves.

move2M :: Monad m => m Pos -> m Pos
move2M mp = moveM (moveM (mp))

Or in pointfree style (thinking only about the transformation, not about the transformated object):

move2M :: Monad m => m Pos -> m Pos
move2M = moveM . moveM

For the general case (number of moves parameterized by an integer n) we just want some number of moveMs connected by the function chaining operator .. So if n is 3, we want moveM . moveM . moveM. Here's how to do this programmatically:

nmoveM :: Monad m => Int -> m Pos -> m Pos
nmoveM n = foldr1 (.) (replicate n moveM)  -- n "moveM"s connected by (.)

A question arises here: What is the result of moving 0 times? foldr1 is undefined for values of n <= 0. It makes quite a lot of sense to define nmoveM 0 to "doing nothing". In other words, the identity function, id.

nmoveM :: Monad m => Int -> m Pos -> m Pos
nmoveM n = foldr (.) id (replicate n moveM)

Here, we used foldr instead of foldr1 which needs an additional "base case", id.

Now we basically have what we want, but the type signature doesn't fit 100%: We have a m Pos -> m Pos, but we want Pos -> m Pos. That means, given a Pos, we first have to embed it in the context m, and then execute nMoveM. This embedding operator (i think it could be called initial algebra) is return (of type Monad m => a -> m a)

nmoves :: Monad m => Int -> Pos -> m Pos
nmoves n = nmoveM n . return

Let's write all that at once so you can appreciate the terseness in its full glory.

nmoves :: Monad m => Int -> Pos -> m Pos
nmoves n = foldr (.) id (replicate n move) . return

Composition of arrows

Using (>>=) is actually often a little unclean because it is so un-symmetric: It takes an m a and an a -> m b. In other words, it is a little too concerned about the transformed object, instead only the transformation for our case. This makes it unnecessarily hard to compose transformations. That's why we had to tack on . return: It's the initial transformation from Pos to m Pos, so that we can freely combine arbitrary amounts of m Pos -> m Pos.

Using (>>=) results in the following pattern:

ma >>= f_1 >>= f_2 >>= ... >>= f_n

where ma is a monad thing and the f_i are "arrows" of type a -> m b (where often a = b).

There is a much nicer variant, (>=>), which combines two a -> m b type arrows in a sequence, and returns another arrow.

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)

Here we are not unnecessarily concerned with the transformed objects, but only with transformations and their composition.

Now let's agree that move is actually such an arrow (Pos -> m Pos). So

move >=> move >=> move >=> move >=> move

is a valid expression still of type Pos -> m Pos. The composable nature of monads becomes much more apparent when using (>=>).

We could re-write nmoves using (>=>) like so:

nmoves :: Monad m => Int -> Pos -> m Pos
nmoves n = foldr1 (>=>) (replicate n move)  -- n "move"s connected by >=>

Again, we used foldr1, and we are asking "what gives 0 times move in a row"? It must be of the same type, Pos -> m Pos, and the answer is return.

nmoves :: Monad m => Int -> Pos -> m Pos
nmoves n = foldr (>=>) return (replicate n move)

Compare this to our earlier definition of nmoves in the monad endomorphisms world: Instead of functions combined with (.) and the base case id, we now combine arrows with (>=>) and the base case return. The benefit being that we don't have to inject the given Pos to m Pos.

What makes more sense depends on your case, but more often than not (>=>) is much cleaner than (>>=).

Answer 2

Using direct recursion:

inNMoves :: KnightPos -> Int -> [KnightPos]
inNMoves start 0 = return start
inNMoves start n = do
  first <- moveKnight start
  inNMoves first (n - 1)

But as mentioned in the comments: you can use built-in functions for this. For example:

inNMoves start n = (foldl (>>=) . return) start (replicate n moveKnight)

Or even completely pointfree:

inNMoves = (. flip replicate moveKnight) . foldl (>>=) . return

Answer 3

Note that concatMap moveKnight has type [Knight] -> [Knight] and will return the positions reachable from the input positions.

Knowing that, you can use:

iterate (concatMap moveKnight)

to generate an infinite list of sets of positions where the next set of positions is obtained by making a knight move from a position in the previous set.

For example:

iterate (concatMap moveKnight) [(1,2)]
  = [ [(1,2)],               -- the initial list
      [(3,1),(3,3),(2,4)],   -- after one iteration
      [(5,2),(1,2),(4,3),(2,3), ... -- after two iterations
      ...
    ]

Now in3 may be written as

in3 xs = moves !! 3
  where moves = iterate (concatMap moveKnight) xs