Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Haskell recursion in 'do' notation

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?

like image 843
Marcin Avatar asked Dec 02 '22 17:12

Marcin


2 Answers

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 (>>=).

like image 96
Jo So Avatar answered Jan 01 '23 18:01

Jo So


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
like image 45
Jeremy List Avatar answered Jan 01 '23 18:01

Jeremy List