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

但它们都会产生语法错误。有谁知道如何实现这一点吗？

推荐答案

tl；dr；这个问题比看起来要深一些，因为我不想让别人做作业，所以我决定写一篇关于如何将递归函数转换为尾递归函数的指南。结果比我预期的要大一点：)

(尾部)递归的最终指南

什么是尾递归？

要识别函数何时是尾递归、何时不是尾递归并不总是很容易。关键思想是，如果您在递归调用之后做了一些工作，那么您的函数就是而不是尾递归函数。要使其尾递归，我们需要将足够的信息传递给递归调用，以便后者可以在没有我们干预的情况下计算结果，即函数的结果成为递归调用的结果。

这里有一个简单的示例，一个计算列表长度的非尾递归length函数，

let rec length = function
  | [] -> 0
  | _ :: xs -> 1 + length xs

我们可以看到，在1 + length xs中，计算机首先对length xs求值，然后等待其结果将其加1。显然，我们可以将当前长度传递给递归调用，并让基例返回它，例如

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)，因为我们必须构建并返回一个新映射。但它消耗堆栈，而堆栈是一种稀缺的¹资源，与常规的堆内存不同。所以让我们把这个函数变成尾递归函数。同样，我们必须沿着递归向下传递必要的信息，这样当我们到达递归底部时，我们就可以构建答案，

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

正如我们所看到的，将我们的函数转换为累加器样式的递归(显然将累加器选择为整数)没有任何帮助。首先，我们现在必须对初始最大值NEXT做出一个可疑的选择，这是主要的问题是我们必须对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)

好的，首先，什么是@@，我们不是要调用loop两次吗？这是一个应用程序操作符，被定义为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>并向其传递一个Continue(函数)，该函数接收子树l的最大值，然后调用loop r <cont2>，loop r <cont2>从r接收最大值，将它们组合以找到2中的最大值，然后使用Continuereturn将其发回(向上)。

仍然不能完全确定这是尾递归吗？让我们试着把它重写得更详细，

  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捕获上层延续return，因此最终我们有一个连续的链表。所以没有空闲的奶酪，我们仍然使用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

这样我们就可以构建一条简单的语法规则

0. 将额外的函数参数追加到参数列表
1. 所有递归调用都要绑定let@
2. 返回值应通过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中，我们甚至没有费心从子树搜索中返回TRUE或FALSE。我们使用返回给我们的函数作为元素不在左子树中的证据，因此我们需要检查右侧的元素。

延续是函数式语言的一个非常强大的特性，您可以用它们来实现一些奇妙的功能，比如各种函数、非确定性计算、轻松地表示回溯等等。但这是一个不同的话题，我希望我们最终会探讨这个话题。

---

¹⁾是否缺少取决于体系结构、操作系统及其配置。在现代Linux上，您可以通过设置ulimit -s unlimited使堆栈大小不受限制，并且根本不用担心堆栈溢出。在其他操作系统上，对最大堆栈大小有硬限制。

这篇关于OCaml中二叉树的尾递归最大元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！