OCaml 中二叉树中的尾递归最大元素
tail-recursive maximum element in a binary tree in OCaml
我正在练习尾递归并且我想练习，给定类型
type 'a tree = Leaf of 'a | Pair of 'a tree * 'a tree
和一个在二叉树中找到最大元素的函数
let rec tree_max t = match t with
| Leaf v -> v
| Pair (l,r) -> max (tree_max l) (tree_max r)
使上述函数尾递归
我试过了
let rec tree_max t acc= match t with
| Leaf v -> acc
| Pair (l,r) -> (max (tree_max l) (tree_max r))::ACC
我也试过了
let rec tree_max t acc= match t with
| Leaf v -> acc
| Pair (l,r) -> if (max (tree_max l) (tree_max l) = acc) then tree_max l acc else tree_max r acc
但它们都会产生语法错误。有人知道如何实现吗？
在伪代码中，您需要将模式匹配方程转换为正确的 match 语法，
tree_max (Leaf a) = a
| (Pair (l,r)) = go1 [l;r]
go1 (Pair (l,r)::ts) = go1 (l::r::ts)
| (Leaf a::ts) = go a ts
go a [] = a
| a (Leaf b::ts) = go (max a b) ts
| a (Pair (l,r)::ts) = go a (l::r::ts)
尾递归函数不一定总是调用自己；它可以调用另一个函数，这个函数又可以调用另一个函数；等等，只要所有调用都是tail.
go1 去最左边的叶子找到第一个值；然后 go 去做真正的工作。它的列表参数用作 yet-to-be-processed 节点的显式堆栈，因此当有 none 更多要处理时，处理必须停止。
TL;DR;这个问题比看起来要深一点，因为我不想做别人的功课，所以我决定写一篇关于将递归函数转换为尾递归函数的指南。结果比我想象的要大一点:)
（尾）递归终极指南
什么是尾递归？
确定一个函数何时是尾递归函数并不总是很容易。关键思想是，如果您在 递归调用之后做一些工作，那么您的函数不是 尾递归。而要使其成为尾递归，我们需要将足够的信息传递给递归调用，以便后者可以在没有我们干预的情况下计算结果，即函数的结果成为递归调用的结果。
这是一个简单的例子，一个计算列表长度的非尾递归length函数，
let rec length = function
| [] -> 0
| _ :: xs -> 1 + length xs
我们可以看到，在1 + length xs中，计算机首先计算length xs，然后等待它的结果只是加一。显然，我们可以将当前长度传递给递归调用并让基本情况 return 它，例如
let rec length acc = function
| [] -> acc
| _ :: xs -> length (acc+1) xs
因此，如您所见，诀窍是使用参数将信息传递给递归。一个直接的警告是我们现在有一个额外的参数，acc（代表 accumulator）。约定是在嵌套函数中向界面的最终用户隐藏此参数。我通常称这个函数为loop，例如
let length xs =
let rec loop acc = function
| [] -> acc
| _ :: xs -> loop (acc+1) xs in
loop 0 xs
在 length 示例中，我们能够将我们的算法从内存大小的 O(N) 改进为 O(1)。事实上，在非尾递归版本中，编译器创建了一个等于列表长度的堆栈调用链，每个槽存储子列表的长度。本质上，编译器构建了一个立即结果的单链表，然后使用 + 运算符将其缩减。这是一种非常低效的求和 n 数字的方法。
但有时，我们无法将递归参数减少为单个标量值，因此在堆栈中构建结果可能是有益的，请考虑将函数应用于每个元素的 map 函数一个列表并构建一个新的结果列表，
let rec map f = function
| [] -> []
| x :: xs -> f x :: map f xs
无法将此功能从 O(N) 减少到 O(1)，因为我们必须构建和 return 一张新地图。但是它消耗堆栈，这是一种稀缺1资源，不像常规的堆内存。所以让我们把这个函数变成尾递归函数。同样，我们必须将必要的信息传递给递归，以便当我们到达递归底部时我们可以构建答案，
let map f xs =
let rec loop acc = function
| [] -> List.rev acc
| x :: xs -> loop (x::acc) xs in
loop [] xs
如您所见，我们再次使用 acc 和嵌套循环函数来隐藏额外参数的技巧。与前面的示例不同，我们使用列表而不是整数来累加结果。由于我们是假装列表，我们最终得到的结果顺序颠倒了，所以我们必须在底部将它倒过来。我们可以改为附加到列表，但这会导致代码效率非常低，因为附加到单链表是一个 O(N) 操作，因此如果我们重复它 N 次，我们将得到O(N^2) 复杂度。
树上的递归
在上面的示例中，我们或多或少地选择了累加器，但是树状结构呢？对于树，我们必须在每个步骤上递归多次，例如，
let max_elt t =
let rec loop current_max t = match t with
| Leaf x -> max current_max x (* so far so good *)
| Tree (l,r) -> <??> in
loop <??> t
正如我们所见，将我们的函数转换为累加器样式的递归，显然选择累加器作为整数没有帮助。首先，我们现在必须对初始最大值做出可疑的选择，接下来，这是主要问题是我们必须分支 l 和 r 我们不能递归到他们都在同一个递归调用中......或者我们可以？
是的，我们可以，事实上，有多种解决方案。让我们从累加器式递归开始。因为我们想要递归几个子树（在我们的例子中是两个）并且我们想在一次调用中完成，所以我们必须将树的另一个分支传递到累加器中。所以累加器本身变成了我们还没有访问过的树的列表。这种方法的通用名称是“工作列表算法”，其关键思想是我们做尽可能多的工作并将其余的推入工作列表，例如，
let max_elt t =
let rec loop work t =
match t with
| Tree (l,r) -> loop (l::work) r
| Leaf x -> match work with
| [] -> x
| [Leaf x'] -> max x x'
| Tree _ as t' :: ts -> loop (t::ts) t'
| Leaf x' :: t :: ts -> loop (Leaf (max x x') :: ts) t in
loop [] t
哎呀，这看起来很复杂，比原来的堆栈消耗版本复杂得多。这是否值得，即我们是否显着提高了我们的表现？对于平衡树，不，我们处于同等水平——基于堆栈的版本消耗 O(depth(t)) 个堆栈槽，其中 depth 是树的深度。由于平衡二叉树（节点数）的大小 N 是 2^depth(t)，我们实际上消耗了 O(log(N))，这很好。我们的尾递归版本也消耗相同数量的堆。而对于一棵平衡树，我们不应该害怕消耗堆栈内存，因为在此之前我们会 运行 出堆内存（同样，要存储深度为 N 的树，我们需要 2^N 个元素，甚至如果堆栈被限制为 64 个槽，我们将能够处理大到 2^64 的树，这比任何计算机都多得多）。这就是为什么对于平衡树我们不需要担心尾递归并安全地使用正则递归，这更具可读性和效率。
但是如果树不平衡怎么办？即，当我们仅在左侧有子树而在右侧有叶子时。在这种极端情况下，我们的元素数量等于列表的深度。不幸的是，除非我们专门平衡我们的树，这是另一个有趣的话题，否则我们将经常以这种树结束，即尝试编写一个 of_list 函数来从列表中生成一棵树，赌注很高你最终进入了一个不平衡的列表。
对于不平衡的树，我们很容易得到堆栈溢出。但是上面这个函数，实在是太难理解了，也太难证明它终止了。
也许有办法让它尾递归并且易于理解？答案是肯定的，请继续阅读。
树上的递归（不涉及大脑）
好吧，下一个技巧有点难掌握，因为它涉及延续。如果你阻止你的大脑试图理解这个概念，那将是一个无需动脑筋的练习，仅仅是一种技术替代。但我们并不是在寻找捷径，所以让我们动动脑筋。
关键思想还是一样的，我们需要调用一次递归函数并传递给它一些递归完成工作所必需的值。在我们之前的示例中，我们将“要完成的工作”具体化为尚未处理的节点列表。但是如果我们将它表示为一个函数，它将接收中间结果并继续工作，即作为一个延续。约定是调用延续 k，但我们将其称为 return、
let max_elt t =
let rec loop t return =
match t with
| Leaf x -> return x
| Tree (l,r) ->
loop l @@ fun x ->
loop r @@ fun y ->
return (max x y) in
loop t (fun x -> x)
好的，首先，什么是@@，我们不是调用了两次循环吗？这是一个应用程序运算符，定义为 let (@@) f x = f x，因此如果我们重写我们的 loop 函数，我们可以看到我们确实每次调用一次，
let rec loop t return =
match t with
| Leaf x -> return x
| Tree (l,r) ->
loop l (fun x ->
loop r (fun y ->
return (max x y)))
所以，慢慢地，在Tree (l,r)的情况下我们调用loop l <cont1>并传递给它一个continuation（一个函数）接收子树l的最大值然后调用loop r <cont2>，它从r接收最大值，将它们结合起来找到两个最大值，然后使用延续return将它送回（向上）。
还不能完全确定这是尾递归吗？让我们尝试更详细地重写它，
let rec loop t return =
match t with
| Leaf x -> return x
| Tree (l,r) ->
let cont1 x =
let cont2 y = return (max x y) in
loop r cont2 in
loop l cont1
如您所见，所有对循环的调用都在尾部位置。但它是如何工作的？
这里的主要思想是每个延续都捕获一些信息，即在每个延续中我们都有一些从外部作用域捕获的自由变量，例如，cont1 捕获正确的树 r , 而cont2 捕获了上层continuation return, 这样最后我们就有了一个continuation 的链表。所以没有免费的奶酪，我们仍然使用 O(N) 内存槽，但由于延续存储在堆内存中，我们不再浪费宝贵的堆栈。
好的，现在是最后一步了，我们如何才能在不让大脑过度紧张的情况下应用这种技术，即，纯粹在句法上？为此，我们将使用 OCaml 的新功能，称为绑定运算符，它允许我们定义我们自己的 letXX 运算符，例如，
let (let@) = (@@)
这样 f (fun x -> <body>) 可以表示为 let@ x = f in <body> 并且使用这个运算符，我们可以表达我们的尾递归版本几乎与非尾递归版本相同，
let max_elt t =
let rec loop t return =
match t with
| Leaf x -> return x
| Tree (l,r) ->
let@ x = loop l in
let@ y = loop r in
return (max x y) in
loop t (fun x -> x)
与非尾递归版本比较，
let rec max_elt t =
match t with
| Leaf x -> x
| Tree (l,r) ->
let x = max_elt l in
let y = max_elt r in
max x y
所以我们可以建立一个简单的句法规则，
- 将额外的函数参数附加到参数列表
- 所有递归调用都应绑定
let@
- returned 值应通过
return 传递，除非我们想更早地退出递归。
提前逃逸或短路
如果我们不使用return在递归中向上传递值呢？在那种情况下，我们的结果立即成为整个顶级调用的结果，因此我们可以在找到一个元素时缩短我们的搜索并且不检查其他元素。例如，这里是我们如何测试我们的树的元素成员资格，
let has t needle =
let rec loop t return = match t with
| Leaf x -> x = needle || return ()
| Tree (l,r) ->
let@ () = loop l in
loop r return in
loop t (fun () -> false)
您可以看到，在 let@ () = loop l 中，我们甚至不用费心从子树搜索中 return 真或假。我们仅使用函数 return 告诉我们的事实作为元素不存在于左子树中的证据，因此我们需要检查右子树。
Continuations 是函数式语言的一个非常强大的特性，你可以用它们来实现美妙的东西，比如可变参数函数、非确定性计算、轻松表达回溯等等。但这是一个不同的话题，我希望我们最终会探讨。
1)稀缺与否取决于架构、操作系统及其配置。在现代 Linux 上，您可以通过设置 ulimit -s unlimited 使堆栈大小不受限制，根本不用担心堆栈溢出。在其他操作系统上，最大堆栈大小有硬性限制。
我正在练习尾递归并且我想练习，给定类型
type 'a tree = Leaf of 'a | Pair of 'a tree * 'a tree
和一个在二叉树中找到最大元素的函数
let rec tree_max t = match t with
| Leaf v -> v
| Pair (l,r) -> max (tree_max l) (tree_max r)
使上述函数尾递归
我试过了
let rec tree_max t acc= match t with
| Leaf v -> acc
| Pair (l,r) -> (max (tree_max l) (tree_max r))::ACC
我也试过了
let rec tree_max t acc= match t with
| Leaf v -> acc
| Pair (l,r) -> if (max (tree_max l) (tree_max l) = acc) then tree_max l acc else tree_max r acc
但它们都会产生语法错误。有人知道如何实现吗？
在伪代码中，您需要将模式匹配方程转换为正确的 match 语法，
tree_max (Leaf a) = a
| (Pair (l,r)) = go1 [l;r]
go1 (Pair (l,r)::ts) = go1 (l::r::ts)
| (Leaf a::ts) = go a ts
go a [] = a
| a (Leaf b::ts) = go (max a b) ts
| a (Pair (l,r)::ts) = go a (l::r::ts)
尾递归函数不一定总是调用自己；它可以调用另一个函数，这个函数又可以调用另一个函数；等等，只要所有调用都是tail.
go1 去最左边的叶子找到第一个值；然后 go 去做真正的工作。它的列表参数用作 yet-to-be-processed 节点的显式堆栈，因此当有 none 更多要处理时，处理必须停止。
TL;DR;这个问题比看起来要深一点，因为我不想做别人的功课，所以我决定写一篇关于将递归函数转换为尾递归函数的指南。结果比我想象的要大一点:)
（尾）递归终极指南
什么是尾递归？
确定一个函数何时是尾递归函数并不总是很容易。关键思想是，如果您在 递归调用之后做一些工作，那么您的函数不是 尾递归。而要使其成为尾递归，我们需要将足够的信息传递给递归调用，以便后者可以在没有我们干预的情况下计算结果，即函数的结果成为递归调用的结果。
这是一个简单的例子，一个计算列表长度的非尾递归length函数，
let rec length = function
| [] -> 0
| _ :: xs -> 1 + length xs
我们可以看到，在1 + length xs中，计算机首先计算length xs，然后等待它的结果只是加一。显然，我们可以将当前长度传递给递归调用并让基本情况 return 它，例如
let rec length acc = function
| [] -> acc
| _ :: xs -> length (acc+1) xs
因此，如您所见，诀窍是使用参数将信息传递给递归。一个直接的警告是我们现在有一个额外的参数，acc（代表 accumulator）。约定是在嵌套函数中向界面的最终用户隐藏此参数。我通常称这个函数为loop，例如
let length xs =
let rec loop acc = function
| [] -> acc
| _ :: xs -> loop (acc+1) xs in
loop 0 xs
在 length 示例中，我们能够将我们的算法从内存大小的 O(N) 改进为 O(1)。事实上，在非尾递归版本中，编译器创建了一个等于列表长度的堆栈调用链，每个槽存储子列表的长度。本质上，编译器构建了一个立即结果的单链表，然后使用 + 运算符将其缩减。这是一种非常低效的求和 n 数字的方法。
但有时，我们无法将递归参数减少为单个标量值，因此在堆栈中构建结果可能是有益的，请考虑将函数应用于每个元素的 map 函数一个列表并构建一个新的结果列表，
let rec map f = function
| [] -> []
| x :: xs -> f x :: map f xs
无法将此功能从 O(N) 减少到 O(1)，因为我们必须构建和 return 一张新地图。但是它消耗堆栈，这是一种稀缺1资源，不像常规的堆内存。所以让我们把这个函数变成尾递归函数。同样，我们必须将必要的信息传递给递归，以便当我们到达递归底部时我们可以构建答案，
let map f xs =
let rec loop acc = function
| [] -> List.rev acc
| x :: xs -> loop (x::acc) xs in
loop [] xs
如您所见，我们再次使用 acc 和嵌套循环函数来隐藏额外参数的技巧。与前面的示例不同，我们使用列表而不是整数来累加结果。由于我们是假装列表，我们最终得到的结果顺序颠倒了，所以我们必须在底部将它倒过来。我们可以改为附加到列表，但这会导致代码效率非常低，因为附加到单链表是一个 O(N) 操作，因此如果我们重复它 N 次，我们将得到O(N^2) 复杂度。
树上的递归
在上面的示例中，我们或多或少地选择了累加器，但是树状结构呢？对于树，我们必须在每个步骤上递归多次，例如，
let max_elt t =
let rec loop current_max t = match t with
| Leaf x -> max current_max x (* so far so good *)
| Tree (l,r) -> <??> in
loop <??> t
正如我们所见，将我们的函数转换为累加器样式的递归，显然选择累加器作为整数没有帮助。首先，我们现在必须对初始最大值做出可疑的选择，接下来，这是主要问题是我们必须分支 l 和 r 我们不能递归到他们都在同一个递归调用中......或者我们可以？
是的，我们可以，事实上，有多种解决方案。让我们从累加器式递归开始。因为我们想要递归几个子树（在我们的例子中是两个）并且我们想在一次调用中完成，所以我们必须将树的另一个分支传递到累加器中。所以累加器本身变成了我们还没有访问过的树的列表。这种方法的通用名称是“工作列表算法”，其关键思想是我们做尽可能多的工作并将其余的推入工作列表，例如，
let max_elt t =
let rec loop work t =
match t with
| Tree (l,r) -> loop (l::work) r
| Leaf x -> match work with
| [] -> x
| [Leaf x'] -> max x x'
| Tree _ as t' :: ts -> loop (t::ts) t'
| Leaf x' :: t :: ts -> loop (Leaf (max x x') :: ts) t in
loop [] t
哎呀，这看起来很复杂，比原来的堆栈消耗版本复杂得多。这是否值得，即我们是否显着提高了我们的表现？对于平衡树，不，我们处于同等水平——基于堆栈的版本消耗 O(depth(t)) 个堆栈槽，其中 depth 是树的深度。由于平衡二叉树（节点数）的大小 N 是 2^depth(t)，我们实际上消耗了 O(log(N))，这很好。我们的尾递归版本也消耗相同数量的堆。而对于一棵平衡树，我们不应该害怕消耗堆栈内存，因为在此之前我们会 运行 出堆内存（同样，要存储深度为 N 的树，我们需要 2^N 个元素，甚至如果堆栈被限制为 64 个槽，我们将能够处理大到 2^64 的树，这比任何计算机都多得多）。这就是为什么对于平衡树我们不需要担心尾递归并安全地使用正则递归，这更具可读性和效率。
但是如果树不平衡怎么办？即，当我们仅在左侧有子树而在右侧有叶子时。在这种极端情况下，我们的元素数量等于列表的深度。不幸的是，除非我们专门平衡我们的树，这是另一个有趣的话题，否则我们将经常以这种树结束，即尝试编写一个 of_list 函数来从列表中生成一棵树，赌注很高你最终进入了一个不平衡的列表。
对于不平衡的树，我们很容易得到堆栈溢出。但是上面这个函数，实在是太难理解了，也太难证明它终止了。
也许有办法让它尾递归并且易于理解？答案是肯定的，请继续阅读。
树上的递归（不涉及大脑）
好吧，下一个技巧有点难掌握，因为它涉及延续。如果你阻止你的大脑试图理解这个概念，那将是一个无需动脑筋的练习，仅仅是一种技术替代。但我们并不是在寻找捷径，所以让我们动动脑筋。
关键思想还是一样的，我们需要调用一次递归函数并传递给它一些递归完成工作所必需的值。在我们之前的示例中，我们将“要完成的工作”具体化为尚未处理的节点列表。但是如果我们将它表示为一个函数，它将接收中间结果并继续工作，即作为一个延续。约定是调用延续 k，但我们将其称为 return、
let max_elt t =
let rec loop t return =
match t with
| Leaf x -> return x
| Tree (l,r) ->
loop l @@ fun x ->
loop r @@ fun y ->
return (max x y) in
loop t (fun x -> x)
好的，首先，什么是@@，我们不是调用了两次循环吗？这是一个应用程序运算符，定义为 let (@@) f x = f x，因此如果我们重写我们的 loop 函数，我们可以看到我们确实每次调用一次，
let rec loop t return =
match t with
| Leaf x -> return x
| Tree (l,r) ->
loop l (fun x ->
loop r (fun y ->
return (max x y)))
所以，慢慢地，在Tree (l,r)的情况下我们调用loop l <cont1>并传递给它一个continuation（一个函数）接收子树l的最大值然后调用loop r <cont2>，它从r接收最大值，将它们结合起来找到两个最大值，然后使用延续return将它送回（向上）。
还不能完全确定这是尾递归吗？让我们尝试更详细地重写它，
let rec loop t return =
match t with
| Leaf x -> return x
| Tree (l,r) ->
let cont1 x =
let cont2 y = return (max x y) in
loop r cont2 in
loop l cont1
如您所见，所有对循环的调用都在尾部位置。但它是如何工作的？
这里的主要思想是每个延续都捕获一些信息，即在每个延续中我们都有一些从外部作用域捕获的自由变量，例如，cont1 捕获正确的树 r , 而cont2 捕获了上层continuation return, 这样最后我们就有了一个continuation 的链表。所以没有免费的奶酪，我们仍然使用 O(N) 内存槽，但由于延续存储在堆内存中，我们不再浪费宝贵的堆栈。
好的，现在是最后一步了，我们如何才能在不让大脑过度紧张的情况下应用这种技术，即，纯粹在句法上？为此，我们将使用 OCaml 的新功能，称为绑定运算符，它允许我们定义我们自己的 letXX 运算符，例如，
let (let@) = (@@)
这样 f (fun x -> <body>) 可以表示为 let@ x = f in <body> 并且使用这个运算符，我们可以表达我们的尾递归版本几乎与非尾递归版本相同，
let max_elt t =
let rec loop t return =
match t with
| Leaf x -> return x
| Tree (l,r) ->
let@ x = loop l in
let@ y = loop r in
return (max x y) in
loop t (fun x -> x)
与非尾递归版本比较，
let rec max_elt t =
match t with
| Leaf x -> x
| Tree (l,r) ->
let x = max_elt l in
let y = max_elt r in
max x y
所以我们可以建立一个简单的句法规则，
- 将额外的函数参数附加到参数列表
- 所有递归调用都应绑定
let@ - returned 值应通过
return传递，除非我们想更早地退出递归。
提前逃逸或短路
如果我们不使用return在递归中向上传递值呢？在那种情况下，我们的结果立即成为整个顶级调用的结果，因此我们可以在找到一个元素时缩短我们的搜索并且不检查其他元素。例如，这里是我们如何测试我们的树的元素成员资格，
let has t needle =
let rec loop t return = match t with
| Leaf x -> x = needle || return ()
| Tree (l,r) ->
let@ () = loop l in
loop r return in
loop t (fun () -> false)
您可以看到，在 let@ () = loop l 中，我们甚至不用费心从子树搜索中 return 真或假。我们仅使用函数 return 告诉我们的事实作为元素不存在于左子树中的证据，因此我们需要检查右子树。
Continuations 是函数式语言的一个非常强大的特性，你可以用它们来实现美妙的东西，比如可变参数函数、非确定性计算、轻松表达回溯等等。但这是一个不同的话题，我希望我们最终会探讨。
1)稀缺与否取决于架构、操作系统及其配置。在现代 Linux 上，您可以通过设置 ulimit -s unlimited 使堆栈大小不受限制，根本不用担心堆栈溢出。在其他操作系统上，最大堆栈大小有硬性限制。