F# 尾递归函数示例

Question

我是 F# 的新手，正在阅读有关尾递归函数的内容，并希望有人能给我两种不同的函数 foo 实现——一种是尾递归的，另一种不是尾递归的，这样我就可以更好地理解原理。

Answer 1

从一个简单的任务开始，比如将列表中的项目从“a”映射到“b”。我们想写一个具有签名的函数

val map: ('a -> 'b) -> 'a list -> 'b list

在哪里

map (fun x -> x * 2) [1;2;3;4;5] == [2;4;6;8;10]

从 开始非尾递归版本:

let rec map f = function
    | [] -> []
    | x::xs -> f x::map f xs

这不是尾递归，因为函数在进行递归调用后仍有工作要做。 ::是 List.Cons(f x, map f xs) 的语法糖.

如果我将最后一行重写为 | x::xs -> let temp = map f xs; f x::temp，该函数的非递归性质可能会更明显一些。 - 显然它在递归调用后工作。

使用 累加器变量 使其尾递归:

let map f l =
    let rec loop acc = function
        | [] -> List.rev acc
        | x::xs -> loop (f x::acc) xs
    loop [] l

这是我们在变量 acc 中建立一个新列表.由于列表是反向构建的，我们需要在将输出列表返回给用户之前反转输出列表。

如果你有点精神错乱，你可以使用 续传更简洁地编写代码:

let map f l =
    let rec loop cont = function
        | [] -> cont []
        | x::xs -> loop ( fun acc -> cont (f x::acc) ) xs
    loop id l

自调用 loop和 cont是最后一个无需额外工作即可调用的函数，它们是尾递归的。

这是有效的，因为继续 cont被一个新的 continuation 捕获，它又被另一个 continuation 捕获，从而产生一种树状数据结构，如下所示:

(fun acc -> (f 1)::acc)
    ((fun acc -> (f 2)::acc)
        ((fun acc -> (f 3)::acc)
            ((fun acc -> (f 4)::acc)
                ((fun acc -> (f 5)::acc)
                    (id [])))))

它按顺序构建列表，而无需您将其反转。

不管它的值(value)是什么，开始以非尾递归方式编写函数，它们更易于阅读和使用。

如果您有一个很大的列表要查看，请使用累加器变量。

如果您找不到以方便的方式使用累加器的方法，并且您没有任何其他选择，请使用延续。我个人认为难以阅读的非平凡的、大量使用延续的。