Missing features: Persistent data structure and Pattern Matching

12th鐵人賽 kotlin functional programming software development

hungyanbin

團隊Kotlin 鐵人陣

2020-09-30 20:25:57

906 瀏覽

上一篇的解答：

fun <R> map(transform: (T) -> R): LinkedList<R> {
    return when(this) {
        Nil -> Nil
        is Cons -> Cons(transform(head), tail.map(transform))
    }
}

map 使用遞迴就可以輕鬆的實作出來了，但是要小心！要是呼叫的層數太多，遞迴是會產生 StackOverflow exception 的，因此這種實作無法用在實際的產品上，如果要避免 StackOverflow exceptio 的話，應該要使用 tailrec ，再加上一些調整才能完成，但是由於我時間不夠，還沒想出來最適合的實作，如果事後比較有時間的話，會再補上的！

Structure sharing

Structure sharing 是什麼呢？上一篇所介紹的 LinkedList 有著 structure sharing 的特性，只要一直持續不斷的往頭 ( addhead )加上新元素，就不需要複製一份完整的 list ，可以直接使用它：

val listA = linkedListOf(1, 2, 3, 4)
// keeps immutablility && saves memory
val listB = Cons(0, listA)

上面的 listA 與 listB 分享了同一個結構，也分享了相同的記憶體空間，所以才叫做 structure sharing。接著，如果想要做 insert 的話，也不需要複製一整份 list，下面範例的 insert 發生在第零個元素跟第一個元素之間，這兩個 List 彼此共用了 [2, 3, 4] 。

val listA = linkedListOf(1, 2, 3, 4)

// 1
val firstElement = (list as Cons).head
// [2, 3, 4]
val subList = (list as Cons).tail
// [1, 0, 2, 3, 4], still immutable
val listAfterInsrted = Cons(head, Cons(0, subList))

有著 Structure sharing 特性的資料結構又稱為 Persistent Data Structure，常見的實作有 LinkedList, Map, Sets, Trees。在純函式程式語言裡，Persistent Data Structure 幾乎是必備的，坦白說，這個觀念也是我從另一個純函式程式語言（Elixir）學來的，因此說明應該還有很多不足之處。另外，對於 functional programming 非常友善的 Scala 也有 Persistent Data Structure 相關的支援。

（Structure sharing for Tree, 圖片取自 Wiki, 圖中的 d 與 d' 共享了 b 這個 node）

那麼問題來了， Kotlin 官方有沒有這樣的資料結構呢？根據我目前的搜尋，其實是有的，請參考這個連結：

https://github.com/Kotlin/kotlinx.collections.immutable

這個 Repo 從 2016 年就開始了，看起來還是有持續的在維護，有 immutableList 與 persistentList , persistentSet 等等不同的資料結構，已經有相當程度的實作內容了，但我不知道為什麼現在的版本號還是 0.33 ，我猜未來可能還會有所變動。總之，這還不是一個正式版本，只能期望在將來會把這些東西放在 standard library 來讓我們可以使用。

Pattern matching

Pattern matching 這概念也是從另一個程式語言學來的，非常像是 when 在做的事，但是 pattern matching 是一個更強大版本的 when ，這邊直接使用別人的例子：

sealed class Download
data class App(val name: String, val developer: Person) : Download()
data class Movie(val title: String, val director: Person) : Download()
val download: Download = // ...

// Without pattern matching:
val result = when(download) {
  is App -> {
    val (name, dev) = download
    when(dev) {
      is Person -> 
        if(dev.name == "Alice") "Alice's app $name" else "Not by Alice"
      else -> "Not by Alice"
    }
  }
  is Movie -> {
    val (title, diretor) = download
    if (director.name == "Alice") {
      "Alice's movie $title"
    } else {
      "Not by Alice"
    }
  }
}

上面的程式碼中有五個不一樣的分支，結果分別是 "Alice's app $name", "Not by Alice", "Not by Alice", "Alice's movie $title" , "Not by Alice" , 其中 "Not by Alice" 就出現了三次，這是因為 when 只能用來做單層的判斷，如果還有另外一層需要被判斷的話，就會有另一個 if 或是 when ，在閱讀上就相對的不容易。以下是 when 的加強版：

val result = when(download) {
  is App(name, Person("Alice", _)) -> "Alice's app $name"
  is Movie(title, Person("Alice", _)) -> "Alice's movie $title"
  is App, Movie -> "Not by Alice"
}

上面的加強版可以同時判斷 Type 跟 class 成員變數的內容，如果可以這樣使用的話，是不是簡潔多了呢？。上面的這個寫法是網路上某個人在 KEEP 提出的 perposal ，相關討論以及內容請參考這連結：

https://github.com/Kotlin/KEEP/pull/213

或是參考這影片：https://www.youtube.com/watch?v=Blj-7SGYUnE

小結

昨天跟今天兩篇帶大家認識到 immutability 所帶來的效能瓶頸以及相關解法，透過 Structure sharing 的特性，讓我們同時可以節省記憶體空間又不會失去 immutability。然而，難過的消息是，這方面的支援在 Kotlin 還不是非常成熟，不僅如此，還有部分其他函式程式語言的特性也還沒支援，像是 Pattern Matching 還有 Scala 的 Higher kinded types( Higher kinded types 這特性是用來方便的寫 Monad ，KEEP 上也有 - https://github.com/Kotlin/KEEP/pull/87/files/374e8489c0ed185aed7597e8ddb0d4212a27d58f )

。

了解這些限制，可以讓我們在寫 functional programming 時關注到更多面向，避免寫出效能不好的程式碼，另外鼓勵大家多多學習不同的程式語言，了解各程式語言的優點與缺點，看看這程式語言擅長或是不擅長解決某些問題，思考問題看的更深、更廣，有助於將來的職涯發展。