这个 Haskell 河内塔解决方案是更有效还是完全多余？

Question

This Haskell solution has been described as recursive, but not quite efficient according to a few claims, so I have tried to rewrite it with that in mind. The problem is described in a course that is available online and whose homework was the Tower of Hanoi.

我的新解：

type Peg = String
type Move = (Peg, Peg)

hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]

hanoi n a b c = hanoiToList n a b c []
  where
    hanoiToList 0 _ _ _ l = l
    -- hanoiToList 1 a b _ l = (a, b) : l
    hanoiToList n a b c l = hanoiToList (n-1) a c b ((a, b) : hanoiToList (n-1) c b a l)

我来解释一下原因：如果这个函数最终是一个列表，那么你最好将它与另一个以空参数为参数的函数进行比较，否则在它被解决后追加它，这我认为这是效率低下的原因，从而导致在其位置调用相同的功能。结果已经过检查并且是正确的，但考虑到我链接到的先前解决方案，我想知道这是否更有效或仅仅是多余的。

编辑：我评论了一行不必要的内容。

Answer 1

是的，这摆脱了 (:) 构造函数的低效复制。这是一种稍微不惯用的编写方式，但更惯用的方式在使用优化编译时应该具有相同的性能。

hanoi n a b c = hanoiToList n a b c []
  where
    hanoiToList 0 _ _ _ = id
    hanoiToList n a b c = hanoiToList (n-1) a c b . ((a, b) :) . hanoiToList (n-1) c b a

这是稍微更惯用的方法。这一切都是为了强调你正在建立价值转变的观点。实际上，只要按预期内联和简化函数组合，它就完全相同。

这个 Haskell 河内塔解决方案是更有效还是完全多余？

Is this Haskell Tower of Hanoi solution more efficient or simply redundant?

performance

haskell

recursion

towers-of-hanoi