Haskell: Monade di monade

Question

Sto imparando un po 'di Haskell e ho qualche problema con queste Monade, ne ho capito e so di cosa si tratta, ma in questo caso particolare ho alcuni problemi. Mentre l'apprendimento su Lyah mi sono imbattuto in un esercitazioni che era sul calcolo delle posizioni si potrebbe ottenere a in 3 movimenti con un cavaliere (dal gioco degli scacchi), abbiamo usato la lista monade, come questo:

Supponendo,

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

Questo funziona e se do la mia posizione a questa funzione, calcolerò con successo le possibili posizioni future ma ora sto cercando di implementare la monade di Writer in modo da poter recuperare come sono arrivato a questo punto. Così ho fatto questa funzione,

Supponendo,

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

Funziona se Ho dato un KnightPos ma utilizzando monadi non posso estrarre un KnightPos da un KnightRoute per eseguire la funzione un'altra volta ...

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

capisco perché non funziona, ho estratto il (4,3) dal mio scrittore, ma poi io do questo a KnightPos'. Ma KnightPos' restituisce un elenco di KnightRoute dove ho bisogno di un KnightRoute, questo è un errore di logica ma non so come fare. C'è un modo semplice per farlo con Monads?

Grazie di anticipo :)

Answer 1

Questo tipo di “ combinazione di due monadi ” è una cosa molto comune in Haskell. Fortunatamente, il linguaggio è abbastanza flessibile da poter essere facilmente riassunto.

Matematicamente parlando quello che vuoi è un composition of two functors. Invece di questo nuovo tipo, questo è solitamente espresso con il concetto di trasformatori: invece di utilizzare direttamente il monad Writer, si utilizza il trasformatore monad WriterT. WriterT w [] a è basically the same come [Writer w a], così nel tuo caso è possibile utilizzare:

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

Answer 2

È possibile scrivere

a' :: Int -> KnightRoute 
a' i = a >>= \p -> moveKnight' p !! i 

Qui i viene utilizzata per eliminare la lista interna di scrittori. E, grazie a pigrizia, è possibile trasformare Int -> a in [a]:

asList :: (Int -> a) -> [a] 
asList f = map f [1..] 

Poi l'elenco di tutte le rotte per a' è

a's :: [KnightRoute] 
a's = asList a' 

Mettendo tutto insieme:

moveKnight :: KnightRoute -> [KnightRoute] 
moveKnight k = map (\i -> k >>= \p -> moveKnight' p !! i) [1..]