Функция SML для возврата списка элементов из дерева вызывает исключение - PullRequest
Новая
       21

Функция SML для возврата списка элементов из дерева вызывает исключение

2 голосов
/ 06 октября 2010

У меня есть задание 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 принимает функцию bool и возвращает все узлы, которые удовлетворяют этой функции, в форме исключения. Я знаю, почему мой код не работает, потому что в оригинале (повышенный ответ) будет (повышенный ответ), но в любом случае это не компилируется. Мне было интересно, что я должен сделать, чтобы это исправить. Я не могу вызвать вспомогательную функцию, которая получает все элементы, а затем просто вызвать исключение, однако я должен использовать исключение, несущее значение. Я также должен быть в состоянии вернуть все элементы по порядку.

1 Ответ

2 голосов
/ 10 октября 2010

Вы не цитируете сообщения об ошибках и не говорите, какой компилятор вы используете.Вот что я получаю из 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, который приходитот Node и должно быть int.Третья ошибка, вероятно, является проблемой старшинства: вы можете увидеть, как компилятор проанализировал ваше выражение, и это, вероятно, не то, что вы хотели.(Но то, что вы намеревались, не имеет смысла, как я объясню ниже.)

Вторая и четвертая ошибка связаны с тем, что вы путаете конструктор :: ("cons"), который добавляет элементв начале списка с оператором @ («добавление»), который объединяет два списка.

Теперь я возвращаюсь к исключению 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
...