Scala by Example‎ > 演習6.0.2解答案 その1

このScala by Example‎ > 演習6.0.2のNat、Succは自然数の定義でもあるペアの公理まんまですね。
公理を限りなく数式に近い形でプログラムで表現できるのはまさに関数型ならではなのでしょうか。

Succの実装がよく分からない…と思ったら、これも原文と違っちゃってますね。

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

最初+の実装でかなり悩んだのですが、具体的な値を考えたら理解できました。

自然数2=Succ(Succ(Zero))
自然数3=Succ(Succ(Succ(Zero)))

2+3= Succ(Succ(Zero))  +  Succ(Succ(Succ(Zero)))
      =  Succ(Succ(Zero)).+(Succ(Succ(Succ(Zero)))) 
                   <= プラスメソッドに3を渡しているのと同じ
      =  Succ(Zero)  +  (Succ(Succ(Succ(Zero)))).successor
                   <= プラスメソッドを展開すると、前の2は1に、後ろの3は3の次の数4になる
     =  Succ(Zero) + (Succ(Succ(Succ(Succ(Zero)))))
                     <= 1+4に変換された
     =  Zero + (Succ(Succ(Succ(Succ(Succ(Zero))))))
                     <= 再度プラスメソッドを展開すると、0+5になる
     =  (Succ(Succ(Succ(Succ(Succ(Zero))))))
                     <=  Zeroのプラスメソッドはthatを返すだけなので5が返却される

どうしても＋という記号から再帰がイメージしにくいですね。
慣れが必要ですね。

やっと本題です。
Scala by Example‎ > 演習6.0.2の解答案その1です。自然数と符号で整数を表現する方法です。

ようするに、Natが絶対値のような役割を担えばいいんですね。

  class Integer(x: Nat, sign: Boolean) {
    def isPositive: Boolean = sign
    def negate: Integer = new Integer(x, !sign)
    def isZero: Boolean = if (x.isZero) true else false
    def next(s: Boolean): Integer = if (this.isZero || this.isPositive == s) new Integer(x.successor, s)
    else new Integer(x.predecessor, !s)
    def predecessor: Integer = next(false)
    def successor: Integer = next(true)
    def shift(n: Integer, m: Integer): Integer = {
      if (n.isZero) m
      else
        shift(n.predecessor, m.successor)
    }
    def +(that: Integer): Integer = if (this.isPositive) shift(this, that)
    else shift(this negate, that negate) negate
    def -(that: Integer): Integer = this + that.negate
  }

もう一つの方法にもチャレンジしてみます。