sml function that returns a list using exceptions

Question

Hello,

I have an sml assignment and one of the questions is to implement a function:
findAll (int -> bool) -> binary search tree -> int list

I have the following so far:

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)

basically, findAll takes in a bool function and returns all the nodes that satisfy this function in the form of an exception. I know why my code isn't working, because there will be a (raise answer) inside the original (raise answer) but either way this isn't compiling. I was wondering what should I do to fix this. I can't call a helper function that gets all the elements and then just call the exception, I should however use the value carrying exception. I should also be able to return all the elements in order.

Thank you

Answer 1

You don't quote the error messages or say which compiler you're using. Here's what I get from 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

The first error should be fairly clear: answer is declared as expecting an int list argument, but answer x uses an x which comes from a Node and must be an int. The third error is probably a precedence problem: you can see how the compiler parsed your expression, and it's probably not what you intended. (But what you intended doesn't make sense, as I'll explain below.)

The second and fourth error are due to your confusing the :: (“cons”) constructor, which adds an element at the front of a list, with the @ (“append”) operator, which concatenates two lists.

Now I'm coming back to the answer exception. What is it for? Your function must find all occurrences, so it has to traverse the whole tree. There is no circumstance which would require you to return early. Thus you don't need an exception. You've basically got the algorithm right (in an empty tree, there is no match so return the empty list; in a node, prepend the match to the result of the recursive call if present), just don't complicate things.

Making the two corrections, we get the following code (which compiles):

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