我目前正在为函数式编程考试学习OCaml，在这个练习中，我很难遵循这个递归函数的步骤。任务是在一棵n元的int树中找到代价最高的叶子(叶子的代价由到达叶子的路径上的整数和给出)。
这是类型定义:
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)声明有点困惑。
给定一棵树，leaf_cost返回一对(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)，跟踪导致该代价的子树中的叶子。