SML Error:Types of if branches do not agree

Question

我正在尝试查找某个元素是否是集合的一部分。这是我的功能：

fun elementOf(x:int, (nil:int list, nil:bool list)) = nil
  | elementOf(x, (y::ys, z::zs)) = if x = y then z else elementOf(x, (ys, zs));

所以如果我调用 elementOf(2, ([2,7,4], [false,true,false])) 它将 return false.

但是，我收到错误消息：

Error: types of if branches do not agree [tycon mismatch]
then branch: bool
else branch: 'Z list
in expression: if x = y then z else elementOf(x,ys,zs))

什么是“Z 列表”以及如何修复此错误？

Answer 1

What is a 'Z list?

A 'Z 列表是标准 ML 在基本情况下推断 nil 的 return 类型的方法。 nil 可以是任何类型的列表，因为它是空的。 'Z 是类型变量。

How do I fix this error?

问题是 elementOf 有时 return nil 有时 true / false。通过将 base-case 更改为 false，该函数将起作用，使得不在列表中的元素也不在集合中：

fun elementOf(x:int, (nil:int list, nil:bool list)) = false
  | elementOf(x, (y::ys, z::zs)) = if x = y then z else elementOf(x, (ys, zs));

但可能没有充分的理由存储不在集合中的元素，而不是将它们丢弃。稍微更有效的表示就是成员列表：

fun elementOf (x, nil : int list) = false
  | elementOf (x, y::ys) = x = y orelse elementOf (x, ys)

或使用 built-in 列表组合器 List.exists:

fun elementOf x xs = List.exists (y => x = y) xs

或写成point-free style：

fun curry f x y = f (x, y)
val elementOf = List.exists o curry op=

更好的一个依赖于二叉树：

data binTree = Empty
             | Node of binTree * int * binTree

fun elementOf (x, Empty) false
  | elementOf (x, Node (left, y, right)) =
    (case Int.compare (x, y) of
          LESS => elementOf (x, left)
        | EQUAL => true
        | GREATER => elementOf (x, right))

Answer 2

编译器已确定“then”分支必须 return 类型 bool，但“else”分支必须 return 类型 'Z list。 'Z list 类型的意思是“一个列表，其元素可以是任何东西”。以 ' 开头的类型是类型变量，如果编译器确定并非所有类型都是可能的，则稍后可能会被另一种类型替换，或者如果类型可以是多态的，则可能最终保留下来。

“then”分支必须是布尔值，因为它是 z，给定匹配构造中的模式是上面模式指定的类型为 bool list 的列表的第一个元素. “else”分支必须是一个列表，因为它是对 elementOf 的调用，并且模式匹配中的第一个 case 有 elementOf return nil 这是一个列表（与对元素的类型没有限制：由于空列表没有元素，它的元素可以说是您愿意选择的任何类型）。

鉴于函数的用途，它应该 return 一个布尔值，因此在第一种情况下 returning nil 没有意义。空列表编码一个没有元素的集合，所以你应该 return false 那里。

Answer 3

您似乎将集合表示为 (U,V)，其中 U 是通用集合，V 是布尔向量（均表示为相同长度的列表）。这当然是合理的，尽管正如@SimonShine 在他的出色回答中所暗示的那样，这并不是最有效的。

使用您的表示，您可以使用模式匹配定义您的函数，让 SML type-inference 为其推断最通用的类型：

fun elementOf (x,([],[])) = false
|   elementOf (x,(y::ys,z::zs)) = if x = y then z else elementOf (x,(ys,zs));

推断类型为

''a * (''a list * bool list) -> bool

''a 指的是任何 相等类型 - 因此您的函数可用于表示任何类型的集合（只要该类型具有相等的概念) 而不仅仅是整数。例如，elementOf ("cat",(["the","cat","in","hat"],[true,true,false,true])) 的计算结果为 true。

在SML/NJ中定义给出警告：Warning: match nonexhaustive。这是因为定义假定列表的长度相同。您可以保持代码不变——如果您的布尔列表与通用集的长度不同，函数应该可能会崩溃，或者您可以决定 false是合理的默认值，修改定义为：

fun elementOf (x,([],_)) = false
|   elementOf (x, (_,[])) = false
|   elementOf (x,(y::ys,z::zs)) = if x = y then z else elementOf (x,(ys,zs));

SML Error:Types of if branches do not agree

SML Error:Types of if branches do not agree

sml

smlnj