难以分析函数的递归步骤

Question

我目前正在为函数式编程考试学习 OCaml，在尝试按照本练习中的递归函数步骤进行操作时遇到了一些困难。任务是在 int N 叉树中找到最昂贵的叶子（叶子成本由到叶子的路径上的整数之和给出）。

这是类型定义：

type 'a ntree = Ntree of 'a * 'a ntree list

这是练习的辅助功能

let rec maxpair = function
  | [] -> failwith "empty list"
  | [(x, y)] -> (x, y)
  | (x, y) :: (a, b) :: rest -> 
      if y > b then maxpair ((x, y) :: rest) 
      else maxpair ((a, b) :: rest)

最后是最终函数

let rec leaf_cost = function
  | Ntree (x, []) -> (x, x)
  | Ntree (x, tlist) -> 
      let (y, c) = maxpair (List.map leaf_cost tlist)
      in 
      (y, c + x)

这是练习的答案，意味着它有效。但是我在尝试分析函数中的每个递归步骤时遇到了麻烦，特别是因为我对 let (y, c) ... in (y, c + x) 声明有点困惑。

Answer 1

给定一棵树，leaf_cost returns 一对 (v, c) 是具有最大成本 v 的叶节点的值，并且该成本 c.

在基本情况下，当没有子节点时，值为x，其成本也为x。

在一般情况下，节点由整数 x 和子节点列表 children（又名 tlist）组成。

List.map leaf_cost children

上面的表达式是一对列表，每一对都是以每个子节点为根的相应子树中的最大叶子及其相关成本。

一般来说，可能有多个叶子具有相同的成本，但您的问题忽略了这一点，并以实现定义的方式选择迄今为止所有成本中具有最大成本的一对。

这是通过调用 maxpair 完成的，它给出一对 (y, c)，其中 y 是递归获得的所有对中具有最大成本 c 的第一片叶子.

已知在所有子树中，(y, c)是一个成本为c的叶子，而你当前节点的权重为x，当前节点的成本为c + x.这就是为什么一般情况下的返回值是 (y, c+x)，跟踪导致此成本的子树中的叶子。

难以分析函数的递归步骤

having difficulties analyzing recursive steps of a function

tree

recursion

ocaml

functional-programming