Scala by Example‎ > 演習7.2.2解答案

Scala by Example > 演習7.2.2の解答案です。

  abstract class IntTree
  case object EmptyTree extends IntTree
  case class Node(elem: Int, left: IntTree, right: IntTree) extends IntTree
  def insert(t: IntTree, v: Int): IntTree = t match {
    case Node(e, l, r) => if (e > v) Node(e, insert(l, v), r)
    else if (e < v) Node(e, l, insert(r, v))
    else t
    case EmptyTree => Node(v, EmptyTree, EmptyTree)
  }

  def contains(t: IntTree, v: Int): Boolean = t match {
    case Node(e, l, r) => if (e == v) true
    else if (e > v) contains(l, v)
    else if (e < v) contains(r, v)
    else false
    case EmptyTree => false
  }

IntSetと比べるとcaseクラスを使う事により大分すっきりしていますね。

Scala by Example‎ > 演習6.0.3解答案その2

Scala by Example > 演習6.0.3の解答案その2です。

ヒントその2をベースにした解答です。

あるいは３つの子クラスとして Zero を 0 に、Succ を正の数のため、Pred を負の数のために使い、既知の Nat 実装を Integer へ一般化できます

ちょっと意味が分からない…原文を読んだ結果、NatをIntegerに改造して、その子クラスを3つ作れば良いと解釈しました。

  abstract class Integer {
    def isZero: Boolean
    def predecessor: Integer
    def successor: Integer
    def +(that: Integer): Integer
    def -(that: Integer): Integer
    def isPositive: Boolean
    def negate: Integer
  }

  object Zero extends Integer {
    def isZero: Boolean = true
    def isPositive: Boolean = false
    def predecessor: Integer = new Pred(Zero)
    def successor: Integer = new Succ(Zero)
    def +(that: Integer): Integer = that
    def -(that: Integer): Integer = that.negate
    def negate: Integer = this
  }

  class Succ(x: Integer) extends Integer {
    def isZero: Boolean = false
    def isPositive: Boolean = true
    def predecessor: Integer = x
    def successor: Integer = new Succ(this)
    def +(that: Integer): Integer = x + that.successor
    def -(that: Integer): Integer = x - that.predecessor
    def negate: Integer = {
      def iter(x: Integer, result: Integer): Integer = {
        if (x.isZero) result
        else
          iter(x.predecessor, result.predecessor)
      }
      iter(this, Zero)
    }
  }

  class Pred(x: Integer) extends Integer {
    def isZero: Boolean = false
    def isPositive: Boolean = false
    def predecessor: Integer = new Pred(this)
    def successor: Integer = x
    def +(that: Integer): Integer = x + that.predecessor
    def -(that: Integer): Integer = x - that.successor
    def negate: Integer = {
      def iter(x: Integer, result: Integer): Integer = {
        if (x.isZero) result
        else
          iter(x.successor, result.successor)
      }
      iter(this, Zero)
    }
  }

negateをもっとうまく書けないですかねー。

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
  }

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

Scala by Example‎ > 演習6.0.2解答案

Scala by Example > 演習6.0.2の解答案です。

  trait IntSet {
    def incl(x: Int): IntSet
    def contains(x: Int): Boolean
    def union(set: IntSet): IntSet
    def intersection(set: IntSet): IntSet
    def excl(x: Int): IntSet
    def isEmpty: Boolean
  }

  class EmptySet extends IntSet {
    def contains(x: Int): Boolean = false
    def incl(x: Int): IntSet = new NonEmptySet(x, new EmptySet, new EmptySet)
    def union(set: IntSet): IntSet = set
    def intersection(set: IntSet): IntSet = new EmptySet
    def excl(x: Int) = this
    def isEmpty = true
  }

  class NonEmptySet(elem: Int, left: IntSet, right: IntSet) extends IntSet {
    val e: Int = elem
    val l: IntSet = left
    val r: IntSet = right
    def contains(x: Int): Boolean =
      if (x < elem) left contains x
      else if (x > elem) right contains x
      else true
    def incl(x: Int): IntSet =
      if (x < elem) new NonEmptySet(elem, left incl x, right)
      else if (x > elem) new NonEmptySet(elem, left, right incl x)
      else this
    def union(set: IntSet): IntSet = {
      def iter(set: IntSet, result: IntSet): IntSet = {
        set match {
          case n: NonEmptySet =>
            iter(n.r, iter(n.l, result incl n.e))
          case _ => result
        }
      }
      iter(set, this)
    }
    def intersection(set: IntSet): IntSet = {
      def iter(set: IntSet, result: IntSet): IntSet = {
        set match {
          case n: NonEmptySet =>
            iter(n.r, iter(n.l, if (this contains n.e) result incl n.e else result))
          case _ => result
        }
      }
      iter(set, new EmptySet)
    }
    def excl(x: Int): IntSet = {
      def iter(set: IntSet, result: IntSet): IntSet = {
        set match {
          case n: NonEmptySet => iter(n.r, iter(n.l, if (n.e == x) result else result incl n.e))
          case _ => result
        }
      }
      if (this contains x)
        iter(this, new EmptySet)
      else
        this
    }
    def isEmpty = false
  }

