Category Archives: Technology

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

Tech Scene: Payment Models for Digital Goods

In the history of the internet, a couple of different payment models have emerged for digital goods. There are various types of digital goods, many of them existed long before the internet: Books, News, Music, Videos, TV-Shows, TV-Channels to name a few. Some goods are inherently digital like virtual goods in computer games.

In the beginning of the internet, there was only one payment model: free digital goods sponsored by advertisement, and we still have that model today. But there were only a couple of digital goods available in the old times, mostly news articles.

Newer models emerged since then. The music and movie industry for instance decided to offer most of their goods by direct payment per item. For virtual goods like in Zynga games, the freemium model disrupted major parts of the gaming industry – you can play the games for free, but once you’re hooked, you have to pay in order to succeed.

The disruption of the direct payment model for music is now driven by services like Spotify or Simfy. Instead of letting you pay for every single item, you have to pay a flat fee per month to listen to any music you want to. You don’t own the titles anymore, you just get the right to listen to them as long as you’re paying for the service.

Which payment model is best depends on the type of goods you offer. I think there are three categories of digital items: collectable, consumable and enabling items. A collectable item has an intrinsic value to people and they want to own it (even after consuming it). Consumable items on the other hand only have value to people before they’ve consumed them. An enabling item allows people to improve on something existing, so they need to have it to get one step further.

Of course, no item falls completely into one category and it also depends on the mindset of the customer where to put an item. To me, books and movies are mostly collectable items which is why we still mainly use direct payment for such goods. TV-Shows and music on the other hand is more of a consumable item – sure, there are some shows and some music that pop-culture aficionados want to watch or to listen to all day long over and over, but most shows are only consumed once or twice. Likewise, we usually listen to a number of songs until we get bored of them and move on. We don’t really care whether we still have them. Hence, flat fee models are on the move for consumable items. It goes without saying that the freemium model is best fitted to enabling items such as virtual goods.

What category is news? Most of the time, it is a consumable good, because news are usually only relevant to you until they’re not new anymore. Because that’s what news is – it’s new. Sure, news portals do contain articles that have long-term value, but mostly it’s only relevant for a short time. So what’s the right payment model? In the old times of the internet, it was free to the consumer and sponsored by advertisement. It was okay for some time that this payment model didn’t produce much revenue, because real news publishing was still happening offline. Nowadays, the digital news portals have to generate more revenue as the offline revenue stream is breaking down.

So what other payment models are there? News publishers transfers their issue-based offline system to the net by offering flat fee subscriptions on a monthly or yearly basis, or per-issue payment like in the offline world. Considering news issues on a fine granular level, you pay a flat fee for reading any number of articles in the issue. So that’s the flat fee model for a consumable item. Makes sense. But there are still not enough people falling for that, as there are still many free news websites.

There is a tendency of news publishers to introduce (soft) paywalls to account for that. A (soft) paywall restricts your access to digital goods – articles in particular – by requiring you to pay a very small fee per article you’re reading or by allowing you a small number of articles to read for free until you either have to pay on a per-article basis or by subscription.

Time will tell whether per-article payment works. Since articles are mostly consumable goods of short relevance with many free competitors, I would rather suggest a different payment model. It should neither be for free, nor be a flat fee, nor be a per-article payment. The problem with the per-article payment is that you can’t really give people a demo of what they’re going to get. Then again people are hesitant to pay for the article as they might regret it in case the article didn’t meet their expectations.

My suggestion therefore would be a model that I call “capped satisfactory payment”. It consists of two rules. You pay on a per-article basis, but if you didn’t like the article after reading, you can get your money back for the article. Obviously, you combine that with a fair-use policy and tracking of rejected articles, so you exclude free-riders. The second rule is to cap the overall payment for read articles per issue. In other words if a reader really digests a lot of articles in an issue, he shouldn’t pay much more than the flat fee for the whole issue in the first place. To my mind, this model communicates clearly that you take the readers’ opinion seriously while reducing the hurdle for the consumer to read and pay for an article dramatically.


Enhanced by Zemanta

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

Tech Scene: Platform Apis and Standards

This post will be about platform application programming interfaces (APIs), protocols and standards. When we build software that has to integrate with components written by other people or when our software has to communicate with some other program (for instance via the internet), both programs have to agree on a common language. Otherwise, they could not exchange any meaningful data or commands.

The designers of the software can create any language they want for communicating, but all involved components have to agree on it. The way software components talk to each other is usually called protocol. It could be seen as both the grammar and the vocabulary that all components understand. Your browser, for instance, used the HTTP protocol to retrieve this website from my web server. They both agreed to speak HTTP. The vocabulary, in this case, was a formal way of your browser saying “give me the following page” and my web server replying “there you go” with the full page attached to it.

