Scala入門・ゼロと後者関数

Scala

動機

自然数ってゼロとサクセサーだよね。

概要

という自然数の作り方がある。

Scalaの1つの特徴は、コンストラクタ以外のパターンマッチが書けること。
一般に関数型言語でパターンマッチができるのは、コンストラクタが単射な関数で、
逆関数があるから。
Scalaでは、自分で逆関数らしきものを書けば(元の関数がなくても)パターンマッチができるようになる。
これを利用して、Int(の部分集合)がゼロとサクセサーに見えるようにする。

実装

まず、ゼロを表現するオブジェクトZeroを定義する。

  • 0 : Intを返すapplyを定義する。
  • 0 : Intが来たらtrueを返す関数unapplyを定義する。

(パターンマッチのためには必ずしもapplyはいらない)

object Zero {
  def main(args : Array[String]) : Unit = {
    //this (singleton) object
    println(Zero)
    
    //this.apply
    println(Zero())
    
    //this.unapply
    println(unapply(0))
    println(unapply(1))
  }
  
  def apply() = 0
  def unapply(n : Int) : Boolean = n == 0
}

ZeroとZero()の違いが紛らわしい…。

次に、サクセサーを表現するオブジェクトSuccを定義する。

  • 0からMath.MAX_INT-1までのIntが来たら1を足して返す関数applyを定義する。
  • 1以上のIntが来たら1を引いてSomeに入れて返す関数unapplyを定義する。

Intはオーバーフローするので、MAX_INTのサクセサーは考えない。

object Succ {
  def main(args : Array[String]) : Unit = {
    println(Succ(2))
    println(unapply(3))
    //Exception
//    println(apply(Math.MAX_INT))
  }
  
  def apply(n : Int) : Int = {
    if(n >= 0 && n < Math.MAX_INT) (n + 1) else { throw new RuntimeException }    
  }
  
  def unapply(n : Int) : Option[Int] = {
    if(n <= 0) None else Some (n - 1)
  }
}

すると、ゼロとサクセサーでパターンマッチが書けるようになる。
これで階乗関数を書いてみたのが、下のFactorial。
applyの中でマイナスを書かなくてよいのがよいと思う。

object Factorial {
  def main(args : Array[String]) : Unit = {
    for(i <- 0 to 10){
      println(i + "! = " + Factorial(i))
    }
    for(i <- 0 to 100){
      i match {
        case Factorial(n) => println(i + " = " + n + "!")
        case _ =>
      }
    }
  }
  
  def apply(n : Int) : Int = {
    n match {
      case Succ(n2) => n * apply(n2)
      case Zero() => 1
    }
  }
  
  def unapply(n : Int) : Option[Int] = {
    var m = n
    var i = 1
    while(n > 0) {
      if (m % i != 0) return None
      m = m / i
      if (m == 1) return Some(i)
      i = i + 1
    }
    None
  }
}

ついでにFactorial.unapplyも書いてみた。
1以上の階乗は単射な関数なので、
逆関数を書くことで、階乗にマッチするようなパターンを書くことができる。
なお、unapply(apply(0)) = Some 1になるのがあまりよろしくない。

実行結果

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
1 = 1!
2 = 2!
6 = 3!
24 = 4!