15

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

Here is an exercise I don't have any clue

enter image description here enter image description here

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.

Jackson Tale
  • 25,428
  • 34
  • 149
  • 271
  • Are you allowed to use lists? May be a list of (string, int) pairs can be your storage? – Asiri Rathnayake Dec 04 '12 at 17:57
  • OK, I checked your reference. You shouldn't be using a (string, int) list for this. Jeffrey has pointed you towards the answer. – Asiri Rathnayake Dec 04 '12 at 18:57
  • Can you give us the reference this is from? I would like to see the question in context to understand what is not allowed. Who is Jeffery everyone keeps mentioning, the author, teacher, etc.? – Guy Coder Feb 05 '13 at 12:35

4 Answers4

11

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.

asm
  • 8,758
  • 3
  • 27
  • 48
  • Ok, in Java, we just use one dict object to store all {key, value}s. So, in here, for every {key,value} I create a dict? – Jackson Tale Dec 05 '12 at 11:47
  • Right, in Java your *single* dict is destructively modified every time you add or remove an element. In OCaml and related functional languages the typical idiom is that you get back a new data structure and the original is still intact. Take lists for example, you start with `[]`, empty list. Then you do `let x = 5 :: []`, you haven't destructively modified the empty list to contain `5` you've created a new list which contains `5`. Now you do `let y = 6 :: x`, again you've not modified x. You still have `x = [5]` and you now have a new list, `y` where `y = [6; 5]`. In Java x is changed. – asm Dec 05 '12 at 13:02
  • ok, thanks. In the this OCaml dict example, if we really want to find a value of a key, we have to go through all the dict we have created? – Jackson Tale Dec 05 '12 at 13:04
  • It depends on what you mean. If you're asking whether we have to look in both `x` and `y` from my example, not really. If we want to know if a key is in `x` then we only look in `x`, we have the advantage of knowing that now one else modified `x` out from under us (for example in another thread). If you're asking whether we have to look in all dictionaries to the end of the chain, yes that's true, our lookup is worst case `O(n)` where n is the number of elements. In practice you would never actually implement a dictionary like this, you would use a tree of some sort instead. – asm Dec 05 '12 at 13:10
  • Something that may help. Note that I said `the` empty list in my example. If a data structure is immutable it's entirely possible have it be unique, as in OCaml `[]` is conceptually. Java is a different story. You have to create a `new` empty list every time because you know that list will be modified in place. You could not just create one empty list and use it every place in your program that you needed a new list. – asm Dec 05 '12 at 13:17
  • ahh, ok, I understand now. This exercise does not intend to let me implement a real dict. I am thinking about your extra exercise now. – Jackson Tale Dec 05 '12 at 13:17
  • A hint about that, don't try to modify our `list` of functions. Wrap it in another function. – asm Dec 05 '12 at 13:36
  • You mean `let remove d k = fun k' -> if k = k' then 0 else d k`? – Jackson Tale Dec 05 '12 at 13:44
  • Yep exactly. This makes our worst case runtime even worse than linear though :) It's not a good dictionary implementation but an excellent exercise in how to use closures. – asm Dec 05 '12 at 13:47
  • What is exactly **closure**? I have looked at wiki, still can't get it. maybe later that OCaml book will introduce it? – Jackson Tale Dec 05 '12 at 14:22
  • I've added an explanation in the answer. – asm Dec 05 '12 at 14:37
  • 1
    Hi, I believe your implementation of `add` is wrong. It should read `d k'` not `d k`! – Dave L. Oct 22 '13 at 18:49
7

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.)

Jeffrey Scofield
  • 65,646
  • 2
  • 72
  • 108
  • Thanks for your answer. Your `bump` example is easier to understand as it is a not storing any stats. But how can I image the `dict`? a `dictionary` is storing all `{key, value}`s, right? – Jackson Tale Dec 05 '12 at 10:19
  • Ok, in Java, we just use **one** dict object to store all {key, value}s. So, in here, for every {key,value} I create a dict? – Jackson Tale Dec 05 '12 at 10:24
  • In some sense this is true. In pure FP, you never modify data. You just create new data. However, the garbage collector will clean up all the old dicts you're not using. In return you never have to worry about stepping on somebody else's data. There's some cost to this approach, but it works amazingly well. – Jeffrey Scofield Dec 05 '12 at 14:22
  • But the point is that let's say if I have `dict1` with "key1", 0, then at some point, gc will wipe it after some time? – Jackson Tale Dec 05 '12 at 15:24
  • Yes, but it's based on whether you can "see" the value, not on time. Any value that you can talk about (have a name for) will always exist as long as the name exists. So you don't have to worry about it. – Jeffrey Scofield Dec 05 '12 at 15:32
5

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.

Community
  • 1
  • 1
Asiri Rathnayake
  • 1,138
  • 1
  • 11
  • 27
  • Ok, in Java, we just use one dict object to store all {key, value}s. So, in here, for every {key,value} I create a dict? – Jackson Tale Dec 05 '12 at 11:47
  • A single `(key, value, f)` entry can be wrapped in a function-object as above. That `f` will be yet another function-object containing the next `(key, value, f)` entry... and so and so on until the final entry `(key, value, empty)`. At each `add` call, this *list* (implicit) of entries (a.k.a the dictionary) will be extended by one. If you bang your head on this problem for a couple of days, you'll sure learn lots!!! – Asiri Rathnayake Dec 05 '12 at 12:05
  • thanks, actually, I am **banging my head to the wall now**, in addition to the problem. so I will describe my current imagination in English. it is like `add dict1 k1 v1` returns `dict2`, then `add dict2 k2 v2` returns `dict3`...so on so forth. After insert 10 `k,v` pairs, we get `dict10`? **then how do we find a key then?** starting from `dict10`? – Jackson Tale Dec 05 '12 at 12:12
  • It is like some kind of `linkedlist`? – Jackson Tale Dec 05 '12 at 12:39
  • To find the value of a key, you have to remember which `dict` it was used for storing? – Jackson Tale Dec 05 '12 at 12:43
  • @JacksonTale: I hope you got the problem solved with Andrew's advice. Your description of `add` is correct. You just have to chain those dictionaries and recursively find the item when needed. I can update the answer with the code if that helps. Cheers! – Asiri Rathnayake Dec 05 '12 at 14:06
  • Thanks. Is Andrew's code correct? Your answer is inspiring but I have to mark Andrew's answer as correct one because of his continuous help in the comments. – Jackson Tale Dec 05 '12 at 14:24
  • 2
    @JacksonTale: All three answers are correct :) You should select the one that helped you the most. All three of us avoided giving you the exact answer because we wanted you to figure it out yourself. And you have figured it out I think, that's what matters!!! – Asiri Rathnayake Dec 05 '12 at 14:27
1

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.

MSiddeek
  • 71
  • 7