Construindo os números naturais em Scala

Esse post é bastante baseado em uma das aulas do curso Functional Programming Principles in Scala, disponível gratuitamente aqui.

Em matemática, os axiomas de Peano permitem a construção dos números naturais como conhecemos. A ideia desse rascunho é mostrar uma maneira de construir os números naturais usando alguns desses axiomas explicitamente.

Os axiomas de maior importância para a gente serão:

• Existe um número natural chamado Zero;
• Para todo número natural n, o sucessor de n, denotado por S(n), é um número natural;
• Não existe um número natural k, tal que S(k) = Zero, isto é, Zero não possui predecessores;
• A função S:N -> N de números naturais para números naturais é injetiva (m=n se e somente se S(m)=S(n)).

Na prática, esses axiomas não são suficientes para produzir os números naturais porque ainda não há garantia de que todo número natural é o sucessor de um número natural (ver axioma da indução), mas não vamos nos preocupar com isso, de nada afetará nossa brincadeira!

Pois bem.
De cara, temos que S(Zero) é um número natural, e portanto S(S(Zero)), S(S(S(Zero))) e etc são números naturais também.

Como definimos a adição para esses caras? Sejam m e S(n) números naturais, definimos:

1. m + Zero = m
2. m + S(n) = S(m+n)

Se quiser brincar um pouco, tente mostrar que essa soma é comutativa (isto é, que m + n = n + m ).

Beleza! Vamos seguir para o Scala. Vamos começar definindo uma abstract class Nat que representará os naturais.

import java.util.NoSuchElementException

abstract class Nat {
  def isZero: Boolean
  def predecessor: Nat
  def successor: Nat
  def + (that: Nat): Nat
  def - (that: Nat): Nat
}

Para quem não conhece Scala, você pode ignorar isso e pensar que estamos definindo as funções que objetos do conjunto dos números naturais possuem, e quais são suas assinaturas!

O próximo passo, é definir o objeto Succ (o sucessor) e descrever os métodos que foram listados na super classe dos naturais (por exemplo, quando executamos o método isZero para um objeto Succ, esperamos que ele retorne false):

class Succ(n: Nat) extends Nat {
  def isZero: Boolean = false
}

Ótimo! Agora, sempre que tivermos um Succ(n) e executarmos o método isZero (escrevendo Succ(n).isZero), recebermos o booleano false, como desejado.

Note que a classe Succ necessita de um predecessor para ser instanciada, o que faz sentido.. se ele é sucessor, ele sucede alguém.

O próximo passo é implementar o método predecessor, que deve retornar o predecessor de Succ(n):

class Succ(n: Nat) extends Nat {
  def isZero: Boolean = false

  def predecessor: Nat = n
}

Evidentemente, se temos Succ(n), onde n é um número natural (possivelmente Zero), o seu predecessor é n!

O método successor também é trivial:

class Succ(n: Nat) extends Nat {
  def isZero: Boolean = false

  def predecessor: Nat = n

  def successor: Nat = new Succ(this)
}

Isto é, o sucessor de um sucessor é o sucessor do sucessor! Note que this é uma auto-referência ao próprio objeto, então Succ(n).successor = Succ(Succ(n)).

Agora, vamos implementar algo mais divertido, o método + (a soma) para sucessores:

class Succ(n: Nat) extends Nat {
  def isZero: Boolean = false

  def predecessor: Nat = n

  def successor: Nat = new Succ(this)

  def +(that: Nat): Nat =
    if (!that.isZero) new Succ(this + that.predecessor)
    else this
}

O que o método + faz? Vamos tomar um exemplo de soma de S(S(S(Zero))) + S(S(Zero)):

