how to partially implement function in sml

Question

I'm working through the book Modern Compiler Implementation in ML, and learning sml at the same time.

I'm stumped by one of the exercises (1.1.b) in the first chapter. We are asked to implement a binary tree which maintains key/value pairs, with keys being strings, and values being a parameterized type. My data type is defined as follows

type key = string
datatype 'a tree = LEAF | TREE of 'a tree * key * 'a * 'a tree

We are asked to implement a lookup function whose type is 'a tree * key -> 'a. I don't know how to implement this function because I don't know what to return when the tree is a LEAF. There is no default value of 'a. The instructions in the book don't say way to do if the key is not found, but it insists the function MUST return type 'a.

Is this just an error in the book, or is there a correct way to do this in sml?

I toyed with trying to raise an exception in this case, but the compiler apparently won't let me throw an exception without catching it.

If I were implementing this in Scala, I'd change the return type to Option[A] and return None if the key is not found; or in Common Lisp, I'd pass a continuation to call with the found value, and then simply not call the continuation if the key is not found.

Here is my code, which is not yet working.

(* page 12, exercise 1.1 b *)
type key = string
datatype 'a tree = LEAF | TREE of 'a tree * key * 'a * 'a tree

val empty = LEAF

fun insert(key,value,LEAF) = TREE(LEAF,key,value,LEAF)
  | insert(key,value,TREE(l,k,v,r)) =
    if key<k
    then TREE(insert(key,value,l),k,v,r)
    else if key>k
    then TREE(l,k,v,insert(key,value,r))
    else TREE(l,key,value,r)

fun lookup(LEAF,key) =  (* !!!HELP!!!  I don't know what to do in this case *)
  | lookup(TREE(l,k,v,r),key) = if k=key
                                then v
                                else if key<k
                                then lookup(l,key)
                                else lookup(r,key)

val t1 = insert("a",1,empty)
val t2 = insert("c",2,t1)
val t3 = insert("b",3,t2)
   ;

     lookup(t3,"a");
     lookup(t3,"b");
     lookup(t3,"c");
     lookup(t3,"d");

BTW, I don't understand why emacs sml-mode insists on indenting the calls to lookup.

Answer 1

You can definitely change lookup to use 'a option.

Here is a basic dictionary implementation that uses an opaque module and type parameters rather than module parameters. The example you derive from uses a mixture where key is a module parameter and 'a being the value is still polymorphic. This is generally a good idea because you have more flexibility with regards to implementation. But since you're just using a list as dictionary, you can use ''key to denote a type parameter that is comparable for equality. (If you wanted a more efficient representation, such as a tree or a hashmap, you'd need a bigger interface.)

signature DICT = sig
  type (''key, 'value) dict
  val empty : (''key, 'value) dict
  val insert : ''key -> 'value -> (''key, 'value) dict -> (''key, 'value) dict
  val lookup : ''key -> (''key, 'value) dict -> 'value option
end

structure Dict :> DICT = struct
  type (''key, 'value) dict = (''key * 'value) list
  val empty = []
  fun insert k v [] = [(k, v)]
    | insert k v ((k2,v2)::dict) =
        if k = k2
        then (k,v)::dict
        else (k2,v2)::insert k v dict
  fun lookup k dict = Option.map #2 (List.find (fn (k2,v2) => k = k2) dict)
end

Now,

- val demo = Dict.lookup "foo" (Dict.insert "foo" 42 Dict.empty)
> val demo = SOME 42 : int option

---

val t1 = insert("a",1,empty)
val t2 = insert("c",2,t1)
val t3 = insert("b",3,t2)
   ; X

     lookup(t3,"a");
     lookup(t3,"b");
     lookup(t3,"c");
     lookup(t3,"d");

BTW, I don't understand why emacs sml-mode insists on indenting the calls to lookup.

That is because sml-mode thinks the ; is the expression operator and not the declaration separator. I've placed an X where, if it were the expression operator, it would be natural to place an expression here. And making a linebreak, it would be natural to place subsequent expressions on the same indentation point.

Emacs sml-mode uses only the preceding line to determine indentation level which makes it somewhat simplistic. You can avoid fighting the indentation here by either prefixing all your declarations with val ... =, or by placing the ; in a less arbitrary way, e.g.

...
val t3 = insert ("b", 3, t2)
val L1 = lookup(t3,"a")
val L2 = ...

or

...
val t3 = insert ("b", 3, t2)
;lookup(t3,"a");
;lookup(t3,"b");

The idea behind ;s on both sides here is that you're allowed to repeat arbitrarily many ;s when we are talking about the declaration separator (and not the expression operator), and so, since ;s are not required to terminate val ... declarations, these lines are not vulnerable to changing the context before or after, much like val x = .... This style only really makes sense as long as you're only evaluating your SML code as a script / in a REPL. Otherwise you probably want to name your bindings or use val _ = ... if you are only interested in the side-effect.