4

我有一个在 Haskell 中计算二项式系数的函数，它看起来像这样：

binom :: Int -> Int -> Int
binom n 0 = 1
binom 0 k = 0
binom n k = binom (n-1) (k-1) * n `div` k

是否可以修改它并使其尾递归？

4

3 回答 3

11

是的。有一个使用累加器来实现尾递归的标准技巧。在您的情况下，您将需要其中两个（或累积一个有理数）：

binom :: Int -> Int -> Int
binom = loop 1 1
  where
    loop rn rd _ 0 = rn `div` rd
    loop _  _  0 _ = 0
    loop rn rd n k = loop (rn * n) (rd * k) (n-1) (k-1)

更新：对于较大的二项式系数，更好地使用Integer容易Int溢出。此外，在上述简单实现中，分子和分母都可以比最终结果大得多。一个简单的解决方案是累积，另一个是在每一步Rational都除以它们的gcdRational （AFAIK在幕后做的）。

于 2015-03-06T10:32:48.860 回答
3

是的，如果你引入一个带有额外参数的辅助函数，这是可能的：

-- calculate factor*(n choose k)
binom_and_multiply factor n 0 = factor
binom_and_multiply factor 0 k = 0
binom_and_multiply factor n k = binom (n-1) (k-1) (factor * n `div` k)

binom n k = binom_and_multiply 1 n k

最后一行可以用无点样式重写：

binom = binom_and_multiply 1

编辑：上面的函数显示了这个想法，但实际上被破坏了，因为div操作数被截断并与原始版本相反，没有数学证明要除的值总是分母的倍数。因此，必须用 Petr Pudlák 的建议替换该函数：

-- calculate (n choose k) * num `div` denom
binom_and_multiply num denom _ 0 = num `div` denom
binom_and_multiply _   _     0 _ = 0
binom_and_multiply num denom n k = binom_and_multiply num denom (num * n) (denom * k) (n-1) (k-1)

binom = binom_and_multiply 1 1

n在非优化的 haskell 实现中，如果您为and选择高值，您可能会对“正确的尾递归”变体仍然吞噬大量内存感到失望k，因为您正在通过堆空间在非尾递归实现中交易堆栈空间，因为 haskell 懒得及时计算所有产品。它一直等到您真正需要该值（可能要打印它），然后将两个产品表达式的表示形式存储在堆上。为避免这种情况，您应该binom_and_multiply像他们所说的那样在第一个和第二个参数中设置严格，因此在进行尾递归时会急切地评估产品。例如，可以将num和denom与零进行比较，这需要在继续之前评估因子的表达式：

-- calculate (n choose k) * num `div` denom
binom_and_multiply 0 0 _ _ = undefined  -- can't happen, div by zero
-- remaining expressions go here.

确保产品未“评估为大”的一般方法是使用以下seq功能：

-- calculate (n choose k) * num `div` denom
binom_and_multiply num denom _ 0 = num `div` denom
binom_and_multiply _   _     0 _ = 0
binom_and_multiply num denom n k = 
      new_num = num*n
      new_denom = denom*k
    in new_num `seq` new_denom `seq` binom_and_multiply new_num new_denom (n-1) (k-1)

这告诉 haskell 实现递归调用binom_and_multiply可能只发生在new_num并且new_denom已经被评估之后（对 WHNF，但解释 WHNF 超出了这个问题的范围）。

最后一句话：这个答案所做的通常称为将右折叠转换为左折叠，然后将左折叠设为严格。

于 2015-03-06T10:32:59.813 回答
1

使函数尾递归的“自动”方法是使用连续传递样式（根据定义为尾递归）重写它。可以说，在 Haskell 中执行此操作的一种直接方法是将原始函数转换为 monadic 形式，然后使用Cont monad执行结果：

import Control.Monad.Cont

-- | Original function in monadic form
binomM n 0 = return 1
binomM 0 k = return 0
binomM n k = do
  b1 <- binomM (n-1) (k-1)
  return $! b1 * n `div` k

-- | Tail recursive mode of execution
binom :: Int -> Int -> Int
binom n k = binomM n k `runCont` id

注意：通过这种方式，只需将ContT 转换器添加到它们的 monadic 堆栈中，就可以将许多 monadic 函数转换为尾递归函数。

于 2015-03-10T09:59:26.367 回答