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.

Answer 2

I'm also struggling with this problem. Here's my solution and it works for the cases listed in the textbook...

An empty dictionary simply returns 0:

let empty (k:string) = 0

Find calls the dictionary's function on the key. This function is trivial:

let find (d: string -> int) k = d k

Add extends the function of the dictionary to have another conditional branching. We return a new dictionary that takes a key k' and matches it against k (the key we need to add). If it matches, we return v (the corresponding value). If it doesn't match we return the old (smaller) dictionary:

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

You could alter add to have a remove function. Also, I added a condition to make sure we don't remove a non-exisiting key. This is just for practice. This implementation of a dictionary is bad anyways:

let remove (d: string -> int) k =
    if find d k = 0 then
        d
    else
        fun k' ->
            if k' = k then
                    0
                else
                    d k'

I'm not good with the terminology as I'm still learning functional programming. So, feel free to correct me.

Answer 3

I thought it might be worth to add that functions in OCaml are not just pieces of code (unlike in C, C++, Java etc.). In those non-functional languages, functions don't have any state associated with them, it would be kind of rediculous to talk about such a thing. But this is not the case with functions in functional languages, you should start to think of them as a kind of objects; a weird kind of objects, yes.

So how can we "make" these objects? Let's take Jeffrey's example:

let bump f k = 
  fun n ->
    k + f n

Now what does bump actually do? It might help you to think of bump as a constructor that you may already be familiar with. What does it construct? it constructs a function object (very losely speaking here). So what state does that resulting object has? it has two instance variables (sort of) which are f and k. These two instance variables are bound to the resulting function-object when you invoke bump f k. You can see that the returned function-object:

fun n ->
  k + f n

Utilizes these instance variables f and k in it's body. Once this function-object is returned, you can only invoke it, there's no other way for you to access f or k (so this is encapsulation).

It's very uncommon to use the term function-object, they are called just functions, but you have to keep in mind that they can "enclose" state as well. These function-objects (also called closures) are not far separated from the "real" objects in object-oriented programming languages, a very interesting discussion can be found here.

Answer 4

In OCaml you can use an actual function to represent a dictionary. Non-FP languages usually don't support functions as first-class objects, so if you're used to them you might have trouble thinking that way at first.

A dictionary is a map, which is a function. Imagine you have a function d that takes a string and gives back a number. It gives back different numbers for different strings but always the same number for the same string. This is a dictionary. The string is the thing you're looking up, and the number you get back is the associated entry in the dictionary.

You don't need an array (or a list). Your add function can construct a function that does what's necessary without any (explicit) data structure. Note that the add function takes a dictionary (a function) and returns a dictionary (a new function).

To get started thinking about higher-order functions, here's an example. The function bump takes a function (f: int -> int) and an int (k: int). It returns a new function that returns a value that's k bigger than what f returns for the same input.

let bump f k = fun n -> k + f n

(The point is that bump, like add, takes a function and some data and returns a new function based on these values.)