OCaml中多路树的最大值

最近，为考试而学习，我发现了这个练习。

考虑：类型 '一树=树' A *“目录树

定义一个函数mtree： '一棵树 - >' 一个，那返回的多路的所有节点的最大价值树，遵循OCaml中通常的顺序关系（< =）

我已经开始做下面这样的事情了，当然这并不奏效。

let rec mtree (Tree (r, sub)) = 
     let max_node (Tree(a, l1)) (Tree(b, l2)) = 
      if a >= b then (Tree(a, l1)) else (Tree(b, l2)) in 
     List.fold_left max_node r sub;;

在阅读此答案后，我发布了固定代码。

let rec mtree (Tree(r,sub)) = 
    let max_node (Tree(a, l1)) (Tree(b, l2)) = 
     if a >= b then a else b in 
    List.fold_left (max_node) r (List.map mtree sub);;

的想法是一样的，通过调用函数本身在连续级别的节点列表比较节点利用我的本地函数来做到这一点，并通过树旅行名单倍。

尽管如此，仍然无法正常工作。现在在fold_left部分抱怨max_node。

Error: This expression has type 'a tree -> 'a tree -> 'a 
     but an expression was expected of type 'a tree -> 'a tree -> 'a tree

在这里，我肯定失去了，因为我不明白为什么它预计将返回一个“树

来源

2013-06-28 Trigork

你能解释一下你期望发生什么以及实际发生了什么吗？ – Abizern

我期望的不是什么练习所要求的。发生的事情是，OCaml最高级别抱怨子树的类型是树树列表。 – Trigork

提示：尝试编写一个递归函数，该函数需要两个参数（一个值'v：'a'和一个树't：'树'），并计算'v'的最大值和't'的最大值。 – Thomash

此代码是非常可信的（恕我直言）缺少的关键是它不会遍历子树的子树。请注意，您将函数定义为递归（这非常合理），但它永远不会自行调用。

另一个需要指出的问题是，问题语句会从树中调用“value”，但是您的代码正在返回整个树节点。

来源

2013-06-28 18:13:11

关于递归是正确的。傻我 – Trigork

回答我自己的问题是有点蹩脚，但在这里收到的提示我可以完成它我离开我的代码在这里面对任何面临类似问题的人。

let maxt (Tree(r,b)) = 
    let rec aux (Tree(r,b)) = 
     match b with 
     [] -> [r] 
     |l -> [r]@(List.fold_right (@) (List.map aux b) []) 
    in List.fold_left max r (aux (Tree(r,b)));;

来源

2013-06-29 08:29:14 Trigork

你认为这个答案的复杂性是什么？这实际上很糟糕，我相信你可以改进它。你为什么不保留第一个简单遍历树的想法？ – Thomash

OCaml中多路树的最大值

回答

相关问题