iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 21
0
Software Development

Functional Programming in Kotlin系列 第 21

Missing features: Persistent data structure and Pattern Matching

上一篇的解答:

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)

上面的 listAlistB 分享了同一個結構,也分享了相同的記憶體空間,所以才叫做 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 相關的支援。

https://upload.wikimedia.org/wikipedia/commons/thumb/5/56/Purely_functional_tree_after.svg/876px-Purely_functional_tree_after.svg.png

(Structure sharing for Tree, 圖片取自 Wiki, 圖中的 dd' 共享了 b 這個 node)

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

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

這個 Repo 從 2016 年就開始了,看起來還是有持續的在維護,有 immutableListpersistentList , 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 時關注到更多面向,避免寫出效能不好的程式碼,另外鼓勵大家多多學習不同的程式語言,了解各程式語言的優點與缺點,看看這程式語言擅長或是不擅長解決某些問題,思考問題看的更深、更廣,有助於將來的職涯發展。


上一篇
Functional Data Structure
下一篇
Type system and nullability
系列文
Functional Programming in Kotlin30

尚未有邦友留言

立即登入留言