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, "")
  }