尾递归文件夹

Question

我想在f＃中编写一个尾递归文件夹，以利用尾递归优化并了解有关函数式编程的更多信息。

我写了一个尾递归折叠，和一个不是尾递归的文件夹。我以为可以通过反转馈给该函数的列表来获取尾递归文件夹，然后对其调用我的尾递归文件夹，但是由于该功能应采用的顺序不同，因此无法正常工作。

let rec tail_recurse_foldl(list: List<'a>, func:('b -> 'a -> 'b), acc: 'b) =
    match list with 
    | [] -> acc
    | [x] -> func acc x
    | x :: xs -> tail_recurse_foldl(xs, func, func acc x)

和非尾递归文件夹

let rec foldr(list: List<'a>, func:('a -> 'b -> 'b), acc: 'b) =
    match list with
    | [] -> acc
    | [x] -> func x acc
    | x::xs -> func x (foldr(xs, func, acc))

Answer 1

有两种方法可以做到这一点。一种简单的方法是反转列表（这是一种尾递归操作），然后从左侧开始折叠。一种更复杂的方法是使用延续传递样式。

在基于延续的版本中，您添加了一个额外的参数，continuation，这是一个在列表处理完成后应调用的函数（以便您可以将func调用放在该延续中，而不是放在堆栈中）。

let rec foldr(list: List<'a>, func:('a -> 'b -> 'b), acc: 'b, cont:'b -> 'b) =
    match list with
    | [] -> cont acc
    | x::xs -> foldr(xs, func, acc, fun r -> cont (func x r))

当我们得到一个空列表时，我们只用初始状态调用延续acc。当您有非空列表时，我们将foldr递归调用（tail-），并为其赋予一个延续，该延续将func在结果上运行，然后使用其自己的cont调用报告最终的汇总值。