1

关于尾递归函数有几个问题，例如this和this但找不到与以下类似的任何内容。

我的理解是尾调用优化函数应该在其最后一次调用中返回一个累积值，而不需要任何进一步的评估。例如，使用阶乘函数很容易理解，它被优化为循环2。但在其他情况下，例如在以下情况下，告诉您最后一次调用是什么并不总是很明显？其中有很多，因为函数在体内不止一次被递归调用。

Brian 提出了一种查找方法，但我不确定如何优化尾调用。我可以将--tailcalls标志传递给编译器以自动执行它，但它总是成功吗？

f并g返回相同的类型。

type T = T of int * T list

let rec myfunc f (T (x,xs)) =
    if (List.isEmpty xs) then f x
    else 
        List.fold g acc (List.map (fun xxs -> myfunc f xxs) xs)

任何对尾调用优化上述代码的帮助将不胜感激。

4

2 回答 2

5

我的理解是尾调用优化函数应该在最后一次调用中返回一个累积值......

几乎。尾递归是递归调用都出现在尾部位置。尾部位置意味着调用者直接从其被调用者返回结果。

下面，最后一个电话是什么？

尾部位置有两个调用。首先，调用f. 二是调用List.fold。递归调用不在尾部位置，因为它的返回值不是由它的调用者直接返回的。

if (List.isEmpty xs) then f x

另外，使用模式匹配而不是isEmpty和朋友。

任何对尾调用优化上述代码的帮助将不胜感激。

在任何人能够帮助您编写尾递归版本之前，您必须发布工作代码或至少一个规范。一般来说，最简单的解决方案是使用连续传递样式或命令样式编写。

于 2012-05-28T22:55:19.880 回答
5

正如乔恩已经说过的，您的函数不是尾递归的。基本问题是它需要多次递归调用自身（列表中的每个元素一次xs，这是在传递给的 lambda 函数中完成的List.map）。

如果您确实需要进行多次递归调用，则使用延续传递样式或即命令式堆栈可能是唯一的选择。延续背后的想法是，每个函数都将采用另一个函数（作为最后一个参数），当结果可用时应该执行该函数。

以下示例显示了普通版本（左侧）和基于延续（右侧）

let res = foo a b                          fooCont a b (fun res ->
printfn "Result: %d" res                     printfn "Result: %d" res)

要以延续传递风格编写函数，您还需要使用基于延续的fold函数。您可以首先map通过将完成的操作map移入 lambda 函数来避免使用fold：

List.fold g acc (List.map (fun xxs -> myfunc f xxs) xs)

变成：

List.fold (fun state xxs -> g state (myfunc f xxs)) acc xs

然后您可以按如下方式重写代码（请注意，f您g的问题中没有显示的两者现在都是基于延续的函数，因此它们需要额外的参数，代表延续）：

// The additional parameter 'cont' is the continuation to be called 
// when the final result of myfunc is computed
let rec myfunc' f (T (x,xs)) cont = 
  if (List.isEmpty xs) then 
    // Call the 'f' function to process the last element and give it the
    // current continuation (it will be called when 'f' calculates the result)
    f x cont
  else  
    // Using the continuation-based version of fold - the lambda now takes current
    // element 'xxs', the accumulated state and a continuation to call
    // when it finishes calculating 
    List.foldCont (fun xxs state cont -> 
      // Call 'myfunc' recursively - note, this is tail-call position now!
      myfunc' f xxs (fun res -> 
        // In the continuation, we perform the aggregation using 'g'
        // and the result is reported to the continuation that resumes
        // folding the remaining elements of the list.
        g state res cont)) acc xs cont

该List.foldCont函数是一个基于延续的版本，fold可以写成如下：

module List = 
  let rec foldCont f (state:'TState) (list:'T list) cont =
    match list with
    | [] -> cont state
    | x::xs -> foldCont f state xs (fun state ->
        f x state cont)

由于您没有发布完整的工作示例，因此我无法真正测试代码，但我认为它应该可以工作。

于 2012-05-29T00:00:43.217 回答