# Trying to understand how this class representation truly represents Natural numbers in Scala

Following Martin Odersky's course on coursera - Functional Programming with Scala and I'm on Week 4 where we're learning about Types and Pattern Matching. In the video lecture, this is the representation of a Natural Number:

``````abstract class Nat {
def isZero: Boolean
def predecessor: Nat
def successor: Nat = new Succ(this)
def + (that: Nat): Nat
def - (that: Nat): Nat = if (that.isZero) this else (predecessor - that.predecessor)
}

object Zero extends Nat { // for a zero
def isZero = true
def predecessor = throw new NoSuchElementException
def + (that: Nat) = that
}
class Succ(n: Nat) extends Nat { // for non-zero (positive) numbers
def isZero = false
def predecessor = n
def + (that: Nat) = n + that.successor
}
``````

My questions are:

1. when I create a `val two = new Succ(2)` why would I set the `two.predecessor = 2` when `2`'s predecessor is actually `1`?

2. When I call `two + new Succ(4)` internally why am I evaluating `2 + successor of 4` and not `new Succ(2 + 4)`?

3. In the main abstract class `Nat`, the `successor` field is intialised with a `Succ` object. Wouldn't the value of `successor` be the same as the object that was just constructed?

I'm just ...unable to grasp the relationship/implementation here ...

PS - I do have a Java background if that helps

