Functional Data Structure

12th鐵人賽 kotlin functional programming software development

hungyanbin

團隊Kotlin 鐵人陣

2020-09-29 01:07:30

1138 瀏覽

分享至

上次的解答：

fun <P1, P2, P3, R> ((P1, P2, P3) -> R).curried(): (P1) -> (P2) -> (P3) -> R {
    return { p1: P1 ->
        { p2: P2 ->
            { p3: P3 ->
                this(p1, p2, p3)
            }
        }
    }
}

fun <P1, P2, P3, P4, R> ((P1, P2, P3, P4) -> R).curried(): (P1) -> (P2) -> (P3) -> (P4) -> R {
    return { p1: P1 ->
        { p2: P2 ->
            { p3: P3 ->
                { p4: P4 ->
                    this(p1, p2, p3, p4)    
                }
            }
        }
    }
}

ArrayList and LinkedList for immutable List

在我們學習資料結構時，一定都會遇到這兩種資料結構的比較：ArrayList V.S. LinkedList。例如在新增一個 item 時，ArrayList 所花費的成本是如何， LinkedList 所花類的成本又是如何，又例如在獲取某個位置的 item 時，這兩種資料結構所花費的成本各是如何。然而這些問題都是建立在一個共同基礎上，就是這些資料結構都是 "mutable" 的。如果今天資料結構是 immutable 的話，這些問題的答案又是什麼呢？

Indexing

在獲取某個位置的 item 時，是怎樣的情況呢？先從 ArrayList 來看，一個 immutable 的 ArrayList，獲取 item 的方式其實跟 mutable 的方式沒什麼不同，只要知道位置，就可以以 O(1) 的時間複雜度拿到該 item，另外也不會有任何的空間複雜度。如果是 LinkedList 呢？LinkedList 獲取某個位置的 item 時，只能從頭開始，一個一個掃過去即可，最差的情況是最後一個才拿到，所以時間複雜度是 O(n) ，空間複雜度也是幾乎等於 0 。所以以這個角度來看的話， immutable List 跟 mutable List 是沒什麼不同的。

Modifying

對於一個 immutable ArrayList 來說，是不允許修改長度以及內容的，所以唯一的辦法是，複製出一個新的 ArrayList，然後再加以修改，所以對於時間複雜度與空間複雜度都是 O(n) ，對比於 mutable ArrayList ，需要多出許多空間來儲存！那如果是 LinkedList 呢？是否一樣是 O(n) 呢？

讓我們仔細想想，LinkedList 所儲存的是一個指標，或是以 Java 來說，就是一個 object reference。為了要新增一個 item，而新增的是第一個位置的 item 的話，需要做哪些事呢？

class LinkedList<T>(val head: Node<T>?) 
class Node<T>(val value: T, val next: Node<T>?)

