在 Haskell 中使用递归和累加器

Question

我正在尝试保护递归，但我在使用 Haskell 语法时遇到困难。
我正在尝试在 Haskell 中使用递归来减少整数 'n' 次直到它达到我想要的基本情况，同时跟踪 'n'，然后 return 减少的整数和 'n' 作为我的信息的元组.

我的基本情况是整数在 1 到 13 之间。

例如，

Prelude> reduce 42
(3, 2)

Prelude> reduce 3
(3, 0)

为了解释逻辑，

Prelude> reduce 42
( (((42 - 13) - 13) - 13), 1+1+1+1 ) --> assume the accumulator = 0, hence 0,1,2.
(3, 3)

Prelude> reduce 3
(3, 0) --> already in base case!

目前，我有

reduce (x, 0)
  | x `elem` [1 .. 13] = (x, acc)
  | otherwise = reduce (x -13, acc + 1)
  where
    acc = 0

当然，我的 IDE 大喊我错了。我不知道如何将初始化元组实现到这个递归中，所以它就像 reduce :: a -> (a, b)
编辑：我想我越来越接近了……但当然，我正在尝试将其实现为 a -> (a,b)。

Answer 1

此位置不允许使用下划线。

reduce::Int->Int                                                                                                                                                                        
 reduce x
    | elem x [1..13] = x
    | otherwise = reduce (x - 13)

Answer 2

您需要使用辅助函数对其进行初始化：

reduce::Int->(Int,Int)
reduce x = reduce' (x,0)

reduce'::(Int,Int)->(Int,Int)
reduce' (x,n)

  | elem x [1..13] = (x,n) 

  | otherwise = reduce' (x-13,n+1)

Answer 3

使用累加器参数是一种很好的方法，而且确实是最有效的方法，前提是您使用 seq 正确地管理惰性。然而，一种可以说更简单、也许更容易学习的技术将不使用累加器参数。相反，执行递归调用然后修改其结果：

reduce x | x `elem` [1..13] = (x, 0)
         | otherwise = let (y, n) = reduce (x - 13)
                       in (y, n + 1)

事实证明，“修改元组的第二个元素”有一个可爱的快捷方式 - 我不建议在您的第一个程序中使用它，但它可能是一个有趣的尝试：

reduce x | x `elem` [1..13] = (x, 0)
         | otherwise = succ <$> reduce (x - 13)

在 Haskell 中使用递归和累加器

Using Recursion and Accumulators in Haskell

haskell

recursion

accumulator