Haskell add writer to function

Question

here is the snippet to calculate whether knight can move to desired position within x moves:

import Control.Monad (guard)
import Control.Monad.Writer    

type KnightPos = (Int,Int)
-- function returning array of all possible kinght moves from desired position
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')

-- nice little function tells us
-- whether knight can move to desired position within x moves
reaches :: KnightPos -> KnightPos -> Int -> Bool
reaches _ _ 0 = False
reaches from pos n =
    any (\p -> p == pos || reaches p pos (n-1)) $ moveKnight from


-- the result is True or False
-- does knight can move from cell 6,2 to cell 6,3 within 3 moves
main = print $ reachesm (6,2) (6,1) 3

Now i want to add Writer monad to 'reaches' funsction, but completely lost here i come to something like,

-- not so nice and little yet
reachesm :: KnightPos -> KnightPos -> Int -> Writer [String] [Bool]
reachesm _ _ 0 = return [False]
reachesm from pos n = do
    tell [ "-->" ++ (show pos) ]
    p <- moveKnight from -- ???
    np <- reachesm p pos (n-1)
    return(p == pos || any np)

but it does not even compile. I suspect its time for monad transormers here ?

UPD: So, finally we came to following rewrite, but i still unsatisfied with it, beacuse reachesm runs differently from pure variant, it recurses all n steps deep, but i expect it to stop iteration once it found the answer. Is it hard to modify it that way ? And another question is about laziness, it seem that in do block calculations are not lazy is it true ?

reachesm :: KnightPos -> KnightPos -> Int -> Writer [String] Bool
reachesm _    _   0 = return False
reachesm from pos n = do
   tell [ "-->" ++ (show from) ]
   let moves = moveKnight from
   np <- forM moves (\p -> reachesm p pos (n-1))
   return (any (pos ==) moves || or np)

Answer 1

Well it sounds like you are really committed to using the writer monad for this. So here's a solution:

reachesm :: KnightPos -> KnightPos -> Int -> [Writer [String] Bool]
reachesm from pos n | from == pos = return (return True)
reachesm _ _ 0 = return (return False)
reachesm from pos n = do
    p <- moveKnight from
    map (tell [show from ++ "-->" ++ show p] >>) $ reachesm p pos (n-1)

main = print . filter fst . map runWriter $ reachesm (6,2) (6,3) 3

This is silly though. The writer monad is only being used as a baroque interface to lists. Writer is not the solution to your problem, despite how much you clearly want it to be. Here is how I would write this algorithm:

-- returns all paths of length at most n to get to target
paths :: Int -> KnightPos -> KnightPos -> [[KnightPos]]
paths 0 _ _ = []
paths n target p 
    | p == target = return [p]
    | otherwise   = map (p:) . paths (n-1) target =<< moveKnight p

main = print $ paths 4 (6,3) (6,2) 

No writer monad, just the friendly old (:) operator.