尾递归文件夹 [英] Tail-Recursive Foldr

问题描述

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

I'd like to write a tail-recursive foldr in f#, to take advantage of the tail-recursion optimization and learn more about functional programming.

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

I've written a tail-recursive foldl, and a foldr that isn't tail-recursive. I thought I could get a tail-recursive foldr by reversing the list fed to the function, then calling my tail recursive foldl on it, but this doesn't work because of the different order the function is supposed to be applied to.

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))

推荐答案

有两种方法.一种简单的方法是反转列表(这是一种尾递归操作)，然后从左侧开始折叠.一种更复杂的方法是使用延续传递样式.

There are two ways of doing this. An easier one is just to reverse the list (which is a tail-recursive operation) and then run fold from the left. A more sophisticated one is to use continuation-passing style.

在基于延续的版本中，您添加了一个额外的参数 continuation ，该参数在列表处理完成后便应调用(以便您可以将 func在此延续内调用，而不是将其放在堆栈上.

In the continuation-based version, you add an extra argument, continuation which is a function that should be called once the processing of the list finishes (so that you can put the func call inside this continuation, rather than having it on the stack).

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 调用延续.当您有非空列表时，我们递归调用 folder (tail-)，并为其赋予一个延续，该延续将对结果运行 func ，然后使用自己的 cont 调用.

When we get an empty list, we just call the continuation with the initial state acc. When you have non-empty list, we call foldr (tail-)recursively and give it a continuation that will run func on the result and then report the final aggregated value using its own cont call.

这篇关于尾递归文件夹的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！