Haskell hinzufügen Schriftsteller Funktion

Question

hier ist das Snippet zu berechnen, ob Ritter in der gewünschten Position innerhalb x bewegt bewegen kann:

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 

Jetzt will ich Writer Monade in der ‚erreicht‘ funsction, aber völlig verloren hier ich komme zu etwas wie,

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

aber es kompiliert nicht sogar. Ich vermute, es ist Zeit für Monad-Transformers hier?

UPD: So, endlich kamen wir zu folgenden Rewrite, aber ich damit noch nicht zufrieden, beacuse reachesm anders aus reinen Variante läuft, es recurses alle n Schritte tief, aber ich erwarten, dass es zu stoppen Iteration, sobald es die Antwort gefunden hat. Ist es schwierig, das so zu ändern? Und eine andere Frage ist über Faulheit, es scheint, dass in tun Block Berechnungen sind nicht faul ist es wahr?

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

Nun, es klingt, als ob Sie wirklich verpflichtet sind, den Schriftsteller monad dafür zu verwenden. Also hier ist eine Lösung:

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 

Das ist aber albern. Die Schreibermonade wird nur als barocke Schnittstelle zu Listen verwendet. Writer ist nicht die Lösung für Ihr Problem, trotz wie viel Sie es eindeutig wollen. Hier ist, wie ich diesen Algorithmus schreiben würde:

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

kein Schriftsteller Monade, sondern nur den freundlichen alten (:) Operator.

Answer 2

Hier ist eine Version, die funktioniert:

moveKnight :: KnightPos -> [KnightPos] 
moveKnight (c,r) = filter legal possible 
     where possible = [ (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)] 
      legal (c',r') = (c' `elem` [1..8] && r' `elem` [1..8]) 

Answer 3

Es ist ein bisschen einfacher (zumindest für mich) zu denken:

main = print $ runWriterT (reachesm (6,2) (6,5) 4) 

reachesm :: KnightPos -> KnightPos -> Int -> WriterT [String] [] Bool 
reachesm _ _ (-1) = return False 
reachesm from pos n 
    | from == pos = tell [ "-->" ++ (show from) ] >> return True 
    | otherwise = 
    do 
    p <- lift (moveKnight from) 
    t <- reachesm p pos (n-1) 
    guard t 
    tell [ "-->" ++ (show from) ] 
    return True 

können auch Ihre moveKnight Funktion wie folgt geschrieben werden von diesem als einen Weg in einem Baum suchend.

Zuerst importieren wir ein paar Funktionen von Data.Tree:

import Data.Tree (levels, unfoldTree) 

Jetzt haben wir eine Funktion zur Entfaltung des Baumes mit Geschichte, nehmen Sie die Top-n + 1 Ebene des Baums zu schreiben, und sehen, ob sie die gewünschte Position enthalten :

reaches :: KnightPos -> KnightPos -> Int -> Maybe [KnightPos] 
reaches from pos n = lookup pos . concat . take (n + 1) $ levels tree 
    where 
    tree = unfoldTree unfolder (from, []) 
    unfolder (p, hist) = ((p, hist'), map (flip (,) hist') $ moveKnight p) 
     where hist' = p : hist 

das uns von der Endposition zu Beginn in der gegebenen Anzahl von Schritten einen Weg gibt, wenn es vorhanden ist:

Dies ist eine schnelle Lösung aus der Spitze von meinem Kopf

(Wir könnten natürlich umkehren dies, wenn wir einen Weg von Anfang bis Ende. Wollen)

, und es ist nicht unbedingt sehr effizient, aber ich finde es konzeptuell einfach.

Answer 4

Okay, unser Ziel ist es, diese Funktion in die Wrtier Monade zu bringen.

reaches :: KnightPos -> KnightPos -> Int -> Bool 
reaches _ _ 0 = False 
reaches from pos n = 
    any (\p -> p == pos || reaches p pos (n-1)) $ moveKnight from 

Beginnen wir mit der Typensignatur. Fügen Sie einfach Writer um den Ergebnistyp:

reaches :: KnightPos -> KnightPos -> Int -> Writer [String] Bool 

Die ursprüngliche Funktion nicht [Bool] zurückgekommen, so gibt es keinen Grund für die neue Funktion ein Writer [String] [Bool] zurückzukehren.Heben Sie den Rückgabewert des Basisfall:

reaches _ _ 0 = return False 

Wie Sie vermutet, es ein wenig komplizierter wird die rekursive Fall zu tun. Fangen wir an wie bei tell in der aktuellen pos, die Sie richtig gemacht haben.

reaches from pos n = do 
    tell ["-->" ++ show pos] 

moveKnight ist in dem Schriftsteller Monade nicht so wir es nicht <- binden müssen, um mit ihm zu rufen. Verwenden Sie einfach let (das heißt wir konnten moveKnight pos ersetzen, wenn wir unsere neue Variable verwenden, wenn wir wollten):

let moves = moveKnight from 

Lassen Sie uns jetzt die Liste der rekursiven Ergebnisse. Dieses Mal haben wir tun binden müssen, da wir die Bool aus einem Writer [String] Bool bekommen. Wir werden die monadischen Variante map verwenden, mapM :: (a -> m b) -> [a] -> m [b]:

np <- mapM (\p -> reachesm p pos (n-1)) ps 

Jetzt np :: [Bool]. Also dann fertig machen wir nur Ihre Logik:

return (any (pos ==) moves || or np) 

or :: [Bool] -> Bool ist nur any id.

Also denken Sie daran, eine Variable zu binden, wenn Sie die a von einem m a erhalten möchten, verwenden <-, sonst let verwenden.

Um es von main zu verwenden, können Sie verwenden runWriter :: Writer w a -> (w,a):

main = print $ runWriter (reachesm (6,2) (6,1) 3) 

Dieser Code hat immer noch einen Fehler, aber es kompiliert und liefert, was Sie es über den Schriftsteller Kanal gesagt, so sollte es genug sein, dass Sie kann das verbleibende Problem einfach debuggen. Hoffe das hat geholfen.

Answer 5

Hier ist mein später Versuch:

import Control.Monad 

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


findpath :: KnightPos -> KnightPos -> Int -> [[KnightPos]] 
findpath start end steps = trail [start] steps 
    where trail curtrail steps = do 
       nextstep <- moveKnight $ last curtrail 
       if steps == 1 then 
        do guard (nextstep == end) 
        return (curtrail ++ [nextstep]) 
       else trail (curtrail ++ [nextstep]) (steps - 1)