This set of commands could be seen as an application programming interface. The server specified which commands it understands. But an API is not necessarily tied to a protocol. It is just an abstract way of specifying the supported command set.

Within the last couple of years, many applications in the internet developed so-called platform APIs – a way of opening up their applications to other programmers. You could write, for instance, a service that could be hooked up with the Facebook API, so your application could browse through friends, interests and all that.

While all this is great, there is usually no standard attached to these APIs. This means that similar applications offer different APIs – in other words in order for your application to access the friends of Google+, it has to use a different API than when accessing the friends of Facebook. Note that this completely differs from the HTTP protocol for accessing websites. Whenever your browser requests a page from a server, it uses the exact same command set – because all HTTP servers have the same API.

And that’s great, because it makes browsers so versatile – they can browse every page. The same thing holds true for emails: there is a single API that unifies all mail servers. The email system is even more interesting, as it is completely decentralised (with all its benefits and handicaps).

The reason why systems like web browsing and email work so well together is standards: the internet world and the industry agreed a long time ago to all use these protocols and the associated APIs. Standards do contribute to an accessible market, it simplifies planing and it makes it much easier for customers to change between providers of a certain service, the decentralisation makes the standard’s ecosystem robust, reliable and competitive. It even allows user to communicate cross-provider with each other. Hence, there are a lot of benefits associated with standards.

However, standards also serve as barrier for innovation and evolution – because it so hard to change them once they’re successfully in place. The best example is good old email – it’s insecure, out of fashion, full of spam and yet it is still the most successful communication platform we have on the internet. And it will take a lot of time for this to change.

But the specific platform APIs as we have them now on Facebook, Google+, Instagram, Instapaper, Dropbox, Foursquare, Twitter and so on also have their downsides. Every developer that wants to build on their services has to write specific code for each supported platform. While you can say “I support email”, you can’t really say “I support social networking” – because “social networking” has not been standardised. As a consequence, developers have to spend an extended amount of time to integrate different kinds of platforms and even more importantly have to make a selection of supported services. By this, big players like Facebook are of course favoured while smaller players miss out on the opportunity to be supported by other services.

Also for the customer it can have unpleasant side effects at times, particularly when a specific service closes down or when the customer wants to move to a different service. Without standards, there is usually no way to migrate your data in a comfortable way. You can’t just move all your likes, interests, statuses or contacts from Facebook to Google+. Similarly services that store your online playlists like Simfy, Spotify or don’t allow you to migrate to a competitor. And so on. The list could be continued indefinitely.

For the big players, this is kind of neat, because it protects their markets and user bases, but for the customers, it makes it more difficult to change platforms. It is also not possible to communicate with people from other platforms which is, of course, most simple with email. In other words these “closed systems” with their proprietary platform APIs foster monopolies which is usually not in the best interest for the customer.

The different incompatible platform APIs have also contributed to another trend which I would call the middleware service trend, where new applications are being built that try to interlink all different kinds of APIs. This can be on the software as a service level like ShareThis, but it can also feature consumer products like Ifttt.

The best example where we are still desperately lacking an ubiquitous standard is account management and passwords: you still have to sign up for every single page and keep track of the passwords. This is a mess. There is also the problem of personal data that you want to share with different services – such as your payment information with an online shop. The most promising standard here is OpenId and it should serve as a decentralised authentication service. However, the adoption is only so-so. Most websites that feature sign-in via external identity providers preselect Login via Facebook or Login via Twitter – which again features specific platform APIs instead of standards. And this chains you even further to one of the big players.

It will be very interesting to see whether the OpenId standard will gain some serious traction in the future, and how the battle between platform APIs and standards will play out in general.

Applied Engineering: Functional Languages and the Dinner Table Problem

This will be the first post in a series called “applied engineering”. It will feature small tutorials on engineering problems as well as gentle introductions into the art of software engineering. Even non-tech people should be able to follow the series.

My first post in the series considers functional languages, a class of programming languages. Functional languages are mostly used in scientific environments but are now gaining traction in industry applications as well. I will add a couple of posts on functional languages to get the interested reader started.

As with all language paradigma, there is a bunch of concrete realisations that we can use. For our purposes here, we use Ocaml – so if you want to try our little snippets, go ahead and install Ocaml on your own machine.

