Writing min function, part 2: Understanding Concepts

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:

TotallyOrdered(\texttt{T}) \triangleq \hspace{37mm}\texttt{//line1} \\  \hspace*{13mm} \texttt{Regular(T)} \hspace{50mm}\texttt{//line2} \\  \hspace*{7mm} \land <\texttt{: T x T} \rightarrow \textnormal{bool} \hspace{30mm}\texttt{//line3} \\  \hspace*{5mm} \land total\_ordering(<) \hspace{36mm}\texttt{//line4}
 

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 \leq relation on the Natural numbers set, or in other words, (\mathbb{N} , \leq ) is a Reflexive Totally Ordered Set.
    That is, for all a, b and c in \mathbb{N} , the following must hold:
    Transitivity: if a \leq b and b \leq c then a \leq c
    Antisymmetry: if a \leq b and b \leq a then a = b
    Totality: a \leq b or b \leq a

    (\mathbb{N} , \geq ) is another example of a Reflexive Totally Ordered Set.

  • An example of Strict Total Ordering is the \textless relation on the Natural numbers set, or in other words, (\mathbb{N} , \textless ) is a Strict Totally Ordered Set.
    That is, for all a, b and c in \mathbb{N} , the following must hold:
    Transitivity: if a \textless b and b \textless c then a \textless c
    Trichotomy: only one of the following holds, a \textless b, b \textless a or a = b

    (\mathbb{N} , > ) is another example of a Strict Totally Ordered Set.

Exercise 1: Prove that
a. \leq is a Transitive relation
b. \leq is an Antisymmetric relation
c. \leq is a Total relation
on \mathbb{N}
 
Exercise 2: Prove that
a. \textless is a Transitive relation
b. \textless obeys the Trichotomy law
on \mathbb{N}
 

So, we have four options with which the TotallyOrdered concept could be defined: \textless , \leq , > , or, \geq . 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 \textless , but here I will show the thinking behind the choice.

We have two choices to make:

  1. Less… vs. Greater…: \textless or \leq vs. > or \geq
  2. Reflexive vs. Strict: \leq or \geq vs. \textless or >

As we know, for 1, Alex has chosen Less…. The rationale for his decision is simple: Counting!
\textless 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 (\leq ) and Strict (\textless ).
Alex has chosen Strict (\textless ) 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 \textless in their books as the primary ordering, when they talk about, for example, Totally Ordered Fields they write all the axioms in terms of \textless

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

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


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]

 

Advertisements

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s