Transforming Türme von Hanoi Bewegungsablauf Konfigurationsfolge

Question

Als Teil einer „selbst auferlegten Hausaufgaben“ auf Haskell Studie, hat sich die klassische Lösung des Turms von Hanoi:

doHanoi :: Int -> Int -> Int -> [(Int, Int)] 
doHanoi 0 _ _ = [] 
doHanoi n from to = first ++ [(from, to)] ++ last 
    where 
     using = 3 - from - to; 
     first = doHanoi (n - 1) from using; 
     last = doHanoi (n - 1) using to 

(wo die Bedeutung von doHanoi n from to using get die asequence von Bewegungen der Scheiben 0.. n - 1 sind am Wirbel unter der Annahme from, und wir müssen sie bewegen to peg.)

Dies ist die Folge von Bewegungen gibt, zum Beispiel

>>> doHanoi 3 0 2 
[(0,2),(0,1),(2,1),(0,2),(1,0),(1,2),(0,2)] 

Ich wollte dann sehen, ob ich die Ausgabe in den Satz von Konfigurationen (d. H. Zunächst alle Ringe sind auf der linken Seite, dann gibt es Zwischenkonfigurationen, schließlich alle Ringe sind auf der rechten Seite). Ich konnte dies durch eine changeConfig Funktion

changeConfig :: [[Int]] -> (Int, Int) -> [[Int]] 
changeConfig [e0:e0s, e1s, e2s] (0, 1) = [e0s, e0:e1s, e2s] 
changeConfig [e0:e0s, e1s, e2s] (0, 2) = [e0s, e1s, e0:e2s] 
changeConfig [e0s, e1:e1s, e2s] (1, 0) = [e1:e0s, e1s, e2s] 
changeConfig [e0s, e1:e1s, e2s] (1, 2) = [e0s, e1s, e1:e2s] 
changeConfig [e0s, e1s, e2:e2s] (2, 0) = [e2:e0s, e1s, e2s] 
changeConfig [e0s, e1s, e2:e2s] (2, 1) = [e0s, e2:e1s, e2s] 

Schreiben

dann scanl mit:

>>> scanl changeConfig [[0.. 2], [], []] (doHanoi 3 0 2 1) 
[[[0,1,2],[],[]],[[1,2],[],[0]],[[2],[1],[0]],[[2],[0,1],[]],[[],[0,1],[2]],[[0],[1],[2]],[[0],[],[1,2]],[[],[],[0,1,2]]] 

Das funktioniert zwar, ich glaube ich etwas in changeConfig bin fehlt: das ist nur eine erschöpfende Aufzählung aller Konfigurationen In einer Umgebung, die eine Form von zyklischer Symmetrie hat, funktionierte das, weil es drei Stifte gibt, und würde nicht gut skalieren (in Bezug auf LOC). Was ist der "haskellische" Weg, es zu schreiben?

Answer 1

Dank freundlicher Hilfe von chepner und jberryman, hier ist, was ich mir ausgedacht habe.

Die Funktion der Bewegungen unverändert zu finden:

doHanoi :: Int -> Int -> Int -> [(Int, Int)] 
doHanoi 0 _ _ = [] 
doHanoi n from to = first ++ [(from, to)] ++ last 
    where 
     using = 3 - from - to; 
     first = doHanoi (n - 1) from using; 
     last = doHanoi (n - 1) using to 

nun eine Hilfsfunktion, changePeg es i from to new_e kehrt der Ausgang i vorausgesetzt, es Elemente enthalten es war i seinen Index zu binden, war die Bewegung von from zu to, und von Element new_e.

changePeg :: [Int] -> Int -> Int -> Int -> Int -> [Int] 
changePeg es i from to new_e 
    | i == from = tail es 
    | i == to = new_e: es 
    | otherwise = es 

diese Verwendung wird changeConfig

changeConfig :: [[Int]] -> (Int, Int) -> [[Int]] 
changeConfig es (from, to) = new_es where 
    new_e = head $ es !! from; 
    new_es = [changePeg (es !! i) i from to new_e | i <- [0.. 2]] 

Wie zuvor kann die Lösung mit

>>> scanl changeConfig [[0.. 2], [], []] (doHanoi 3 0 2) 
[[[0,1,2],[],[]],[[1,2],[],[0]],[[2],[1],[0]],[[2],[0,1],[]],[[],[0,1],[2]],[[0],[1],[2]],[[0],[],[1,2]],[[],[],[0,1,2]]]