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 在每次递归调用中都会被赋予值 10，这意味着它永远不会达到基本情况 n == 0.

之所以如此困难，是因为必须使用一个参数调用 sumTen。在上面的代码中，我试图给函数一个默认参数 n 和一个预定的值，但它显然不起作用。

谁能帮我在 'n' 次递归调用后停止递归函数？

Answer 1

可以使用辅助功能：

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

sumTen x = sumNRec x 10

Answer 2

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 = -- ...

你喜欢哪一款是一种风格选择，真的。

Answer 3

也许是这样：

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

Answer 4

让我们用一般的方式来解决这个问题。从您的原始功能开始：

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

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

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

现在，如果我们希望递归函数执行零次，我们将得到 id。为了只递归一次，我们可以使用 sumK id since

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

递归两次：sumK (sumK id) since

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

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

Haskell- How to keep track of counter in recursive function

recursion

haskell