在sml中，为什么会产生错误:语法错误: deleting In IF

Question

我正在制作一个函数来确定树是否平衡。

fun balanced(tree) =
  let 
    fun size tree =
      case tree of
           Lf => 0
         | Br(xs,ys,zs) => 1 + size ys + size zs
    fun depth tree =
      case tree of
           Lf => 0
         | Br(xs,ys,zs) =>
            let val l_count = 1 + depth ys
                val r_count = 1+ depth zs
            in
              if l_count > r_count then l_count else r_count
            end
  in
    if size(ys) = size(zs) andalso depth(ys) = depth(zs) then true
    else if tree=Lf then true
    else false
  end;

但它会产生以下错误：

stdIn:829.18-829.20 Error: unbound variable or constructor: zs
stdIn:829.9-829.11 Error: unbound variable or constructor: ys
stdIn:829.48-829.50 Error: unbound variable or constructor: zs
stdIn:829.36-829.38 Error: unbound variable or constructor: ys

Answer 1

在in和end之间

  in
    if size(ys) = size(zs) andalso depth(ys) = depth(zs) then true
    else if tree=Lf then true
    else false
  end;

您可以使用以前从未定义过的ys和zs。depth和size函数中的ys和zs对于这些函数是本地的，对于balanced是不可见的。

Answer 2

您尚未提供此函数所操作的数据类型。我假设它看起来像这样：

datatype 'a binary_tree = Lf | Br of 'a * 'a binary_tree * 'a binary_tree

您会得到未绑定的变量错误，因为代码

if size(ys) = size(zs) andalso ...

在其作用域中没有这样的变量。这些变量仅在helper函数的作用域中可用。这里有一些提示：

1. 不要将变量命名为xs、ys和zs，因为xs实际上是驻留在分支中的值，而ys和zs实际上是分支的左子树和右子树。更好的名称可以是x (如果你不使用它，也可以是_ )，left和left Int.max (x, y)，而不是if x > y then x else y。

类似地，if foo then true else false等同于foo。

因此，您不需要在balanced.

• Perform的主体中使用if-then-else模式直接在函数参数中匹配。

• 没有必要知道子树(size)中的元素数量来确定它是否平衡。它只需要知道树的高度/深度(depth).

• Move这个函数的辅助函数。

它们本身就很有用。

fun size Lf =0| size (Br (_，left，right)) =1+ size left + size right fun depth Lf =0| depth (Br (_，left，right)) =1+ Int.max (depth left，depth right)

• Write balanced in a declarative way：空树(Lf)是平凡平衡的。如果左子树是平衡的，右子树是平衡的，并且左右子树的深度差不大于1，则非空树(Br ...)是平衡的。

fun balanced Lf = true | balanced (Br (_，left，right)) = balanced left和Br(Br(_，left，right ))= balanced left和Br(Br( ...the，left，right))也是平衡的‘abs’(解体) 'depth left‘和'depth right’的差异不超过1...

• 这个解决方案遍历了很多次树:首先是balanced，然后是depth。您可以为本练习编写一个解决方案，通过返回一个元组(is_subtree_balanced, subtree_height)来只遍历树一次。

fun balanced_helper Lf = (true，0) | balanced_helper (Br (_，left，right)) = let val (is_left_balanced，left_height) = balanced_helper left in ...we如果左子树不平衡，可以在此处停止...如果右子树不平衡，让val (is_right_balanced，right_height) = balanced_helper在...we中停止......otherwise：(true，1+ Int.max(left_height，right_height))...end end fun平衡树= #1 (balanced_helper树)