使用 SML 在树中查找字符

Question

我是 SML 的新手，正在尝试全神贯注于函数式编程。我想要一个接受树 t 和字符 c 和 returns true 或 false 的函数，如果树包含字符。

我要实现的算法是：

if leaf 为 null return false,
else if character is in leaf return true,
return左树结果或右树结果

这是我的树数据类型

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。）

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

您遇到的另一个问题是 "leaf is null" 规则 – 叶子不能 "null"。
我怀疑这就是让你误入歧途的原因，因为你的第一个子句的结果是 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

使用 SML 在树中查找字符

Find character in tree with SML

algorithm

functional-programming

sml