algorithm - haskell中的递归函数

Question

我正在尝试用 haskell 解决一些编程问题。

我有这三种类型和 Hanoi 算法:

type Position = Int
type Move = (Position,Position)
type Towers = ([Int],[Int],[Int])

hanoi 1 i j = [(i,j)]
hanoi n i j = hanoi n' i otherT ++ [(i,j)] ++ hanoi n' otherT j
    where      
            n' = n-1
            otherT = 1+2+3-i-j -- other tower

现在我写了一个函数 make one MOVE。

move ::([Move],Towers) -> ([Move],Towers) 
move ::([Move],Towers) -> ([Move],Towers)
move ([],(xs,ys,zs) ) = ((error "Error"),(xs,ys,zs) )
move (((a,b): tail), (xs,ys,zs) )
              | a > 3 =    (tail, ((error "Error"),ys,zs) )                
              | b > 3 =    (tail, ((error "Error"),ys,zs ) )                
              | otherwise = hilfsfunktion (((a,b): tail), (xs,ys,zs) )



hilfsfunktion (((1,2): tail), ((x:xs),(y:ys),zs) ) 
            | x < y = (tail, (xs, (x:y:ys),zs) )
            | x > y = (tail, (xs, (error "too big"),(error "too big")))
hilfsfunktion (((1,2): tail), ((x:xs), [],zs) ) = (tail, (xs, x:[],zs) )

函数要长得多，但你可以看到我用模式匹配解决了这个问题。

现在我尝试编写一个函数，只要列表不为空，它就会调用这个“移动”函数。所以起初我使用模式匹配来处理列表为空的情况。

all_moves:: ([Move], Towers) -> Towers
all_moves ([],(xs,ys,zs) ) = (xs,ys,zs)
all_moves (((a,b): tail), (xs,ys,zs) ) = ????

现在我需要一些帮助，在 Java 中我会使用循环来解决这个问题。我想我必须递归调用函数“移动”，但我不知道该怎么做。如何解决这个功能？

Answer 1

我不确定您的河内解决方案究竟是如何工作的，但我认为这可以回答您的问题:

all_moves :: ([Move], Towers) -> Towers
all_moves ([], (xs, ys, zs)) = (xs, ys, zs)
all_moves movetowers         = all_moves (move movetowers)

希望您能明白为什么这行得通 - 我们不断地进行移动，然后进行递归调用，直到没有移动为止。