This is the third article of the series called “Writing min function”:

- Part 1: http://componentsprogramming.wordpress.com/2014/05/20/writing-min-function-part-1-the-rise-of-concepts/
- Part 2: http://componentsprogramming.wordpress.com/2014/05/28/writing-min-function-part-2-understanding-concepts/

Now we understand what *Concepts* are (do we?), I will try to complete the min function.

What do I mean with “complete”?

Well, we need to see how to use our min function, but first, let’s write the min function in a real programming language.

From now on I will write code in *C++*. Why* C++*?, it is a topic for another article. But don’t worry, I will try to analyze all the algorithms in several programming languages in the following articles.

Here is the code of the min function from part 2:

//Note 1: this code is Concept-enabled C++. // Later we will see how to use it. //Note 2: Still has errors! template <TotallyOrdered T> T const& min(T const& a, T const& b) { if (a < b) return a; return b; }

(We will see how to define the *TotallyOrdered* concept in *C++* later. For now, think in the mathematical definition presented before)

And we use it in this way:

void usage_with_builtin_types_simple() { int a = 12; int b = 34; //using variables cout << min(a, b); //print the result on standard output //using integer-literals (base10) cout << min(1, 2); //using variables and literals cout << min(a, 2); //assigning the result (copy) int m1 = min(a, b); int m2 = min(1, 2); }

These are very simple examples using the int builtin type, but our min function is supposed to be Generic, so it has to operate with all types that satisfy the *TotallyOrdered* concept. So let’s see a little more complicated example.

Suppose we maintain the employee database of a company and we want to take two employees and know which is the minimum of the two. Let’s see it on code. Here a simplified Employee class written in *C++*:

struct employee { string name; float salary; };

And now we use the min function with Employees:

void usage_with_employees() { employee e1 {"John", 5000.0f}; employee e2 {"Peter", 6000.0f}; employee e3 {"George", 4500.0f}; employee e4 {"Frank", 5000.0f}; employee m = min(e1, e2); // ??? }

What happend at line 7?

Well, we should get a compile-time error saying that the employee type doesn’t satisfy the *TotallyOrdered* concept.

Why?

First, syntactically there is no way of comparing two employees using the less-than-operator required by the *TotallyOrdered* concept.

If we use *C++* templates without *Concepts* (or duck-typing templates) we will get a compile-time error pointing to the min function, saying that a < b could not be done. Instead, if we use a dynamic duck-typing language, like Python, we will get a similar error but at runtime.

The compiler (or interpreter) doesn’t know how to do a < b for employees, so this is the reason why we get the error.

So, how to make my Employee type to satisfy the *TotallyOrdered* concept?

Let’s start satisfying the requirements imposed by the concept:

- Employee must satisfy the
*Regular*concept. - We have to provide an operator< with the signature: Employee x Employee -> bool
- The operator< must be a
*total ordering*relation.

For now I want to skip the points 1 and 3, we will see them in another article. So let’s concentrate on point 2, which is a syntactic requirement, that specify that we have to provide the operator<, so let’s do it:

bool operator<(employee const& a, employee const& b) { return ???????; }

This is the canonical way on *C++* for implementing a less-than-operator, but … What should I put on line 2?

Actually, I don’t know. That answer should be given by the designer of the Employee class. Well…, that’s me (?).

First, remember, *total ordering*, is, roughly speaking, some kind of *Natural Ordering*. So we need to know what is the natural ordering of Employees.

Maybe the natural ordering of employees is by name, maybe by salary, … I don’t know. This depends on the domain of the application. In a company, I think, employees have a unique identification number, maybe that is a good candidate to implement *total ordering*. So, let’s modify our Employee class:

struct employee { int id; string name; float salary; };

Now, let’s finalize our less-than-operator:

bool operator<(employee const& a, employee const& b) { return a.id < b.id; }

Now, we have an Employee class with a natural ordering, by id, that satisfies the *TotallyOrdered* concept (remember, we are ignoring the points 1 and 3).

But, what if we want to know who is the lowest paid employee, and then raise his salary. Should we modify the less-than-operator to compare by salary?

bool operator<(employee const& a, employee const& b) { return a.salary < b.salary; }

Is it OK?

No, we are imposing a default un-natural ordering to employee’s, it is not the right way to do it.

Changing the Employee’s natural ordering is not an option, so, we need another min function, one that takes a relation as parameter.

Let’s do it in the old-unconstrained-way (wrong way?), that is, without *Concepts*:

//Note: It compiles, but is incorrect, still, be patient! template <typename T, typename Comparator> T const& min(T const& a, T const& b, Comparator cmp) { if (cmp(a, b)) return a; return b; }

Now we can write code like the following:

struct salary_comparator { bool operator()(employee const& a, employee const& b) const { return a.salary < b.salary; } }; void usage_with_employees() { employee e1 {1, "John", 5000.0f}; employee e2 {2, "Peter", 6000.0f}; employee e3 {3, "George", 4500.0f}; employee e4 {4, "Frank", 5000.0f}; // using natural employee ordering (by id) employee m = min(e1, e2); // using another (unnatural) ordering employee m2 = min(e1, e2, salary_comparator{}); // using another (unnatural) ordering, with lambdas employee m3 = min(e1, e2, [](employee const& a, employee const& b){ return a.name < b.name; } ); }

But so far, I have not mentioned anything that an experienced programmer does not know, the use of predicates (comparators) is a common thing in practically all programming languages.

What most programmers (and existing implementations) forget is to specify the semantics of the predicate.

So, what are the semantic requirements?

What is Comparator?

Comparator is a *Relation*, that is, a *binary Predicate*. What kind of relation?

It is an ordering. What kind of ordering?

Is it a *total ordering* relation? Well, let’s check it:

*Relation*r is a

*Strict Total Ordering*if: For all a, b and c in the domain of the r, the following must hold:

*Transitivity*: if r(a, b) and r(b, c) then r(a, c)

*Trichotomy*: only one of the following holds, r(a, b), r(b, a) or a = b

It’s easy to prove that the *transitivity* axiom holds so I will skip it; but, what about *trichotomy*? Let’s prove it with an example. Given our previous defined employees:

employee e1 { 1, "John", 5000.0f }; employee e2 { 2, "Peter", 6000.0f }; employee e3 { 3, "George", 4500.0f }; employee e4 { 4, "Frank", 5000.0f };

And our salary_comparator, here called r in order to abbreviate it:

- Take e1 and e2: According to
*trichotomy*: only one of the following holds, r(e1, e2), r(e2, e1) or e1 = e2

What is the result of r(e1, e2)? r(e1, e2) means e1.salary < e2.salary, which means: 5000 < 6000, so it holds. The other two propositions are false (intentionally omitted), so*trichotomy*holds in that case. - Take e1 and e3: Following the same analysis, r(e1, e3) means e1.salary < e3.salary, which means: 5000 < 4500, so it doesn’t hold. But r(e3, e1) means … 4500 < 5000 which is true, and the last proposition is false (again, intentionally omitted), so
*trichotomy*holds. - Now, take e1 and e4: Following the same analysis, r(e1, e4) and r(e4, e1) are both false, so, the proposition e1 = e4 have to be true if we want
*trichotomy*holds.

Is e1 = e4 true?

No! because**e1 is not equal to e4**, they are differents employees, they are not the same.

Then, the *trichotomy* axiom does not hold, that is, the salary_comparator relation is not a* Total Ordering* on the Employee Set. This means that *Total Ordering* is too restrictive.

So, what kind of ordering relation should be our Comparator?

*Partial Ordering*? No, we saw in Part1 that *Partial Ordering* is too weak to define min.

We need something in between *Partial* and *Total Ordering*: what we need is called *Weak Ordering*[1].

Roughly speaking, *weak ordering* says that if r(a, b) and r(b, a) are false, then, a and b are **equivalents**.

So, let’s modify the min function to introduce *weak ordering*:

//Note: yes! you guess it, it is incorrect, still! template <typename T, StrictWeakOrdering Cmp> requires SameType<ArgumentType<Cmp>, T> T const& min(T const& a, T const& b, Cmp cmp) { if (cmp(a, b)) return a; return b; }

The code above means that we have a function called min, that takes two formal parameters, a and b, both of the same type, called T.

The funcion has a third formal parameter, cmp, that models the concept called *StrictWeakOrdering.* The “requires” clause means that T (the type of a and b) and the argument type of the Comparator (Cmp) must be the same.

Well, in this article I explained what *Weak Ordering* means and why it is important, I want to end it with a quote from Alex:

“Mathematicians are happy with *Total* and *Partial* *ordering*. But most of them don’t know what is *Weak Ordering. *It is not a common term in mathematics but it is essential in computer science, because when we want to order things, we want to order **by something**. For example by social security number, by name, by age”.

In the next article, finally, I will tell you what are the mistakes that remain to be addressed.

You can get the complete source code on my Github repository.

## References

[1] For a formal definition of *Weak Ordering* see:

http://www.elementsofprogramming.com/eop-concepts.pdf

I hope you introduce projections next to show how to reuse std::less with id and salary. It would be also nice if you cold mention variadic versions of min: min(a,b,c, std::less(), proj).

I hope too :)

I’m a little delayed with the next article, but it is not about projections.