Haskell-如何在递归函数中跟踪计数器

Question

我在尝试跟踪函数中的计数器变量时遇到了一些困难。

我创建了一个函数，它以一个数字作为单个参数，并通过递归将该数字乘以二，将所有乘以二的数字相加，在下面的代码中更清楚地说明了我的意图：

sum :: Float -> Float
sum x = x + sum (2*x)

然而，我面临的困难是，我希望该函数递归仅限于十次。因此，在累加了十个数字后，我希望它停止递归。我尝试使用计数器来跟踪函数递归的次数，但没有成功。

这是我尝试过的代码:

sumTen :: Float -> Float
sumTen x n
    where
      n=10
       |n == 0 = x
       |otherwise = x + sumTen (2*x) (n-1)

我意识到上面的代码无法正常工作，因为在每次递归调用中，计数器n都将被赋予数字十的值，这意味着它永远不会达到基本情况n == 0。

使这个问题变得困难的是，sumTen必须使用一个参数进行调用。 在上面的代码中，我尝试给函数一个默认的参数n，并赋予一个预定的值，但很明显它不能正常工作。

有人能帮助我让这个递归函数在'n'个递归调用后停止吗？

- buydadip

---

小心！你的声望值是666，我不知道会发生什么！现在说正经的，你第一个代码块里的asin应该改成sum，或者反过来。 - afsantos

@afsantos 抱歉，那是个打错字... 666 完了，我真幸运 :) - buydadip

如果我理解正确的话，您想要一个带有一个参数的函数来得到您想要的结果，sumTen x。但是您希望递归调用在十次迭代后结束。是这样吗？ - afsantos

Answer 1

您可以使用一种辅助函数：

sumNRec x 0     = 0 
sumNRec x times = x + sumNRec (x*2) (times - 1)

sumTen x = sumNRec x 10

- Fernando

---

这并不完全符合OP的要求，但我认为他/她能够找出缺失的部分。 - Jeremy List

Answer 2

让我们以一种通用的方式解决问题。从您的原始函数开始：

sum :: Float -> Float
sum x = x + sum (2*x)

作为第一步，添加额外的rec参数。这个rec代表“递归调用”，是一个我们将要调用而不是函数体中所有递归调用的函数。具体来说，只需将定义右侧出现的任何sum替换为rec：

sumK :: (Float -> Float) -> Float -> Float
sumK rec x = x + rec (2*x)

现在，如果我们希望递归函数不执行任何次数，我们会得到 id。如果要递归一次，我们可以使用 sumK id，因为

sumK id x = x + id (2*x) = x + 2*x

要递归两次：使用sumK (sumK id)，因为

sumK (sumK id) x = x + sumK id (2*x) = x + (2*x) + 2*(2*x)

类似的，要递归 n 次，我们只需运行 sumK (... (sumK id)...)，其中 sumK 应用了 n 次。同样地，这可以写成组合形式 sumK . sumK . ... . sumK $ id。因此，要达到这一点，只需生成列表 [sumK,sumK,...]，将它们组合起来，最后应用 id。

sum10 :: Float -> Float
sum10 = compose (replicate 10 sumK) id

compose :: [a -> a] -> a -> a
compose = foldr (.) id

如果你愿意，你可以编写一个小的通用帮助程序：

recurseOnly :: Int -> ((a->a)->(a->a)) -> (a->a)
recurseOnly n funK = compose (replicate n funK) id

sum10 :: Float -> Float
sum10 = recurseOnly 10 sumK

- chi

Answer 3

sumTen :: Float -> Float
sumTen x = go 10 x
    where
      go n x
       | n == 0 = x
       | otherwise = x + go (n-1) (2*x)

这里有两个主要的观点: go 是一个简单的递归函数，有两个参数，它会传递 n 来确保在正确的时间停止。但是因为你不想暴露这个参数，所以顶层的函数 sumTen 只是 go 的部分应用版本。你甚至可以写成以下形式：

sumTen = go 10
  where go n x = -- ...

你更喜欢哪一个，其实是一种风格选择。

- amalloy

Answer 4

也许甚至是这个：

sumTen x = sum $ take (10+1) $ iterate (* 2) x

- Dan D.

---

这个并不像递归版本那样做同样的事情，因为加倍和添加在原始函数中交织在一起。这种“简化”并不真正忠实。 - amalloy

编译器可以通过循环融合和森林砍伐来进行自我交错。 - Dan D.

我不是说你错过了一些优化，我的意思是你的代码是错误的：它产生的结果与OP试图产生的代码不同。例如，与我的直接递归版本进行比较。 - amalloy