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

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

现在我尝试编写一个函数，只要列表不为空就调用此 "move" 函数。所以起初我使用模式匹配来处理列表为空的情况。

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

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

Answer 1

我不确定你的河内解决方案究竟是如何工作的，但我认为这回答了你的问题：

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

希望您能明白为什么这样做 - 我们一直在进行移动，然后进行递归调用，直到没有移动为止。

Answer 2

我想这样做，尽管我的方法也不是递归的。

allllmove :: 塔 -> 塔

allmove ([0],[0],[0]) = ([0],[0],[0])

allmove ((x:xs),y,z)

长度(x:xs) > 长度z && 长度z > 长度y = (xs,(x:y),z)

长度(x:xs) >= 长度z && 长度(x:xs) > 长度y = (xs,(x:y),z) ... .. .

haskell 中的递归函数

Recursive function in haskell

algorithm

haskell

recursion

pattern-matching

towers-of-hanoi