Applied Engineering: Modules, Functors and Maps

In the last post of the series, we introduced the functional programming language OCaml and basic types like lists. We applied higher-order functions like map to them (recall that a higher-order function essentially is a function taking a function as an argument).

Recall that we’ve considered the list of people:

let people = [
  (0, "Hank");
  (1, "Karen");
  (2, "Becka");
  (3, "Mia");
  (4, "Julian");
  (5, "Trixi")

If we now want to look up the name of the person with id, let’s say, 4, we can only walk through the list until we find an entry that matches the respective number. This is a very inefficient algorithm for looking up data (its worst-case and average-case complexity are both linear). We can be much faster using a different data structure that stores all entries in order and applies binary search. The classic structure is a balanced tree and all database system rely on such organization of data. Luckily, OCaml already provides a module for handling such data. A module can be seen as a namespace for types and functions that belong together.

We will use the map module that allows to quickly look up a key and return a corresponding value – in our case, the keys would be the people’s ids and the values would be the people’s names. The map module is general enough to allow arbitrary keys and arbitrary values to be stored in a balanced tree.

If you think about that for a minute, you might see an issue here. In order to organize the data in the tree, you need to be able to compare keys with each other, so they can be arranged in the right order. But how would the map module compare stuff with each other if the map module doesn’t know how to compare certain types? Well, it doesn’t. We have to specify how our keys should be compared with each other.

How do we explain to the map module how our keys can be compared with each other? By parametrizing the map module by an auxiliary module that explains the key comparison. More precisely, we map the auxiliary module to a concrete map module by a functor (a mapping from a module to a module).

module IntMap = Map.Make(
    type t = int
    let compare = compare

On other words: we define the module IntMap to bethe  Map.Make-Functor applied to the auxiliary module with key type int (our people’s ids) and the comparator compare (OCaml provides a “magic” compare function for every type that we use here – for ints, it’s the natural ordering on integers).

Next, we want to convert our list of people to an IntMap, mapping ids to people’s names. In order to build and use the map, we need three IntMap-functions: one to create an initial empty IntMap-instance, one to add assignments to it and one to look up keys.

IntMap.empty: 'a IntMap.t
IntMap.add: int -> 'a -> 'a IntMap.t -> 'a IntMap.t
IntMap.find: int -> 'a IntMap.t -> 'a

Recall that ‘a is a type variable. In our case, the type variable corresponds to the value type – and since the map does not care about the specifics of this type, we don’t have to fix it via any auxiliary modules and functors.

The first function, IntMap.empty, simply returns an empty instance of an IntMap. The second function, IntMap.add, takes a key, a value and an existing IntMap as arguments and returns a new IntMap that added the new key-value assignment to the existing IntMap. The third function, IntMap.find, takes a key and an existing IntMap as arguments and returns the corresponding value (assuming that the key-value pair is present).

Our conversion function therefore looks as follows:

let int_list_to_map int_list =
	let empty_map = IntMap.empty in
	let rec helper rest_list acc_map =
		match rest_list with
			[] -> acc_map
		|	(domain, range)::rest_list' ->
                                helper rest_list' (IntMap.add domain range acc_map)
		helper int_list empty_map

The function starts with an empty map and then walks recursively through the last, adding the assignments one by one to the map. We can now use it to generate our people mapping and use it to look up people’s names:

let people_map = int_list_to_map people
let people_func p = IntMap.find p people_map

Recall that in our initial post, we had two more lists – the list of constraints (which person likes to sit next to which person) and the table configuration (which is seat is close to which set). Every entry in each of these lists is a triple – two ids and a value (how likable / how close).

let constraints = [
	(0, 1, 1.0);
	(0, 2, 1.0);
	(0, 3, -0.5);
	(0, 4, -1.0);
	(1, 0, 0.75);
	(1, 2, 1.0);
	(1, 3, 0.5);
	(1, 4, 0.5);
	(1, 5, -0.75);
	(2, 0, 0.5);
	(2, 1, 0.5);
	(2, 3, 0.75);
	(2, 4, -0.75);
	(3, 0, 1.0);
	(3, 5, 0.5);
	(4, 1, 0.5);
	(5, 0, 1.0);
	(5, 1, -0.5)

let table = [
	(0, 1, 1.0);
	(0, 4, 1.0);
	(1, 0, 1.0);
	(1, 4, 1.0);
	(1, 2, 1.0);
	(1, 5, 0.5);
	(2, 3, 1.0);
	(2, 1, 1.0);
	(2, 5, 1.0);
	(2, 4, 0.5);
	(3, 2, 1.0);
	(3, 5, 1.0);
	(4, 0, 1.0);
	(4, 1, 1.0);
	(4, 5, 1.0);
	(4, 2, 0.5);
	(5, 3, 1.0);
	(5, 4, 1.0);
	(5, 3, 1.0);
	(5, 1, 0.5)

We again want to convert both lists to maps, but in this case, the key consists of two ids, i.e. is an int product-type. We need to create a new module IntMap2 by mapping a new auxiliary module (that allows to compare key pairs with each other) to a map:

module Int2Map = Map.Make(
	  type t = int * int
	  let compare = compare

let int2_list_to_map int2_list =
	let empty_map = Int2Map.empty in
	let rec helper rest_list acc_map =
		match rest_list with
			[] -> acc_map
		|	(domain, domain2, range)::rest_list' ->
                                   helper rest_list' (Int2Map.add (domain, domain2) range acc_map)
		helper int2_list empty_map

let constraint_map = int2_list_to_map constraints

let table_map = int2_list_to_map table

We again want to define functions to look up the respective values by key pairs. There will be cases, however, in which certain key pairs don’t exist in the mappings. We didn’t specify, for instance, any constraints for the two seats 0 and 2 with respect to each other, because we implicitly assign them the proximity value 0. Similarly, this holds true for the constraints. We need to make sure, therefore, that our look up routines catch the exception in which no key pair could be found.

let constraint_func p q =
		Int2Map.find (p, q) constraint_map
		Not_found -> 0.0

let table_map = int2_list_to_map table		

let table_func p q =
		Int2Map.find (p, q) table_map
		Not_found -> 0.0

We say here, try to execute the look up code provided by the Map module. If it raises the exception Not_found, return 0.

Next, we need to define a new type for handling dinner table assignments. It should be a map from a person’s id to a seat id – in other words an int IntMap.t. To play around with it, let us setup a test assignment that assigns each person the seat with the same id:

let test_assignment = int_list_to_map [(0,0); (1,1); (2,2); (3,3); (4,4); (5,5)]

So far, so good. To get a feeling of what’s going on, let us print the table assignment. We will make use of another higher-order function provided by the Map module that allows us to walk through the map:

IntMap.fold: (int -> 'a -> 'b -> 'b) -> 'a IntMap.t -> 'b -> 'b

This looks pretty complicated, so let’s check the details. The first argument is function that accepts a key and a value, and maps some data (of type ‘b) to updated data (of type ‘b again). The second argument is the map and third argument is some initial data (of type ‘b). Overall, the routine routines data of type ‘b. Internally, the function starts with initial data and the first key-value-pair and calls the user function to obtain an updated data object. It continues in that fashion with the second key-value-pair until all key-value-pairs have been handled. The final updated data object is then returned.

We will make us of it build a textual representation of dinner table assignments:

let format_assignment assignment =
	IntMap.fold (fun person seat acc_format ->
		acc_format ^
                people_func person ^
                " sits on seat #" ^
                string_of_int seat ^ "\n"
	) assignment ""

How does it work? It starts with the empty string “” and adds a line for every assignment pair in the user defined function. The current string is given by the accumulator variable acc_format. The output accumulator is built by concatenating (denoted by ^ in Ocaml) the accumulator variable with the person’s name and the seat number.

Applying that to our test assignment, we get the following output:

# print_string (format_assignment test_assignment);;
Hank sits on seat #0
Karen sits on seat #1
Becka sits on seat #2
Mia sits on seat #3
Julian sits on seat #4
Trixi sits on seat #5

We conclude the post by realizing the assignment value function of our initial post that allows us to rate a given dinner table assignment:
\sum_{p,q \in People} constraint(p,q) \cdot proximity(assign(p), assign(q))
We make extensive use of the fold operation again (which corresponds to the sum operation here):

let assignment_value assignment = 
	IntMap.fold (fun p _ acc_value ->
		IntMap.fold (fun q _ acc_value' ->
			acc_value' +. constraint_func p q *.
                        table_func (IntMap.find p assignment)
                                   (IntMap.find q assignment)
		) people_map acc_value
	) people_map 0.0

For the record, the assignment value of our test assignment is 3.5. We should find an assignment that yields a higher value, right? We will see how to accomplish that in our final post in the series.

Enhanced by Zemanta

Leave a Reply