Scala By Example: 类和对象 习题

1. 二叉树的 union 和 intersection

首先，作为山寨程序员，必要的补课是在所难免的：Binary Tree

很不幸的是，在看了 Wiki、Google 和算法导论后，我并没有看到一个非常权威的关于二叉树的 union / intersection 定义。所以，我做了小小的猜测，并实现对 Binary Tree 中所有元素的 union / intersection。当然，很快，我就有了新的想法。

1: trait IntSet { 2: def incl(x: Int): IntSet 3: def contains(x: Int): Boolean 4: def union(that: IntSet): List[Int] = that.toList -- toList ++ toList 5: def intersection(that: IntSet): List[Int] = 6: toList -- (toList -- that.toList) 7: def isEmpty = this == EmptySet 8: def toList: List[Int] 9: } 10:  11: object EmptySet extends IntSet { 12: def contains(x: Int) = false 13: def incl(x: Int): IntSet = new NonEmptySet(x, this, this) 14: def toList: List[Int] = List() 15: } 16:  17: class NonEmptySet(elem: Int, left: IntSet, right: IntSet) extends IntSet { 18: def contains(x: Int) = 19: if(x < elem) left contains x 20: else if(x > elem) right contains x 21: else true 22: def incl(x: Int): IntSet = 23: if(x < elem) new NonEmptySet(elem, left incl x, right) 24: else if(x > elem) new NonEmptySet(elem, left, right incl x) 25: else this 26: def toList: List[Int] = 27: (List(elem) ++ left.toList ++ right.toList).distinct 28: }

在这里，我提前实现了 isEmpty。但是出于少打两个字的目的，代码中隐隐有些味道。首先，isEmpty 的实现直接放在 trait 中，这很好，但是这个实现依赖到了 EmptySet 的实现，也就是说，两者间产生了双向的耦合。其次，我用到了 List 的 -- / ++方法，而这两个方法都已经不推荐使用了，更好的方法是 list1 filterNot (list2 contains)。但不光光是这些味道，在写下 excl 方法的同时，我忽然意识到，其实在这个二叉树实现中，由于 incl 方法对 x 的大小进行了判断，所以左树和右数是有顺序的，从而 union 和 intersection 是有着另外的非常明显的含义的。不过，这些还是放着和 excl 一起实现吧。

2. 实现 excl(x: Int) 来排除某个元素（顺便实现 isEmpty）

习题 1，2 答案

1: trait IntSet { 2: def incl(x: Int): IntSet 3: def excl(x: Int): IntSet 4: def contains(x: Int): Boolean 5: def union(that: IntSet): IntSet 6: def intersection(that: IntSet): IntSet 7: def isEmpty: Boolean 8: } 9:  10: object EmptySet extends IntSet { 11: def contains(x: Int) = false 12: def incl(x: Int): IntSet = new NonEmptySet(x, EmptySet, EmptySet) 13: def excl(x: Int): IntSet = EmptySet 14: def isEmpty = true 15: def union(that: IntSet) = that 16: def intersection(that: IntSet): IntSet = EmptySet 17: override def toString = "E" 18: } 19:  20: class NonEmptySet(elem: Int, left: IntSet, right: IntSet) extends IntSet { 21: def contains(x: Int) = 22: if(x < elem) left contains x 23: else if(x > elem) right contains x 24: else true 25: def incl(x: Int): IntSet = 26: if(x < elem) new NonEmptySet(elem, left incl x, right) 27: else if(x > elem) new NonEmptySet(elem, left, right incl x) 28: else this 29: def isEmpty = false 30: def excl(x: Int): IntSet = 31: if(x < elem) new NonEmptySet(elem, left excl x, right) 32: else if(x > elem) new NonEmptySet(elem, left, right excl x) 33: else left union right 34: def union(that: IntSet): IntSet = 35: if(that.isEmpty) this 36: else left union right union that.incl(elem) 37: def intersection(that: IntSet): IntSet = 38: if(that.isEmpty) EmptySet else { 39: val s = left union right intersection that 40: if(that contains elem) s.incl(elem) else s 41: } 42: override def toString = "" + elem + "[" + left + ", " + right + "]" 43: } 44:  45: val s1 = EmptySet incl 2 incl 12 incl 3 incl 4 incl 9 46: val s2 = EmptySet incl 12 incl 4 incl 15 incl 2 incl 33 47:  48: println(s1 union s2) 49: println(s1 intersection s2)

在新的实现中，我多打了N个字，消除了设计中的耦合，同时 union 和 intersection 也变成返回新的 IntSet 的方法。

3. 实现 Integer

先前实现了自然数 Nat，那么只需要加上符号支持，那么自然数就可以扩展为整数

1: class Integer(abs: Nat, sign: Boolean) { 2: def isZero = abs.isZero 3: def isPositive = if(isZero) false else sign 4: def predecessor = 5: if(isPositive) new Integer(abs.predecessor, isPositive) 6: else new Integer(abs.successor, isPositive) 7: def successor = 8: if(isPositive || isZero) new Integer(abs.successor, true) 9: else new Integer(abs.predecessor, false) 10: def + (that: Integer): Integer = 11: if(that.isZero) this 12: else if(that.isPositive) successor + that.predecessor 13: else predecessor + that.successor 14: def - (that: Integer): Integer = this + (that.negate) 15: def negate = new Integer(abs, !isPositive) 16: def p { 17: if(isZero) println("") 18: else if(isPositive) { 19: print("#") 20: predecessor.p 21: } else { 22: print("-") 23: negate.p 24: } 25: } 26: }

PS. 新浪围脖被老妈关注了，从此不能畅所欲言

PS II. 学习数据结构很重要，做程序员不能山寨到底。

Technorati 标签: Scala