Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Haskell: Monads of monad

Tags:

haskell

monads

I'm learning some Haskell and I have some trouble with these Monads, I understood about them and know what they are about but in this particular case I have some issues. While learning it on LYAH I ran across an exercices which was about calculating the positions you could get to in 3 movements with a knight (from the chess game), we used the list monad like this:

Assuming,

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

This works and if I give my position to this function it sucessfuly calculate the possible future positions but now I'm looking to implements the Writer monad in it so I can retrieve how did I get to this point. So I made this function,

Assuming,

type KnightRoute = Writer [KnightPos] KnightPos

moveKnight' :: KnightPos -> [KnightRoute]
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 $ toKr (c',r') (c,r)
 where toKr pos oldpos = Writer (pos,[oldpos])

It works if I give it a KnightPos but using monads I can't extract a KnightPos from a KnightRoute to execute the function another time...

*Main> let a = moveKnight' (2,4) !! 0
*Main> runWriter a
((4,3),[(2,4)])
*Main> a >>= moveKnight'

<interactive>:4:7:
Couldn't match type ‘[]’ with ‘Writer [KnightPos]’
Expected type: KnightPos -> Writer [KnightPos] KnightRoute
  Actual type: KnightPos -> [KnightRoute]
In the second argument of ‘(>>=)’, namely ‘moveKnight'’
In the expression: a >>= moveKnight'

I understand why it's not working, I extract the (4,3) from my Writer but then I give this to KnightPos'. But KnightPos' returns a list of KnightRoute where I need a KnightRoute, this is an error of logic but I don't know how to do. Is there a simple way to do this with Monads?

Thanks by advance :)

like image 214
Bryce Tichit Avatar asked Aug 17 '15 12:08

Bryce Tichit


1 Answers

This kind of “combination of two monads” is an extremely common thing in Haskell. Fortunately, the language is flexible enough that we can nicely abstract over this.

Mathematically speaking what you want is a composition of two functors. Instead of that newtype, this is usually expressed with the concept of transformers: instead of using the Writer monad directly, you use the WriterT monad transformer. WriterT w [] a is basically the same as [Writer w a], so in your case you can use:

import Control.Monad.Trans.Class
import Control.Monad.Trans.Writer

moveKnight'' :: KnightPos -> WriterT [] [KnightPos] KnightPos
moveKnight'' (c,r) = do
   (c',r') <- lift [(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])
   tell [(c,r)]
   return (c',r')
like image 159
leftaroundabout Avatar answered Oct 02 '22 14:10

leftaroundabout