How to implement a dictionary as a function in OCaml?

Question

I am learning Jason Hickey's Introduction to Objective Caml.

---

Here is an exercise I don't have any clue

---

First of all, what does it mean to implement a dictionary as a function? How can I image that?

Do we need any array or something like that? Apparently, we can't have array in this exercise, because array hasn't been introduced yet in Chapter 3. But How do I do it without some storage?

So I don't know how to do it, I wish some hints and guides.

Answer 1

I think the point of this exercise is to get you to use closures. For example, consider the following pair of OCaml functions in a file fun-dict.ml:

let empty (_ : string) : int = 0
let add d k v = fun k' -> if k = k' then v else d k'

Then at the OCaml prompt you can do:

# #use "fun-dict.ml";;
val empty : string -> int = 
val add : ('a -> 'b) -> 'a -> 'b -> 'a -> 'b = 
# let d = add empty "foo" 10;;
val d : string -> int = 
# d "bar";;  (* Since our dictionary is a function we simply call with a
                  string to look up a value *)
- : int = 0   (* We never added "bar" so we get 0 *)
# d "foo";;
- : int = 10  (* We added "foo" -> 10 *)

In this example the dictionary is a function on a string key to an int value. The empty function is a dictionary that maps all keys to 0. The add function creates a closure which takes one argument, a key. Remember that our definition of a dictionary here is function from key to values so this closure is a dictionary. It checks to see if k' (the closure parameter) is = k where k is the key just added. If it is it returns the new value, otherwise it calls the old dictionary.

You effectively have a list of closures which are chained not by cons cells by by closing over the next dictionary(function) in the chain).

Extra exercise, how would you remove a key from this dictionary?

---

Edit: What is a closure?

A closure is a function which references variables (names) from the scope it was created in. So what does that mean?

Consider our add function. It returns a function

fun k' -> if k = k' then v else d k

If you only look at that function there are three names that aren't defined, d, k, and v. To figure out what they are we have to look in the enclosing scope, i.e. the scope of add. Where we find

let add d k v = ...

So even after add has returned a new function that function still references the arguments to add. So a closure is a function which must be closed over by some outer scope in order to be meaningful.