这个F#函数是尾递归的,在函数内多次调用递归函数吗？

Question

关于尾递归函数有几个问题,例如这个和这个但是找不到类似于下面的东西.

我的理解是尾部调用优化函数应该在其最后一次调用中返回累积值而无需进一步评估.使用因子函数很容易理解,例如,它被优化为循环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)

任何有关尾部调用优化上述代码的帮助都将非常感激.

Answer 1

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

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

在下面,最后一次电话是什么？

尾部位置有两个叫声.一,致电f.二,来电List.fold.递归调用不在尾部位置,因为其返回值不会由其调用者直接返回.

if (List.isEmpty xs) then f x

此外,使用模式匹配代替isEmpty和朋友.

任何有关尾部调用优化上述代码的帮助都将非常感激.

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

Answer 2

正如Jon已经说过的,你的函数不是尾递归的.基本问题是它需要多次递归调用自身(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函数是基于continuation的版本,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)

既然您没有发布完整的工作示例,我无法真正测试代码,但我认为它应该可行.