使用SML查找树中的字符

Question

我是SML的新手，正在尝试把我的头放在函数式编程上。我想要一个接受树t和字符c的函数，如果树包含字符，则返回true或false。

我要实现的算法是：

1. 如果叶子为null，则返回false，

2. 否则，如果字符在叶子中，则返回true，

3. 左树的返回结果或右树的结果

这是我的树数据类型

datatype 'a tree =
    Leaf of 'a
  | Node of 'a tree * 'a * 'a tree;

这是功能

fun containsChar (Leaf t, c: char) = false 
  | containsChar (Node (left, t, right)) = 
    if t = c then true else false
  | containsChar (Node (left, t, right)) = (containsChar left) <> (containsChar right);

我得到Unbound value identifier "c".这是为什么？

Answer 1

在该子句中没有所谓的“ c”。叶子的情况下有一个“ c”，但这是完全不同的情况。在其他情况下，您忘记了该参数。（并且if t = c then true else false等效于t = c。）

您在第二和第三子句中也具有相同的模式，这是行不通的。

您遇到的另一个问题是“叶子为空”规则-叶子不能为“空”。我怀疑这是使您误入歧途的原因，因为第一个子句的结果是false，即使该参数显然是现有的叶子，而第二个子句显然也不是叶子，但看起来像您的第二条规则。

您的规则应为：

[仅当且仅当一棵树包含一个字符

• 它是叶子中的值，或
• 它是节点中的值，或
• 它包含在节点的子树中。

在ML中（由于似乎是任意的，所以删除了对char Tree的限制），

fun contains (Leaf t, c) = t = c 
  | contains (Node (left, t, right), c) = t = c
                                       orelse contains(left, c)
                                       orelse contains(right, c)