-1

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

  • 2
    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
  • 1
    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
  • 1
    @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
5

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.

| improve this answer | |
  • 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
3

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:

Addition:

  • 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 Ints to their corresponding Nats.

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 records 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]
| improve this answer | |
  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.