5

有一种明确的方法可以将二进制递归转换为在函数下封闭的集合的尾递归，即斐波那契数列的加法整数：

（使用 Haskell）

fib :: Int -> Int
fib n = fib' 0 1 n

fib' :: Int -> Int -> Int
fib' x y n
    | n < 1 = y  
    | otherwise = fib' y (x + y) (n - 1)

这是有效的，因为我们有我们想要的值，y和我们的操作，，x + y其中x + y返回一个整数，就像做的y那样。

但是，如果我想使用一个在函数下没有闭合的集合怎么办？我想采用一个函数将一个列表分成两个列表，然后对这两个列表执行相同的操作（即像递归地创建一个二叉树），当另一个函数神奇地告诉它查看结果拆分时何时停止时，我会停止：

[1, 2, 3, 4, 5] -> [[1, 3, 4], [2, 5]] -> [[1, 3], [4], [2], [5]]

那是，

splitList :: [Int] -> [[Int]]
splitList intList
    | length intList < 2    = [intList]
    | magicFunction x y > 0 = splitList x ++ splitList y
    | otherwise             = [intList]
  where
    x = some sublist of intList
    y = the other sublist of intList

现在，如何将这种二进制递归转换为尾递归？先前的方法不会显式工作，因为 (Int + Int -> Int与输入相同) 但 (Split [Int] -/> [[Int]]与输入不同)。因此，需要更改累加器（我假设）。

4

2 回答 2

7

使任何函数尾递归都有一个通用技巧：以连续传递样式（CPS）重写它。CPS 背后的基本思想是每个函数都有一个额外的参数——一个在完成时调用的函数。然后，原始函数不是返回值，而是调用传入的函数。后一个函数称为“延续”，因为它将计算继续到下一步。

为了说明这个想法，我将使用您的函数作为示例。请注意对类型签名以及代码结构的更改：

splitListCPS :: [Int] -> ([[Int]] -> r) -> r
splitListCPS intList cont
  | length intList < 2    = cont [intList]
  | magicFunction x y > 0 = splitListCPS x $ \ r₁ -> 
                              splitListCPS y $ \ r₂ -> 
                                cont $ r₁ ++ r₂
  | otherwise             = cont [intList]

然后，您可以将其包装成一个看起来很正常的函数，如下所示：

splitList :: [Int] -> [[Int]]
splitList intList = splitListCPS intList (\ r -> r)

如果你遵循稍微复杂的逻辑，你会发现这两个函数是等价的。棘手的一点是递归情况。在那里，我们立即调用splitListCPS。告诉完成后要做什么x的函数——在这种情况下，使用下一个参数 ( ) 调用。最后，一旦我们得到两个结果，我们只需将结果合并并将其传递给原始延续 ( )。所以最后，我们得到了与最初相同的结果（即），但我们没有返回它，而是使用了延续。\ r₁ -> ...splitListCPSsplitListCPSycontsplitList x ++ splitList y

此外，如果您查看上面的代码，您会注意到所有递归调用都处于尾部位置。在每一步，我们的最后一个操作总是递归调用或使用延续。使用聪明的编译器，这种代码实际上可以相当有效。

从某种意义上说，这种技术实际上与您所做的类似fib；然而，我们不是维护一个累加器值，而是维护一个我们正在做的计算的累加器。

于 2013-05-11T05:25:57.393 回答
2

您通常不希望在 Haskell 中使用尾递归。您想要的是生产性核心递归（另请参阅this），它描述了SICP中称为迭代过程的内容。

您可以通过将初始输入包含在列表中来修复函数中的类型不一致。在你的例子中

[1, 2, 3, 4, 5] -> [[1, 3, 4], [2, 5]] -> [[1, 3], [4], [2], [5]]

只有第一个箭头不一致，所以改成

[[1, 2, 3, 4, 5]] -> [[1, 3, 4], [2, 5]] -> [[1, 3], [4], [2], [5]]

它说明了迭代应用的过程concatMap splitList1，其中

   splitList1 xs 
      | null $ drop 1 xs = [xs]
      | magic a b > 0    = [a,b]    -- (B)
      | otherwise        = [xs]
     where (a,b) = splitSomeHow xs

(B)如果在某个迭代中没有触发任何案例，您想要停止。

（编辑：删除了中间版本）

但是最好尽快生成准备好的输出部分：

splitList :: [Int] -> [[Int]]
splitList xs = g [xs]   -- explicate the stack
  where
    g []                  = []
    g (xs : t)
       | null $ drop 1 xs = xs : g t
       | magic a b > 0    = g (a : b : t)
       | otherwise        = xs : g t
     where (a,b) = splitSomeHow xs 
           -- magic a b = 1
           -- splitSomeHow = splitAt 2

不要忘记用-O2标志编译。

于 2013-05-12T10:48:27.550 回答