// 原來的 LinkedList
// "A" -> "B" -> "C" -> "D"
val a = LinkedList(Node("A", Node("B", Node("C", Node("D", null))))
// 新增一個 Z 在前面
"Z" -> "A" -> "B" -> "C" -> "D"
val b = TODO("implement a.addHead("Z")")

上面所列的是一個 String Linked List，為了要完成剛剛所說的需求，現在讓我們實作一個 function - addHead，這個 function 的功能是可以從頭新增一個新的 item。

第一步，建立一個 LinkedList ，加入第一個 Node("Z", ??) ，得到了一個 LinkedList(Node("Z"), ??) 。接下來，拿出原本 List 的第一個元素的值 "A" ，建立一個新的 Node("A", ??) ，那麼就可以拿這個新建立的 Node 填入剛剛 Node("Z", ??) 的第二個參數，變成了 Node("Z", Node("A", ??)) 。就這樣，持續新增下去，空間複雜度跟時間複雜度就也是 O(n) 了。但是，我們真的只有這個做法嗎？如果只是把 reference 給新的 LinkedList 會發生什麼事呢？

val a = LinkedList(Node("A", Node("B", Node("C", Node("D", null))))
val b = LinkedList("Z", a.head)

時間複雜度空間複雜度是多少呢？各是 O(1) 對吧！幾乎不用做什麼事，也不需要因為要複製 List 而產生出新的 Node 。然而，你可能懷疑，這樣的 LinkedList 是 immutable 的嗎？他們都共用這些 Node ，共用變數不會有危險嗎？然而事實上，不管是 LinkedList 或是 Node ，他們都是只能讀不能寫的 (因為全部的參數都是 val) 類別，所以以這樣的方式建立 LinkedList ，永遠都會是 immutable。這樣的策略，其實跟 copyOnWrite 非常的相似，如果不熟悉 copyOnWrite 的朋友，非常推薦去弄懂這概念喔。

Add head operation
Time complexity : [ArrayList] - O(n), [LinkedList] - O(1)
Space complexity: [ArrayList] - O(n), [LinkedList] - O(1)

Create our own implementation

事實上，這種資料結構在很多語言都是有支援的，有著不一樣的名字，例如在 Scala 中， Node 就被取代為 Cons (Constructor) ， ? 被取代為 Nil。讓我們試著寫出 Kotlin 版本的實作以及各種不同的 operator 吧！

sealed class LinkedList<out T> {}

object Nil: LinkedList<Nothing>()

class Cons<out T>(val head: T, val tail: LinkedList<T> = Nil): LinkedList<T>()

另一種版本的 LinkedList 在這裡是一個 sealed class ， Nil 跟 Cons 繼承自 LinkedList ，這樣的設計同時也形成一個遞迴式的 Algebraic Data Type ：

"x | y" -> Sum Type
"(x, y)" -> Product Type

LinkedList = Nil | (T, LinkedList)    -> Sum Type and Product Type

由於這是一個 sealed class ，所以這個 Algebraic Data Type 的外層是一個 Sum Type ，不是 Nil 就是 Cons ，其中 Cons 又是一個 type T 與 LinkedList 的 Product type 。

接下來，看看他的基本使用方法吧：

// ["A", "B", "C"]
val list1 = Cons("A", Cons("B"), Cons("C"))
// []
val list2 = Nil
// ["A", "B", "C", "D"]
val list3 = Cons("A", Cons("B"), Cons("C", Cons("D", Nil)))

但是這樣寫實在是很麻煩啊～～還是替他寫一個類似 listOf 的函式吧，這個函式的名字就稱他為 linkedListOf ：

fun <T> linkedListOf(vararg values: T): LinkedList<T> {
    val consCreator = { head: T, tail: LinkedList<T> -> Cons(head, tail) }

    return values.toList()
        .reversed()
        .asSequence()
        .map { value -> consCreator.curried()(value) }
        .fold( Nil as LinkedList<T> , { tail, creator -> creator(tail) })
}

上面的實作稍微難了一點，在這之中還有用到上一篇的 curried ，基本上這邊實作的想法是，從最後一個 value 開始，一直往前包。首先建立一個 Nil 當作是預設的 tail ，然後再跟最後一個值一起包成一個 Cons ，並將它記錄起來，到下一輪的時候這個 Cons 就會是下一個 LinkedList 的 tail ，跟倒數第二個的值一起再包成下一個 Cons ，依此類推，一直包到第一個值為止。

所以第一個 operator 才會是 reversed ，就是為了反過來包。接下來，介紹一下 consCreator ，consCreator 是一個建立 Cons 的函式，沒有什麼魔法，就跟建構子是一樣的。然後這個 consCreator 呢，如果使用 curried 之後以及填入第一個參數 head（也就是 "A", "B", "C" 等等），就能得到另一個函式，一個只差 tail 就能建立出 Cons 的函式，這也是倒數第二行在做的事情。所以到這邊，我們有一個 list ，裡面放的都是沒有 tail 的 Cons 建構函式，這邊的任務就只差把這些 Cons 接起來了，最後再使用 fold 將所有的函式組合起來，就得到我們要的資料結構了。

實作完之後我們就可以用更方便的方式來建構 LinkedList 了：

// [1, 2, 3]
val list1 = linkedListOf(1, 2, 3)
// ["A", "B", "C", "D"]
val list2 = linkedListOf("A", "B", "C", "D")
// Nil
val list3 = linkedListOf<String>()

head, tail, isEmpty

依據 Scala 官網中的文件（https://www.tutorialspoint.com/scala/scala_lists.htm），第一個出現的就是這三個函式，所以我們也來實做看看這三個函式吧：

//Demo code for scala:
object Demo {
   def main(args: Array[String]) {
      val fruit = "apples" :: ("oranges" :: ("pears" :: Nil))
      val nums = Nil

      println( "Head of fruit : " + fruit.head )
      println( "Tail of fruit : " + fruit.tail )
      println( "Check if fruit is empty : " + fruit.isEmpty )
      println( "Check if nums is empty : " + nums.isEmpty )
   }
}

// Output 
Head of fruit : apples
Tail of fruit : List(oranges, pears)
Check if fruit is empty : false
Check if nums is empty : true

首先最簡單的就是 head 啦！根本什麼事都不用做，至於 tail 的話呢，就要做點事了。為了要輸出正確的訊息：“List(oranges, pears)”，必須要 override toString() 才行，以下是 toString() 的實作：

override fun toString(): String {
        return when(this) {
            Nil -> "LinkedList()"
            is Cons -> {
                var result = "LinkedList("
                var currentList = this
                while (currentList is Cons) {
                    result += currentList.head.toString()
                    currentList = currentList.tail
                    if (currentList is Cons) {
                        result += ", "
                    }
                }
                "$result)"
            }
        }
    }

雖然這系列文是 functional programming ，但我可沒說我不寫 Imperative code XD ，如果 toString 的實作也全部都要 immutable 的話，就必須要用到遞迴了，寫遞迴不是一個簡單的任務，只能含淚跳過了。而且這邊的程式碼並不會破壞到使用方，任何使用 LinkedList 的程式還是保有 immutable 的特性的。

有了 toString 的實作， tail 就沒問題了，然後是 isEmpty 的實作，非常簡單：

fun isEmpty(): Boolean = this == Nil

最後將上面的 Scala 程式碼轉為 Kotllin 版本試試看吧：

fun linkedListTest() {
    val fruit = linkedListOf("apples", "oranges", "pears") as Cons<String>
    val nums = Nil

    println( "Head of fruit : " + fruit.head )
    println( "Tail of fruit : " + fruit.tail )
    println( "Check if fruit is empty : " + fruit.isEmpty() )
    println( "Check if nums is empty : " + nums.isEmpty() )
}

執行會得到一樣的結果。

小結

今天介紹了一種不太一樣的 LinkedList，這種專門為 functional programming 而存在的資料結構還有個名詞，就是 Functional Data structure ，另外除了 LinkedList 之外，還有很多不一樣的 Functional Data structure ，可以針對各種情況，非常高效率的去做計算或是修改，不會因為 immutable 的這個限制，一直不斷的 copy，而需要非常多的額外空間來儲存。

今天又有小練習了！今天的練習是替 LinkedList 加上 map 的實作！試試看用遞迴的作法來完成吧！