Now what exactly are language paradigma and what are the different programming languages? Language paradigma are based on the same idea as language families in natural languages – you group languages together that share the same roots. The main language paradigma that we have in computer science are imperative languages, functional languages, markup languages, logic languages and object orientation, although object orientation could be seen as a “language topping”. It is mostly but not exclusively used in combination with imperative languages though.

So we are using the functional language called OCaml. We could also use Haskell – we would stay in the same language family (like Germanic languages). In other words, once you’ve understood the concepts of functional languages using Ocaml, you can easily adapt to Haskell in case you want to.

Let’s start with a real-world problem to see how we could solve it using Ocaml. Assume that you host a dinner party and you’re having a hard time assigning people to your table as some people want to sit right next to each other while others cannot without ruining your evening. After a couple of minutes writing down some possible seatings on a piece of paper, you give up – there are just too many combinations.

Hence let the computer solve the problem for us by using our Ocaml program – because that’s what programs are all about: you give them some well-structured data – in our case whether people want or not want to sit next to each other – and let them compute a solution to the data – in our case a favourable dinner table seating assignment.

Before starting to write a single line of code, let us structure the data. For the purpose of this example, we need to add a bunch of people, a bunch of constraints (who wants to sit or not sit next to whom) and some table configuration (i.e. what seats are next to each other).

First, let us start with the people. We will assign consecutive natural numbers starting from 0 to all people:

0 Hank
1 Karen
2 Becka
3 Mia
4 Julian
5 Trixi

Second, let us add some constraints. A constraint will be of the following form:

Person A likes Person B by +/-p%

This means that person A would like to sit next to person B by a specific rating – ranging from 0% – 100%. If person A would rather not sit next to person B, we let p% range from -100% to 0%. Note that person A wanting to sit next to person B does not necessarily imply the converse. Let us assume the following constraints:

Hank likes Karen by 100%
Hank likes Becka by 100%
Hank likes Mia by -50%
Hank likes Julian by -100%
Karen likes Hank by 75%
Karen likes Becka by 100%
Karen likes Mia by 50%
Karen likes Julian by 50%
Karen likes Trixi by -75%
Becka likes Hank by 50%
Becka likes Karen by 50%
Becka likes Mia by 75%
Becka likes Julian by -75%
Mia likes Hank by 100%
Mia likes Trixi by 50%
Julian likes Karen by 50%
Trixi likes Hank by 100%
Trixi likes Karen by -50%

This for instance tells us that while Hank isn’t too eager to sit next to Mia, she, on the other hand, would like so very much.

Third, let us add some table configuration. We do this be specifying the proximity between seats while no proximity specification means that these two seats are so distant from each other that the two people sitting there could not be considered next to each other. For our purposes, we assume a small dinner table with one seat on each end and two seats on each side. We will give every seat a number again, assigning 0 and 3 to the left resp. the right end, and 1-2 resp. 4-5 to the bottom resp. top side. We will give the proximity specification by such lines:

i j p%

This means that seat $i$ is in $p%$-proximity of $j$ where $100%$ means directly next to each other and $50%$ for instance means that these two chairs are near each other but not exactly next to each other. For our table, the specification could look as follows:

0 1 100%
0 4 100%
1 0 100%
1 4 100%
1 2 100%
1 5 50%
2 3 100%
2 1 100%
2 5 100%
2 4 50%
3 2 100%
3 5 100%
4 0 100%
4 1 100%
4 5 100%
4 2 50%
5 3 100%
5 4 100%
5 3 100%
5 1 50%

This table tells us, for instance, that the bottom left seat 1 is right next to left head seat 0, bottom right seat 2 and top left seat 2, while it is only “near” top right seat 5 and not at all next to the right head seat 3.

A dinner table seating assignment is now an identification like “Hank sits on seat number 3 and Karen sits on seat number 0”. And our program will search for such an assignment that optimizes all given constraints. We will use a mathematical formulation to explain what we mean by optimal – intuitively, we want to maximize the accumulated satisfaction of constraints.

More formally, let $assign: People \rightarrow Seat$ be a table seating assignment, $proximity: Seat \times Seat \rightarrow Precentage$ be the proximity configuration between two seats and let $constraint: People \times People \rightarrow Percentage$ be the constraint of two people. We then want to maximize the value of
\sum_{p,q \in People} constraint(p,q) \cdot proximity(assign(p), assign(q))
with respect to the table seating assignment. In other words we build the sum over all pairs of people, where the value of a pair is given by the product of its proximity and its constraint, i.e. the further away two people are the less relevant the constraint is.

Are we still on the same page? You had this or similar problems before? Great! You have just seen how you model a real-world problem in terms of mathematics and processable structures. In the next post, we will write our first Ocaml program and integrate this data.