Ханойские башни в Haskell


Конечно рекурсивной версии тривиально:

hanoi n = solve n 1 2 3

solve 0 _ _ _ = []
solve n from help to = (solve (n-1) from to help) ++ [(from,to)] ++ (solve (n-1) help from to)

Однако мой итерационный версия выглядит ужасно с большим количеством повторений кода:

hanoi n = map rep $ solve [1..n] [] [] where
          rep (x,y) | odd n = ([1,3,2] !! (x-1), [1,3,2] !! (y-1))
                    | otherwise = (x,y) 

solve from help to = head $ mapMaybe ready $ iterate step (from,help,to,[]) where
   step (1:xs,ys,zs,sol) = let (xs',zs',sol') = try xs zs 1 3 ((1,2):sol)
                           in (xs',1:ys,zs',sol')
   step (xs,1:ys,zs,sol) = let (xs',ys',sol') = try xs ys 1 2 ((2,3):sol)
                           in (xs',ys',1:zs,sol')
   step (xs,ys,1:zs,sol) = let (ys',zs',sol') = try ys zs 2 3 ((3,1):sol)
                           in (1:xs,ys',zs',sol')
   try [] [] _ _ sol = ([],[], sol)                            
   try (x:xs) [] a b sol = (xs,[x], (a,b):sol)                            
   try [] (y:ys) a b sol = ([y],ys, (b,a):sol)                            
   try (x:xs) (y:ys) a b sol | x < y = (xs,x:y:ys, (a,b):sol)
                             | y < x = (y:x:xs,ys, (b,a):sol)          
   ready ([],[],_,sol) = Just $ reverse sol
   ready ([],_,[],sol) = Just $ reverse sol
   ready _ = Nothing

Любые идеи? Более общий, Как бороться с такими ситуациями, где у вас есть много разных дел и args?

[Разъяснения]

С "итерационное решение" я имею в виду алгоритм, описанный здесь: http://en.wikipedia.org/wiki/Tower_of_Hanoi#Iterative_solution



2800
8
задан 6 апреля 2011 в 06:04 Источник Поделиться
Комментарии
1 ответ

МММ. Что о

import Data.Bits
hanoi :: Int -> [(Int, Int)]
hanoi n = map (\x -> ((x .&. (x-1)) `mod` 3, ((x .|. (x-1)) + 1) `mod` 3)) [1..shift 1 n]
main = print $ hanoi 5

?

4
ответ дан 15 апреля 2011 в 07:04 Источник Поделиться