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

Question

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

我

创建了一个函数，它将一个数字作为单个参数，并将数字递归乘以 2，将所有数字乘以 2 相加，下面的代码更清楚地表明了我打算做什么：

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"次递归调用后停止递归函数吗？

Answer 1

您可以使用辅助函数：

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

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

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

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

Answer 4

也许这甚至：

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