字体不匹配的问题

Question

做一个家庭作业，本质上需要一棵树，树的声明是：

datatype a BinTree = 
Leaf of a
| Node of a BinTree * a BinTree;

并返回树的整数高度元组和存储在树最深处的值列表。

fun deepest tree = 
case tree of 
Leaf(n) => [n]
| Node(l, r) => if #1(deepest l) > #1(deepest r) then ((#1(deepest l) + 1), #2(deepest l)) else
if #1(deepest l) < #1(deepest r) then ((#1(deepest r) + 1), #2(deepest r)) else
(1, #2(deepest l) @ #2(deepest r)); 

尝试测试此代码时，我出现以下错误消息：

stdIn:43.1-47.35 Error: types of rules don't agree [tycon mismatch]
earlier rule(s): 'Z BinTree -> 'Z list
this rule: 'Z BinTree -> [+ ty] * 'Y list
in rule:
Node (l,r) =>
if (fn <rule>) (deepest <exp>) > (fn <rule>) (deepest <exp>)
then (<exp> <exp> + 1,(fn <rule>) (deepest <exp>))
else if <exp> <exp> < <exp> <exp>
then (<exp> + <exp>,<exp> <exp>)
else (1,<exp> @ <exp>)
stdIn:21.2-47.35 Error: right-hand-side of clause doesn't agree with 
function result type [type mismatch]
expression:  'Z list
result type:  {1:[+ ty], 2:'X list; 'Y}
in declaration:
deepest =
(fn tree =>
(case tree
of <pat> => <exp>
| <pat> => <exp>))
stdIn:1.2-47.35 Error: unresolved flex record (need to know the names of ALL 
the fields
in this context)
type: {1:[+ ty], 2:'Y list; 'Z}

虽然我知道这是一种类型冲突，但我找不到冲突是什么，也找不到如何解决它。任何帮助将不胜感激。

Answer 1

earlier rule(s): 'Z BinTree -> 'Z list

来自叶子大小写([n](，这使它成为从树到列表的函数。

而这个：

this rule: 'Z BinTree -> [+ ty] * 'Y list

来自节点大小写，使其成为从树到"支持加法的类型"和列表对的函数。

其余错误是由于 SML 无法推断#1和#2在存在该冲突时的含义引起的。

你的基本情况是错误的——它应该是一对，而不是一个列表。
该对中的深度应为 1，如果两个子树的深度相等，则深度不应为 1。

在最坏的情况下，您还要为每个子树计算三次最深的值，在最佳情况下计算两次。
最好只对每个子树递归一次。

像这样：

fun deepest (Leaf n) = (1, [n])
| deepest (Node (l, r)) =
case deepest l of (dl, ll) =>
case deepest r of (dr, lr) =>
if dl > dr then (dl + 1, ll)
else if dr > dl then (dr + 1, lr)
else (dl + 1, ll @ lr)

Answer 2

虽然我也更喜欢像 molbdnilo 这样的大小写来编写这个函数，但这里有一个使用let-in-end的例子来证明当结果是乘积(元组(时它们都可以使用。由于在if-then-else中有三种情况，具有三种不同的结果(dl > dr，dr > dl和dl = dr(，使用Int-compare可能更可取：

fun deepest (Leaf n) = (1, [n])
| deepest (Node (l, r)) =
let val (lcount, ls) = deepest l
val (rcount, rs) = deepest r
in case Int.compare (lcount, rcount) of
GT => (lcount + 1, ls)
| LT => (rcount + 1, rs)
| EQ => (lcount + 1, ls @ rs)
end