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