2

我有一个 SML 任务，其中一个问题是实现一个功能

findAll : (int -> bool) -> binary search tree -> int list

到目前为止，我有以下内容： 

datatype 'a tree = Empty | Node of (int * 'a tree  * 'a tree) 

exception answer of int list

fun findAll f Empty = raise answer []
  | findAll f (Node(x, l, r)) = 
    if (f x) then raise answer(x)::(findAll f l)::(findAll f r)
    else 
        (findAll f l)::(findAll f r)

基本上，findAll接受一个布尔函数并以异常的形式返回满足该函数的所有节点。我知道为什么我的代码不起作用，因为在原始（提高答案）中会有一个（提高答案），但无论哪种方式，这都不会编译。我想知道我应该怎么做才能解决这个问题。我不能调用获取所有元素的辅助函数，然后只调用异常，但是我应该使用携带值的异常。我也应该能够按顺序返回所有元素。

4

1 回答 1

2

您不会引用错误消息或说出您正在使用哪个编译器。这是我从 SML/NJ 得到的：

3867615/john316.sml:7.25-7.64 Error: operator and operand don't agree [tycon mismatch]
  operator domain: int list
  operand:         int
  in expression:
    answer x
3867615/john316.sml:7.25-7.64 Error: operator and operand don't agree [circularity]
  operator domain: 'Z * 'Z list
  operand:         'Z * 'Z
  in expression:
    (findAll f) l :: (findAll f) r
3867615/john316.sml:7.25-7.64 Error: argument of raise is not an exception [tycon mismatch]
  raised: _ list
  in expression:
    raise (answer x :: (findAll <exp>) l :: (findAll <exp>) r)
3867615/john316.sml:9.9-9.37 Error: operator and operand don't agree [circularity]
  operator domain: 'Z * 'Z list
  operand:         'Z * 'Z
  in expression:
    (findAll f) l :: (findAll f) r

第一个错误应该相当清楚：answer被声明为期望一个int list参数，但answer x使用x来自 aNode并且必须是 a 的 an int。第三个错误可能是优先级问题：您可以看到编译器如何解析您的表达式，这可能不是您想要的。（但你的意图没有意义，我将在下面解释。）

第二个和第四个错误是由于您混淆了::(“cons”) 构造函数，该构造函数在列表的前面添加一个元素，而@(“append”) 运算符则连接两个列表。

现在我回到answer例外。它是干什么用的？您的函数必须找到所有出现的事件，因此它必须遍历整个树。没有任何情况需要您提前返回。因此，您不需要例外。您基本上已经得到了正确的算法（在空树中，没有匹配项，因此返回空列表；在节点中，将匹配项添加到递归调用的结果（如果存在）），只是不要使事情复杂化。

进行两次更正，我们得到以下代码（编译）：

fun findAll f Empty = []
  | findAll f (Node(x, l, r)) = 
    if f x then x :: findAll f l @ findAll f r
    else findAll f l @ findAll f r
于 2010-10-10T11:42:37.810 回答