This is the second article of the series called “Writing min function”.

I want complete the min function and fix the mistakes mentioned in the previous post. But first, we have to understand *Concepts*, so let’s review the last version of the function with its requirements.

// Requires: // The type of a is equal to the type of b, and it is called T, // and T is TotallyOrdered min(a, b) { if (a < b) return a return b }

Here we specify that:

- the formal parameters a and b are of the same type, and we called this type: T.
- T
*models*the concept called*TotallyOrdered*.

“A type *models* a concept, if the requirements expressed by the concept are *satisfied* for this type”

So, let’s review the formal definition of the *TotallyOrdered* concept:

This reads as:

- line1: A type T models the
*TotallyOrdered*concept if: - line2: The type T also has to model the
*Regular*[1] concept. This means that*TotallyOrdered*is defined in terms of*Regular*. - line3: A procedure less-than-operator (<) with the signature: T x T -> bool, must exist. This is the syntactic rule that allows us to write things like: a < b
- line4: This is a semantic requirement, meaning that the
*less-than-operator*procedure has to be a*Total Ordering relation*.

But… remember that there are two kinds of *TotalOrdering*.

Do we mean *Reflexive* or *Strict* *TotalOrdering*? Because it would be one or the other.

Let’s review the difference with examples:

- An example of
*Reflexive Total Ordering*is the relation on the*Natural*numbers set, or in other words, (, ) is a*Reflexive Totally Ordered Set*.That is, for all a, b and c in , the following must hold:

*Transitivity*: if a b and b c then a c

*Antisymmetry*: if a b and b a then a b

*Totality*: a b or b a(, ) is another example of a

*Reflexive Totally Ordered Set*. - An example of
*Strict Total Ordering*is the relation on the*Natural*numbers set, or in other words, (, ) is a*Strict Totally Ordered Set*.That is, for all a, b and c in , the following must hold:

*Transitivity*: if a b and b c then a c

*Trichotomy*: only one of the following holds, a b, b a or a b(, ) is another example of a

*Strict Totally Ordered Set*.

**Exercise 1**: Prove that

a. is a Transitive relation

b. is an Antisymmetric relation

c. is a Total relation

**Exercise 2**: Prove that

a. is a Transitive relation

b. obeys the Trichotomy law

So, we have four options with which the *TotallyOrdered* concept could be defined: , , , or, . Whatever we choose is a right decision, but we have to choose.

**Exercise 3**: Do you know why any of the four options is a right choice?

I’m lying, actually we will not choose anything, the *TotallyOrdered* concept is defined using , but here I will show the thinking behind the choice.

We have two choices to make:

*Less…*vs.*Greater…*: or vs. or*Reflexive*vs.*Strict*: or vs. or

As we know, for 1, Alex has chosen *Less…*. The rationale for his decision is simple: Counting!

is the natural order of natural numbers. Why? Usually we count in ascending order, it is the natural way of counting.

Having chosen *Less…* then, we have to chose between *Reflexive* () and *Strict* ().

Alex has chosen *Strict* () and his reasoning is: “It is one character less” (len(‘<‘) < len(‘<=’))

But maybe you could think: “This is not a good reason”.

The Alex’s answer is: “Well, we can choose either because they are equivalents!, then, you could use any decision procedure, such as, fewer typing”

Finally, another fundament: “Mathematicians consistently use in their books as the primary ordering, when they talk about, for example, *Totally Ordered Fields* they write all the axioms in terms of ”

Summarizing, the choice is to use *LessThan* that is *Strict*, so we use .

Well, now we understand what we mean when we use the *TotallyOrdered* concept, but this post is ended and we haven’t written any new code.

You must be thinking: “Anyone knows how to write the min function without having any knowledge about abstract algebra”.

The Alex’s answer is: “Yes, they may know how to write it, but they implemented it incorrectly time and time again. How I know that? Because I was one of them.”

And this is mine: “Remembering some mathematics doesn’t do any harm”

In the next post I will write some code. Be patient 🙂

## The Series

- Part 1: The rise of Concepts
- Part 2: Understanding Concepts
- Part 3: Weakening the ordering
- Part 4: Const-Correctness

## References

[1] *Regular* is another concept, maybe the most important one, I will cover it later, but for the moment we will ignore it. If you want to see its definition, see http://www.elementsofprogramming.com/eop-concepts.pdf [page 1]

## 3 thoughts on “Writing min function, part 2: Understanding Concepts”