1. S(S(S(Zero))) + S(S(Zero))
2. S(S(S(S(Zero))) + S(Zero))
3. S(S(S(S(S(Zero))) + Zero))
4. S(S(S(S(S(Zero))))

Podemos imaginar que o algoritmo encapsula o primeiro termo com S() ao mesmo tempo que ele remove S() do segundo, até que este se torne Zero, onde retornamos somente o primeiro termo.

Agora, vamos implementar o método -, a ideia é parecida:

class Succ(n: Nat) extends Nat {
  def isZero: Boolean = false

  def predecessor: Nat = n

  def successor: Nat = new Succ(this)

  def +(that: Nat): Nat =
    if (!that.isZero) new Succ(this + that.predecessor)
    else this

  def -(that: Nat): Nat = {
    if (that.isZero) this
    else (this.predecessor - that.predecessor)
}

Vamos usar o mesmo exemplo para analisar esse método:

1. S(S(S(Zero))) - S(S(Zero))
2. S(S(Zero)) - S(Zero)
3. S(Zero) - Zero
4. S(Zero)

Neste caso, pegamos o predecessor de ambos termos ao mesmo tempo, até que o segundo termo se torne Zero! O que fazer quando o primeiro termo for menor que o segundo? Teríamos um número negativo nesse caso! Mas olhando para o algoritmo, notamos que antes de atingir os número negativos, teríamos que realizar uma operação da forma Zero - (algo), e ainda não implementamos o método de subtração para o Zero! Portanto, vamos começar a implementar os métodos do objeto Zero!

Assim como para o Succ, começamos com o método isZero:

object Zero extends Nat {
    def isZero: Boolean = true
}

Obviamente, será true quando executarmos ele para um objeto Zero.

Uma pequena observação é que estamos definindo um object aqui em Scala. Na prática, isto se traduz para o fato que existe somente um elemento de Nat com essas propriedades, então não podemos instanciar dois caras da "classe" Zero!

Agora, vamos implementar o método predecessor para o Zero. Claramente, pelo nome, ele deve retornar o predecessor do Zero:

object Zero extends Nat {
    def isZero: Boolean = true

    def predecessor: Nat = 
    new throw java.util.NoSuchElementException("no predecessor for zero")
}

Mas opa! É claro que o predecessor do Zero não deve existir, como dita um dos axiomas. Para contornar esse problema, fazemos com que o código, ao executar Zero.predecessor, jogue um erro (uma exception) para você, informando que não há um predecessor para o Zero!

Agora, implementando o successor de Zero:

object Zero extends Nat {
    def isZero: Boolean = true

    def predecessor: Nat = 
    new throw java.util.NoSuchElementException("no predecessor for zero")

    def successor: Nat = new Succ(this)
}

Aqui, estamos dizendo que o sucessor do Zero é simplesmente um novo cara da classe Succ(this). Como já dito, this significa uma auto-referência a própria classe, então na prática, estamos dizendo que o sucessor de Zero é o sucessor do Zero (Succ(Zero))!

Agora, definindo a o método de soma + para o Zero:

object Zero extends Nat {
  def isZero: Boolean = true

  def predecessor: Nat = throw new NoSuchElementException("no predecessor for zero")

  def successor: Nat = new Succ(this)

  def + (that: Nat): Nat = new Succ(this)
}

Como esperado, quando executamos Zero + that, retornamos that! Pois n + 0 = n!

Por fim, como definir a subtração - para os casos Zero - that?

object Zero extends Nat {
  def isZero: Boolean = true

  def predecessor: Nat = throw new NoSuchElementException("no predecessor for zero")

  def successor: Nat = new Succ(this)

  def + (that: Nat): Nat = new Succ(this)

  def - (that: Nat): Nat =
    if (that.isZero) Zero
    else throw new java.util.NoSuchElementException("no negative naturals allowed")
}

Novamente, como não há um predecessor para o zero, fazemos o código jogar um erro ao tentar fazer uma soma da forma 0 - n, com n diferente de Zero!

Isso conclui tudo que precisamos para construir os números naturais em Scala! É fácil verificar que os outros axiomas são respeitados e você está convidado para testar isso.

Para brincar, aproveitei e implementei um método toString em ambos casos para descrever ao código como exibir esses objetos. No caso, a regra que implementei é:

1. Succ(n) => "S(S(S(S(...n-vezes...S(0))"
2. Succ(0) => "S(0)"

O código completo com essa implementação está disponível abaixo:

import java.util.NoSuchElementException

abstract class Nat {
  def isZero: Boolean
  def predecessor: Nat
  def successor: Nat
  def + (that: Nat): Nat
  def - (that: Nat): Nat
}

class Succ(n: Nat) extends Nat {
  def isZero: Boolean = false

  def predecessor: Nat = n

  def successor: Nat = new Succ(this)

  def +(that: Nat): Nat =
    if (!that.isZero) new Succ(this + that.predecessor)
    else this

  def -(that: Nat): Nat = {
    if (that.isZero) this
    else (this.predecessor - that.predecessor)
  }


  override def toString(): String = {
    if (!n.isZero) "S(" + n.toString() + ")"
    else "S(0)"
  }
}

object Zero extends Nat {
  def isZero: Boolean = true

  def predecessor: Nat = throw new NoSuchElementException("no predecessor for zero")

  def successor: Nat = new Succ(this)

  def + (that: Nat): Nat = new Succ(this)

  def - (that: Nat): Nat =
    if (that.isZero) Zero
    else throw new java.util.NoSuchElementException("no negative naturals allowed")

  override def toString(): String = {
    return "0"
  }
}

Agora, vamos testar algumas operações!

1. S(S(S(0))) + S(S(0)) = ?

val n = new Succ(new Succ(Zero)) // S(S(0))
val m = new Succ(new Succ(new Succ(Zero))) // S(S(S(0)))
val s = n + m // S(S(S(0))) + S(S(0))

Resultado:
val s: Nat = S(S(S(S(S(0)))))

1. S(S(S(0))) - S(S(0)) = ?

val d = m - n // S(S(S(0))) - S(S(0))

Resultado:
val d: Nat = S(0)

1. Zero + S(S(S(0))) = ?

Zero + m

Resultado:
val res1: Nat = S(S(S(0)))

1. S(S(S(0))) + Zero = ?

m + Zero

Resultado:
val res1: Nat = S(S(S(0)))

PS 2: Não citei em nenhum momento, mas é óbvio que podemos traduzir nossa notação para a notação usual de números naturais, isto é:

• Zero => 0
• S(Zero) => 1
• S(S(Zero)) => 2
• S(S(S(S..n-vezes..S(Zero)))..) => n