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?
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 moveM
s 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 (>>=)
.
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With