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 回答