Applied Engineering: Types, Lists and Functions

In the last post, we introduced the problem of assigning seats at your dinner table to your guests in an optimal way – and by optimal, we mean that most constraints can be satisfied most accurately.

In order to solve the problem, we use the functional programming language OCaml. Functional programs are very close to mathematical formulations – it is about the definition of data and functions operating on data and not so much about how to compute stuff with it. So let us define the list of people first. Every person is described by a number and his or her name – mathematically, we describe that by a pair, which is exactly what happens in OCaml:

(0, "Hank")

Ocaml is a typed language, so it will tell you what type the definition you just made has. The type corresponds to the set-theoretic universe in which the pair lives. Integers like 0 have the type int while words like “Hank” have the type string. Therefore Ocaml will infer the following type (you can try that out by starting “ocaml” in your terminal and entering the pair terminated by “;;”):

- : int * string = (0, "Hank")

That makes sense – a pair (“*”) of an integer and a string.

The description of the whole table is a different story – in general, we have an arbitrary number of people. Mathematically, we could describe that by a set – a similar type exists in functional languages as well. But we first introduce a simpler type: the list. A list contains an arbitrary number of objects of the same type in a fixed order. In Ocaml, we introduce the list of persons as follows:

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

Again, Ocaml infers the type which is a list of pairs:

val people : (int * string) list

Next, we want to crunch some numbers. For starters, let’s try to find out how many people there are in the list. As a mathematician, one would define a recursive function that sums up the number of objects in the list – and that’s exactly what we will do in a functional language:

let rec cardinal list =
match list with
[] -> 0
| obj::list_rest -> 1 + cardinal list_rest

The first line introduces a definition again – we define a recursive function named “cardinal” that has one argument named “list”. The function is defined by a pattern matching on the given list. If the list is empty “[]”, the function returns 0. Otherwise, the list can be partitioned into a head named “obj” and a tail named “list_rest”, and the number of items in the list can be computed by counting the number of items in the the tail of the list plus 1.

Ocaml gives our function “cardinal” a type again:

val cardinal : 'a list -> int

Therefore “cardinal” is a function that maps a list based on a type variable ‘a to an integer. The type variable means that “cardinal” does not depend on how the objects of the list look like. Indeed, we can apply “cardinal” to our list of people:

cardinal people: int = 6

Let us consider another example of a recursive definition. We could be interested in obtaining the list of names without the integers. For this, we actually have to solve two problems: obtaining an element of a pair and mapping every object of a list to a new object. In order to select the second element of a pair, we use pattern matching again:

let second (x,y) = y

Ocaml infers the following type:

val second : 'a * 'b -> 'b

Therefore, “second” is a function that takes a pair with type variables ‘a and ‘b and maps it to the type variable ‘b. In other words, the function does not care about the type of the first entry of the pair and preserves the type of the second entry of the pair.

We continue with mapping a list of objects to a new list of new objects. For this, we assume that “f” is a function that maps an object to a new object. Then, we can define the mapping operation as follows:

let rec map f list =
match list with
[] -> []
| obj::list_rest -> (f obj)::(map f list_rest)

As before, we define “map” to be a recursive function that takes “f” and “list” as arguments. If “list” is an emtpy list, it returns an empty list as well. Otherwise, the list can be partitioned into a head “obj” and a tail “list_rest”. We apply “f” to “obj” in order to get a new object and use it as head of our new list that we create by calling “map” recursively on the tail of the list.

Ocaml infers the following type:

val map : ('a -> 'b) -> 'a list -> 'b list

The type might look scary at first sight – it says the following: “map” is a function that maps the argument “f” to a function that maps the argument “list” to a result. The first argument “f” has the type (‘a -> ‘b) which requires “f” itself to be a function that maps something of type ‘a to something of type ‘b. Then, “map” maps a list with objects of type ‘a to a list with objects of type ‘b.

We can now apply “map” to our function “second” that selects the second entry of a pair:

map second: ('a * 'b) list -> 'b list

In other words, “map second” is now a function that takes a list of object pairs and maps it to a list of objects that share the type of the second pair items of the original list. If we now apply this to our list of people, we get the following result:

map second people: string list = ["Hank"; "Karen"; "Becka"; "Mia"; "Julian"; "Trixi"]

In our next post in the series, we will consider advanced types like Sets and Maps, and introduce a type for describing table assignments, bringing us closer to the solution of our problem.

Enhanced by Zemanta

Leave a Reply