• I'm having trouble seeing where the Software Engineering-relevant problem (as defined in the help center) is in your question. It looks like you have trouble understanding basic math (this is just the standard Peano-representation of natural numbers you learned in high school) and basic Scala syntax (there are no fields in that code). Note that "Explaining code" is explicitly called out in the help center as "may still be off-topic". – Jörg W Mittag Sep 11 at 4:52
• I apologize. Perhaps this is off-topic. Also, was never exposed to Peano numbers during high school. From the video i thought it was piano numbers misspelled (that's what the subtitles said too) as Peano. Thank you for pointing me to the right direction. – Saturnian Sep 11 at 5:09
• Maybe it helps to see that `new Succ(2)` does not represent the number two, but its successor, which is three. – pschill Sep 11 at 6:16
• Also, be aware that no integers are involved here. The code only uses the types `Boolean`, `Nat`, `Zero`, `Succ`. So there is no `new Succ(2)`, because `2` does not have the type `Nat`. – pschill Sep 11 at 6:21
• @FilipMilovanović: Peano numbers are commonly used to represent numbers in type-level metaprogramming, e.g. in C++ Templates, or Haskell and Scala Types. Precisely because they have nothing except functions available as "building blocks". (A generic type `T<C>` is essentially a function at type-level.) – Jörg W Mittag Sep 11 at 18:46

when I create a `val two = new Succ(2)` why would I set the `two.predecessor = 2` when 2's predecessor is actually `1`?

You can't call `new Succ(2)`, as Succ needs to have an object of type `Nat` as argument, and the literal 2 is not of type `Nat`.

Succ is defined as the natural number succeeding (or following) the Nat object given as its argument. With the code presented, you can do things like this

``````val zero = new Zero
val one = new Succ(zero)
val two = new Succ(one)
val three = two + one
``````

Note that there isn't an integer literal in sight.

• I see! I guess this makes sense. You can only start "making" objects in the order so that it makes sense logically. This helps! Thank you! – Saturnian Sep 11 at 18:14

The encoding shown here is based on the Peano Axioms for natural numbers:

1. `Z` ∈ ℕ. (Existence of zero.)

2. x ∈ ℕ: x = x. (Reflexivity of equality.)

3. x, y ∈ ℕ: x = yy = x. (Symmetry of equality.)

4. x, y, z ∈ ℕ: x = yy = zx = z. (Transitivity of equality.)

5. a, b: b ∈ ℕ ∧ a = ba ∈ ℕ. (Closure under equality.)

6. n ∈ ℕ: S(n) ∈ ℕ. (Closure under S.)

7. m, n ∈ ℕ: m = n IFF and only if S(m) = S(n). (S is injective.)

8. n ∈ ℕ: S(n) = 0 is false. (Z is not the successor of any natural number.)

9. If K is a set such that:

• Z is in K, and
• for every natural number n, n being in K implies that S(n) is in K,

then K contains every natural number. (Axiom of induction.)

These axioms rigorously define every natural number with the properties that we commonly expect of natural numbers. Based on these Axioms, we can then also define the arithmetic operations recursively:

• a + Z = a. (Zero is the additive identity.)
• a + S(b) = S(a + b).

Multiplication:

• a · Z = Z. (Zero is the multiplicative Zero element.)
• a · S(b) = a + a · b.

It is these definitions and axioms that are used in the implementation of natural numbers that you showed.

when I create a `val two = new Succ(2)` why would I set the `two.predecessor = 2` when `2`'s predecessor is actually `1`?

First off, you cannot instantiate a `Succ` with an `Int` argument, as the constructor only takes a `Nat`. But, let's assume that we have an implicit conversion in scope somewhere that would allow us to convert `Int`s to their corresponding `Nat`s.

The second problem here is simply a problem of variable naming: your variable named `two` represents the concept of the natural number three, that is where your confusion lies. Three's predecessor is obviously 2, so that is correct.

When I call `two + new Succ(4)` internally why am I evaluating `2 + successor of 4` and not `new Succ(2 + 4)`?

Because you can't. Again, the constructor of `Succ` takes a `Nat` as argument, not an `Int`. Using Scala's built-in numbers would completely defeat the purpose of teaching how to define numbers using Scala, would you agree?

What this does, is effectively just shift the "successorness" of the number from the left operand to the right operand. So, we are turning S(a) + b into a + S(B).

Why are we doing that? Because we have defined our base case for the recursive definition of addition inside the `Zero` object to just return the right operand. Which means, in order for our recursion to terminate, we need to make sure that the left operand reaches `Zero` at some point, and the only way to do that, is to "peel off" one layer of successorness from the left operand and stick it onto the right operand.

Assuming, you want to add 2 + 3, what happens is this:

``````Succ(Succ(Zero)) + Succ(Succ(Succ(Zero))) // calls Succ.+
Succ(Zero) + Succ(Succ(Succ(Succ(Zero)))) // calls Succ.+
Zero + Succ(Succ(Succ(Succ(Succ(Zero))))) // calls Zero.+
Succ(Succ(Succ(Succ(Succ(Zero)))))        // … which returns 5
``````

In the main abstract class `Nat`, the `successor` field is intialised with a `Succ` object. Wouldn't the value of `successor` be the same as the object that was just constructed?

I don't quite understand what "be the same as the object that was just constructed" means. However, there is a fundamental misconception in your question: `successor` is not a field, it is a method. Fields are defined with `val`, methods are defined with `def`.

So, this constructs a new successor every time it is called.

I do have a Java background if that helps

Here is how that same implementation would look like in Java (I'm gonna use Java 14 `record`s to save me some typing for the constructor and `toString`, but it could just as well be written with classes):

``````interface Nat {
boolean isZero();

Nat predecessor();
default Nat successor() { return new Succ(this); }

Nat plus(Nat that);
default Nat minus(final Nat that) {
return that.isZero() ? this : predecessor().minus(that.predecessor());
}

public static void main(final String[] args) {
final var two = Zero.ZERO.successor().successor();
final var three = two.successor();

System.out.println(two.plus(three));
// Succ[n=Succ[n=Succ[n=Succ[n=Succ[n=Zero]]]]]
}
}

final class Zero implements Nat { // for a zero
private Zero() {};
public static final Zero ZERO = new Zero();

@Override public boolean isZero() { return false; }
@Override public Nat predecessor() { throw new java.util.NoSuchElementException(); }
@Override public Nat plus(final Nat that) { return that; }
}

record Succ(final Nat n) implements Nat { // for non-zero (positive) numbers
@Override public boolean isZero() { return true; }
@Override public Nat predecessor() { return n; }
@Override public Nat plus(final Nat that) { return n.plus(that.successor()); }
}
``````

Here's a slightly expanded version in Scala 3, with an implicit conversion from `Int` to `Nat`:

``````sealed trait Nat:
val isZero: Boolean
def predecessor: Nat
def successor: Nat = Succ(this)
def +(that: Nat): Nat
def -(that: Nat): Nat = if that.isZero then this else predecessor - that.predecessor
override def toString(): String

object Zero extends Nat: // for a zero
override val isZero = true
override def predecessor = throw new NoSuchElementException
override def +(that: Nat) = that
override def toString() = "0"

final case class Succ(n: Nat) extends Nat: // for non-zero (positive) numbers
override val isZero = false
override def predecessor = n
override def +(that: Nat) = n + that.successor
override def toString() = s"S\${n}"

object Nat:
given int2Nat as Conversion[Int, Nat] =
_ match
case 0 => Zero
case n if n > 0 => Succ(n - 1)
case _ => throw new IllegalArgumentException
``````

And a couple of test cases demonstrating usage:

``````import org.junit.Test
import org.junit.Assert._

class TestNat:
@Test def plus() =
val two = Zero.successor.successor
val three = two.successor
val five = two + three
assertEquals("SSSSS0", s"\${five}")

@Test def minus() =
val two = Zero.successor.successor
assertEquals("S0", s"\${two - Succ(Zero)}")

@Test def conversion() =
//import Nat.int2Nat
val one = Succ(0)
assertEquals("S0", s"\${one}")
``````

You might ask yourself why the author of the course chose this particular exercise. Is that really how we define numbers in functional languages?

Well … actually that depends on the functional language. Especially in Dependently-Typed Languages, it is somewhat common to define natural numbers this way, because it has nice properties for proving theorems about programs. Functional programs are often written using recursion, and having an inductively defined data type matches perfectly with recursive processing of that data type.

For example, this is how lists are typically defined in functional languages. (In fact, this is exactly how lists are defined in Scala, modulo some efficiency tricks):

``````sealed trait List[+A]:
val isEmpty: Boolean
def map[B](f: A => B): List[B]
override def toString(): String

case object Nil extends List[Nothing]:
override val isEmpty = true
override def map[B](f: Nothing => B) = this
override def toString() = "[]"

final case class ::[+A](head: A, tail: List[A]) extends List[A]:
override val isEmpty = false
override def map[B](f: A => B) = ::(f(head), tail map f)
override def toString() = s"\${head} :: \${tail}"

val nums = ::(1, ::(2, ::(3, ::(4, Nil))))
val squares = nums.map(n => n*n)
println(squares)
//1 :: 4 :: 9 :: 16 :: []
``````

Or, trees:

``````sealed trait Tree[A]
case object Leaf extends Tree[Nothing]
final case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]
``````
• THIS!!! This is brilliant representation. The issue with my understanding was that a `Succ` was initialized with an `Int` and not a `Nat`. And that every object will be sequentially constructed. I failed to understand that Peano system is represented as `Succ(Succ(Zero))` for a `2` in the decimal system or a `10` in the binary system. The java code helped me understand that a bit better! Thanks a ton, kind sir! – Saturnian Sep 11 at 18:18