用SML查找树中的字符

Question

我对SML很陌生，我想把我的注意力集中在函数式编程上。我希望有一个函数，它接受树t和字符c，如果树包含该字符，则返回true或false。

我要实现的算法是：

1. 如果叶为空返回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) 

Answer 2

您可以再次将该函数概括为

fun any p Leaf = false
  | any p (Node (left, x, right)) =
      p x orelse any p left orelse any p right

fun contains c t = any (fn x => c = x) t