Construindo os números naturais em Scala
Tags: scala, numerosnaturais, functional, math
Published: 2021-04-09 08:21:07

Esse post é bastante baseado em uma das aulas do curso Functional Programming Principles in Scala, disponível gratuitamente [aqui](https://www.coursera.org/learn/progfun1/home/welcome).

Em matemática, os [axiomas de Peano](https://en.wikipedia.org/wiki/Peano_axioms) 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](https://en.wikipedia.org/wiki/Mathematical_induction#Axiom_of_induction)), 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.

```scala
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):

```scala
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):

```scala
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:

```scala
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:

```scala
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))
5. 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:

```scala
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`:

```scala
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:

```scala
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:

```scala
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:

```scala
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?

```scala
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:

```scala
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)) = ?
```scala
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)))))
```

2. S(S(S(0))) - S(S(0)) = ?
```scala
val d = m - n // S(S(S(0))) - S(S(0))

Resultado:
val d: Nat = S(0)
```

3. Zero + S(S(S(0))) = ?
```scala
Zero + m

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

4. S(S(S(0))) + Zero = ?
```scala
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