Scala 筆記10 - Binary search tree union

課堂中有個binary search tree例子的邏輯讓我感到很不直覺，但又讓人驚嘆FP能寫出優美的expression （不過看code的人可能會有點傷腦筋）：

首先我們有以下兩種node定義，Empty class是leaf node:

non-leaf node則是NonEmpty class:

既然是binary search tree，就滿足left-tree elem < right-tree elem。看看NonEmpty的union方法 ((left union right) union other) incl elem

1. 首先 (left union right) 會一直往下traverse，直到遇到兩個children都是leaf node的NonEmpty object，由於left和right都是Empty object，所以(left union right) = right, (right union other) = other，而other incl elem就會把這個NonEmpty node elem給incl到sibling的tree中

2. trace過會發現，這個expression的執行path的確就是其語意，非常神奇，但是隔了幾年要我在寫出來，我還是寫不出來。

我寫成以下的版本：

def union(other: Inset): Inset = {
  val incl1 = other.incl(elem)
  val incl2 = left.union(incl1)
  right.union(incl2)
}

這算是top-down的方法，而課堂中的方法為bottom-up方法，後者對我來說比較不直覺！