case使ったせいでisEmptyが不要に…

Scala by Example‎ > 演習6.0.1解答案

Scala by Example‎ > 演習6.0.1の解答案です。

これも翻訳がちょっと分かりにくかったのですが、要するに和集合と積集合を求めよ、ということですね。

  trait IntSet {
    def incl(x: Int): IntSet
    def contains(x: Int): Boolean
    def union(set: IntSet): IntSet
    def intersection(set: IntSet): IntSet
  }

  class EmptySet extends IntSet {
    def contains(x: Int): Boolean = false
    def incl(x: Int): IntSet = new NonEmptySet(x, new EmptySet, new EmptySet)
    def union(set: IntSet): IntSet = set
    def intersection(set: IntSet): IntSet = new EmptySet
  }

  class NonEmptySet(elem: Int, left: IntSet, right: IntSet) extends IntSet {
    val e: Int = elem
    val l: IntSet = left
    val r: IntSet = right
    def contains(x: Int): Boolean =
      if (x < elem) left contains x
      else if (x > elem) right contains x
      else true
    def incl(x: Int): IntSet =
      if (x < elem) new NonEmptySet(elem, left incl x, right)
      else if (x > elem) new NonEmptySet(elem, left, right incl x)
      else this
    def union(set: IntSet): IntSet = {
      def iter(set: IntSet, result: IntSet): IntSet = {
        set match {
          case n: NonEmptySet =>
            iter(n.r, iter(n.l, result incl n.e))
          case _ => result
        }
      }
      iter(set, this)
    }
    def intersection(set: IntSet): IntSet = {
      def iter(set: IntSet, result: IntSet): IntSet = {
        set match {
          case n: NonEmptySet =>
            iter(n.r, iter(n.l, if (this contains n.e) result incl n.e else result))
          case _ => result
        }
      }
      iter(set, new EmptySet)
    }
  }

NonEmptySetの要素にアクセスできないとどうにもならないなあ…とメンバ変数を付け足したら、なんだか長くなってしまいました。
EmptySetのメンバ変数をうまく定義できればmatchも無くせそうです。
そもそもメンバ変数すら不要だったりするのでしょうか？

以下はデバッグ用です。Treeを奇麗に出力するのはあきらめました。

  def printIntSet(set: IntSet): String = {
    def iter(set: IntSet, result: String): String = {
      set match {
        case n: NonEmptySet =>
          iter(n.r, iter(n.l, result + n.e.toString + ","))
        case _ => result
      }
    }
    iter(set, "")
  }

Scala by Example‎ > 演習5.3.1解答案

Scala by Example‎ > 演習5.3.1の解答案です。
立方根なので、

x = y * y * y
y = x / ( y * y )

を補正関数に使います。

def cube(x: Double) = fixedPoint(averageDamp(y => x / (y * y)))(1.0)

Scala by Example‎ > 演習5.2.1〜5.2.4解答案

Scala by Example‎ > 5.2 カリー化 (Currying)の演習問題の解答案です。

演習 5.2.1

この問題ですが、??を埋めてもコンパイルエラーになって変だなと思ったら、原文とちょっと違ってますね。

原文の問題

def sum(f: Int => Int)(a: Int, b: Int): Int = {
  def iter(a: Int, result: Int): Int = {
    if (??) ??
    else iter(??, ??)
  }
  iter(??, ??)
}

原文に沿った解答にしました。

def sum(f: Int => Int)(a: Int, b: Int): Int = {
  def iter(a: Int, result: Int): Int = {
    if (a > b) result
    else iter(a + 1, f(a) + result)
  }
  iter(a + 1, f(a))
}

演習 5.2.2

末尾再帰での計算を積に変えただけです。

def product(f: Int => Int)(a: Int, b: Int): Int = {
  def iter(a: Int, result: Int): Int = {
    if (a > b) result
    else iter(a + 1, f(a) * result)
  }
  iter(a + 1, f(a))
}

演習 5.2.3

def factorial(n: Int): Int = product(x => x)(1, n)

演習 5.2.4

違いが末尾再帰でのresult反映方法だけなので、その部分を関数引数で指定できるようにしてみました。

def func(f: Int => Int, g: (Int, Int) => Int)(a: Int, b: Int): Int = {
  def iter(a: Int, result: Int): Int = {
    if (a > b) result
    else iter(a + 1, g(f(a), result))
  }
  iter(a + 1, f(a))
}