Scalable Peano

Peano axioms are the foundation of modern mathematics. The five rules that bring its name define the concept of ordered set of numbers. The axioms are:

1. 0 is a number
2. the successor of a number is a number
3. two different numbers can’t have the same successor
4. 0 is not the successor of any other number
5. every property of 0 or of any successor of a number which has that property, if a property of every number

Peano axioms was intended to describe natural numbers: 0, 1, 2, 3, 4, 5, … But the idea of successor is open to a wide range of interpretations. Bertrand Russel writes in its Introduction to Mathematical Philosophy that if we take the notion of pair number and we use it to define what is the successor of a number, Peano axioms still hold: 0, 2, 4, 6, 8, …

This idea can be elegantly formalized in Scala by defining a successor function for a specific number series:

def peano(successor: (Int) => Int, zero: Int, length: Int) {
    print (zero)
    if (length > 0) {
        val s = successor(zero)
        print (", ")
        peano(successor, s, length - 1)
    }   
}   

This function takes another function as first parameter. Goal of this function is to compute the successor of the given number. Changing the rule to guess the successor requires just changing the function. We can start by defining a function that returns the integer successor of a natural number:

scala> def naturalSuccessor(i: Int): Int = i + 1
naturalSuccessor: (i: Int)Int

scala> peano(naturalSuccessor, 0, 20)
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Nothing special here. Now I define another function that returns the next even number:

scala> def evenSuccessor(i: Int): Int = i + 2
evenSuccessor: (i: Int)Int

scala> peano(evenSuccessor, 0, 20)
0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40

Here it is! Now the successor of each number is the next even number. Another example: doubles!

scala> def doubleSuccessor(i: Int): Int = if (i == 0) 1 else i * 2
doubleSuccessor: (i: Int)Int

scala> peano(doubleSuccessor, 1, 20)
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576

That’s just a simple case where functional programming allows to express mathematical concepts in an elegant an concise way.

Another interesting observation about Peano’s axioms is that if 100 is used in place of 0, the set of axioms still holds (but the numbers lower than 100 disappear from that version of the mathematical universe). We can just change our zero argument to check this:

scala> peano(simpleSuccessor, 100, 20)
100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120

scala> peano(doubleSuccessor, 100, 20)
100, 200, 400, 800, 1600, 3200, 6400, 12800, 25600, 51200, 102400, 204800, 409600, 819200, 1638400, 3276800, 6553600, 13107200, 26214400, 52428800, 104857600

Scala allows us to inline the code of the successor function inside the peano() call:

scala> peano ((i: Int) => {i + 2}, 0, 10)
0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20
scala> peano ((i) => {i + 2}, 0, 10)
0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20
scala> peano (i => {i + 2}, 0, 10)
0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20
scala> peano (i => i + 2, 0, 10)
0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20

The last form is the less cluttered, while the first one is the most complete. Curly braces are useful if the successor function has a complex body formed by more than one instruction. The last form is the leanest and should be preferred whenever possible.