Golang 的函數式數據結構

【導讀】go 語言不強調可變和不可變。本文中作者記錄了學習數據結構和函數式編成語言 Scala 的過程中對 go 語言的思考。

這個東西有很多叫法，比如函數式（Functional）數據結構，持久化（persist）數據結構，或者不可變（Immutable）數據結構。函數式數據結構似乎最早出現在 CMU 教授 Chris Okasaki 的 Purely Functional Data Structures 文章中。教條主義的說（其實我個人不是很喜歡太教條），函數式數據結構的反義詞是命令式數據結構，它強調的是該數據結構可以在修改後，舊的版本不會丟失，可以（和新的）同時被引用。比如，並查集就是一種命令式數據結構，因爲每次添加節點都是在並查集的數組上直接修改。可以看到，函數式數據結構的典型特點是不可變。

按照 MIT 數據結構課上的概念，函數式持久化是最高級別的持久化。它將持久化分爲 4 種：

1. 部分持久化（Partial Persistence）。舊的版本只能查詢，不能修改。

2. 完全持久化（Full Persistence）。允許修改舊版本，這意味着可能形成樹結構。

3. 可合併持久化（Confluent Persistence）。類似於 Git，可以將不同的版本合併成一個新的版本。

4. 函數式。不會修改舊的數據結構，永遠創建新的。

爲什麼函數式是最強的呢？這一點你可以思考一下，或者直接看 MIT 的課程教案。

函數式數據結構其實已經不是一個新鮮的概念了。我自己也不是從 Go 語言接觸的，而是 Scala。另外在 JavaScript 裏也有對應的庫實現。值得一提的是，現代編譯器技術對於這種數據結構的運用：由於現代 IDE 都實現了諸如 intellisense，refactor 等功能，當我們不斷修改代碼時，實際上 AST 在時刻變化。這種多版本的變化與持久數據結構有天然的聯繫。

你也可以在 Infoq 或者油管看一下 Daniel Spiewak 小哥在 13 年講的視頻。本文受了許多他的啓發，包括下面的一些圖片也是來自於該演講。

結構共享

函數式數據結構有結構共享這樣的思想並不令人意外。難點在於如何共享。以最簡單的單鏈表爲例。假設我們有head，tail和 List 的拼接方法，可能會形成的結果是：

img

可能你會問，如果這裏修改任意節點，比如 B 的話不就無法共享了嗎？實際上確實如此，修改後就需要 COW。這就是爲什麼這裏視頻中小哥使用了 Scala 作爲示例的原因。Scala 的 List 嚴格限制了對數據結構的操作方法，避免了這種隨機的修改。但是，我們依然可以實現一個 Immutable 的Add和Remove：

package persist

import "errors"

var (
 IsEmpty = errors.New("List is empty")
 nilList = &Empty{}
)

type List interface {
 // return the head of the list.
 Head() interface{}

 // return the tail of the list.
 Tail() List

 // return true if the list is empty.
 IsEmpty() bool

 // return count of items in the list.
 Len() int

 // add item to the head of list.
 Add(head interface{}) List

 // insert item at the specific position.
 // will throw error if position is invalid.
 Insert(val interface{}, pos int) (List, error)

 // remove item at the specific position.
 //will throw error if position is invalid.
 Remove(pos int) (List, error)
}

type Empty struct{}

func New() *Empty {
 return nilList;
}

func (e *Empty) Head() interface{} {
 return nil
}

func (e *Empty) Tail() List {
 return nil
}

func (e *Empty) Len() int {
 return 0
}

func (e *Empty) Add(head interface{}) List {
 return &list{head, e}
}

func (e *Empty) Insert(val interface{}, pos int) (List, error) {
 if pos == 0 {
  return e.Add(val), nil
 }
 return nil, IsEmpty
}

func (e *Empty) Remove(pos int) (List, error) {
 return nil, IsEmpty
}

func (e *Empty) IsEmpty() bool {
 return true
}

type list struct {
 head interface{}
 tail List
}

func (l *list) Head() interface{} {
 return l.head
}

func (l *list) Tail() List {
 return l.tail
}

func (l *list) IsEmpty() bool {
 return false
}

func (l *list) Len() int {
 cur := l.Tail()
 length := 1
 for !cur.IsEmpty() {
  length += 1
  cur = cur.Tail()
 }
 return length
}

func (e *list) Add(head interface{}) List {
 return &list{head, e}
}

func (l *list) Insert(val interface{}, pos int) (List, error) {
 if pos == 0 {
  return l.Add(val), nil
 }
 tail, err := l.tail.Insert(val, pos-1)
 if err != nil {
  return tail, err
 }
 return tail.Add(l.head), nil
}

func (l *list) Remove(pos int) (List, error) {
 if pos == 0 {
  tail := l.Tail()
  return tail, nil
 }

 re, err := l.tail.Remove(pos - 1)
 if err != nil {
  return nil, err
 }
 return &list{l.head, re}, nil
}

其實我比較想用繼承來實現 Empty（即 Scala 的 Nil），但是 Golang 的組合不太方便實現多態。

可以看到這裏在Add時進行了遞歸。舉個例子，當圖中 C 後繼插入一個新節點時，C 必須構造一個新鏈 C' 指向原先的 B，同時 B 必須也要照做，以此類推，也就是一種蝴蝶效應。當然用遞歸從性能上也許不太完美，但因爲 Golang 也沒有實現 TOC（tail call optimization），所以…… 就這樣吧。

這裏的思路其實是一種路徑拷貝：將每次修改經過的節點全部複製一遍。實際上，可持久化平衡樹多應用了這種思想。

均攤

均攤（Amortization）這一概念常見於算法分析中。

考慮怎麼實現一個函數式的隊列。前面的單鏈表實際上是一個棧，它的不可變部分非常明顯。如果依然用單鏈表實現隊列，則出隊和入隊必須有一個需要! O(n) 的開銷（原因很簡單，考慮前面的持久化鏈表在尾部插入和刪除的開銷，即使你設置一個指向尾部的指針依然如此）。

在 Programming in Scala 一書中，有一個章節的例子實現了這種思路的函數式隊列，當時讓我覺得非常巧妙（和老爺子在 Coursera 的網課風格一樣，基本上名曰講語言實則學習數據結構，這就是大師嗎）。

我們設置兩個鏈表，leading 和 trailing ，分別表示隊列中靠前和靠後的元素，不過 trailing 是反向的。每次元素從 trailing 進，從 leading 出。如果 leading 爲空就將 trailing 一次性倒入 leading。當然還可以更巧妙一些，當 leading 的大小小於 trailing 時就倒入——這實際上跟 Java 裏 ArrayList 之類的集合擴容類似。

Daniel Spiewak 把這個算法叫做銀行家隊列（Banker's Queue），其實更準確來說是均攤分析中記賬方法對於這種持久化隊列的應用，並不能說是代表着這個算法。它來自於 Chris Okasaki 的文章。

順便一提，這個思路刷題的小夥伴肯定很熟悉：它是 LeetCode 上一道 easy 難度的題，用棧實現隊列。所以其實很多算法還是水很深的啊。

Finger Tree

Scala 的隊列是用前面說的算法實現的。當然它也可以用於 Deque。不過，對於雙端隊列還有一種實現是 Finger Tree（沒搜到國內的翻譯，就湊合一下吧）。Finger Tree 的論文是用 Haskell 寫的，有興趣可以瞅瞅。或者看看浙大的高材生這篇入門的介紹：Finger Tree 的簡單介紹和實現。https://zhuanlan.zhihu.com/p/30589105

Finger Tree 本身也是很簡單的，就是把左右兩邊最遠端連在一起：

img

從這個圖上雖然可以直觀理解 Finger Tree 的意圖，但並不好理解其實現。Finger Tree 實際上是一種自頂向下的結構，這一點和一般的多叉樹不同：比如最典型的 B 樹，標準的流程都是先通過本身的搜索樹特性找到葉節點然後插入。Finger Tree 從頂部插入，而後擴散到樹的每一層，整個過程和 B 樹的分裂、合併是非常類似的。這個過程可以完美用遞歸來表示。看一下 wiki 上演示的插入和刪除過程：

img

由於 Golang 沒有 union type（順帶一提，這個是 Go 2 中正在討論的特性，希望可以通過，畢竟 TS 都有），因此 Finger Tree 寫起來並不優雅。比如 Finger Tree 用 Haskell 最簡單的定義是這樣的：

data FingerTree a 
  | Empty
  | Single a
  | Deep (Digit a) (FingerTree (Node a)) (Digit a)

type Digit a = Digit [a]

這裏有兩種關鍵子結構：Digit 和 Node。Digit 本身是一個 作爲緩衝區的 List，它的長度可以是 1-4 個元素。它對應的是第一個圖中被連起來的線上的節點，和第二個圖中淺藍色的節點。Node 是其他非葉子節點，對應圖二中深藍色節點。我們知道，2-3 樹具有自平衡的特性。典型的 2-3 Finger Tree，2-3 指的就是 Node 的孩子個數。這裏 還有一個 Deep，表示 Finger Tree 的核心，即圖二中綠色節點。它實際上不代表原本樹（比如圖一）中的任何節點，而是一種遞歸結構的抽象。

因爲 Finger Tree 本身實現比較麻煩，這裏只給出一個追加節點的 golang 僞代碼：

type four [4]interface{}

type three [3]interface{}

type two [2]interface{}

func (t *ftree) Append(val interface{}) *ftree {
 switch suffix := t.suffix.(type) {
 case four:
  pushdown := &three{
   suffix[0],
   suffix[1],
   suffix[2],
  }
  return &ftree{
   t.prefix,
   &two{
    suffix[3],
    val,
   },
   t.tree.Append(pushdown),
  }
 default:
  return &ftree{
   t.prefix,
   suffix.Append(val),
   t.tree,
  }
 }
}

這裏當樹中右子樹追加元素溢出時，就會分裂成 three 節點和 two 節點，同時將 three 節點向下傳遞，遞歸進行追加。刪除操作與此類似，當節點是一個 one 節點時，就對上述操作反過來進行，把下層的節點重新移到上層來。在此過程中，消除不必要的中間節點。

可以看到，Finger Tree 是不可變的，每次我們都是構造新的節點和新的樹，且新的節點和樹總是和舊的共享結構。這裏 three 節點、two 節點等我都是使用數組別名來表示。注意到這裏的 interface{} 不僅僅表示可以傳任意類型的數據，實際上還有可能是指針——代碼中 pushdown 變量就是一個 three 節點的指針。這意味着每次 pushdown 的時候，Deep 兩邊的深度都會倍增。前面說過，Finger Tree 是自頂向下的，這就是 Finger Tree 的好處——由於 Finger Tree 的結構和傳統的多叉樹相反，因此每次添加和刪除節點都能以最小代價進行 copy。同時，Finger Tree 是對稱的，因此不論 head 和 tail 都是從頂部獲取，所以 Finger Tree 的查詢時間複雜度也是漸進於! O(1) 的。

在 Scala 裏我只在 Vector 裏看到過 Finger Tree 的影子。爲什麼不用 Finger Tree 實現前面的函數式隊列呢？原因是 Finger Tree 只具有理論上的最優，而在工程實踐中，Finger Tree 有大量引用不同對象的指針（否則，JVM 可以像鏈表一樣通過優化它們在堆中的位置來提高性能），不具有很好的數據本地性。

Bitmapped Vector Trie

這裏就簡單說下思路好了。

首先 Vector 是一種順序數據結構（比如鏈表）和隨機訪問數據結構（平衡樹）的折中，它允許順序和隨機的訪問。Vector Trie 一詞就是使用 trie 來表示的 Vector。說實話這種叫法我還沒有在正式的場合看到。Bitmapped Vector Trie 是由 Closure 中最早實現的一種不可變數據結構——然而並不爲人所知的是，這一數據結構的設計也受到 Scala 團隊的影響。

Bitmapped Vector Trie 正如他的名字一樣，是一種按照比特位劃分的字典樹。通常這個樹的度是 32，與 Cache Line 相同（正如 B + 樹總是和磁盤塊相關），從而可以完美的利用緩存來提高性能。Bitmapped Vector Trie 也使用了路徑拷貝進行持久化，同時考慮到某些時候存在朝生暮死的版本，會使用版本號來控制 COW（也就是說，某些情況下並不是完全的 COW，而是 mutable 的）。爲什麼使用字典樹而不是自平衡的搜索樹呢？我想是因爲字典樹並不需要進行平衡操作（該操作在 persist 要求下開銷變大），且樹的深度是穩定的。

最後，函數式數據結構有什麼好處呢？除了對函數式的支持（因此 Go 語言不是一門函數式語言），它提供了一種額外的併發範式。不過 CSP 和 Immutable 之間更多是一種替代關係，而不是像 Mutex 是一種補強，所以 Golang 沒有包含也是情理之中。

轉自：

juejin.cn/post/6844904133502173191

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/OyNFsZBPlMKbXCWZktEqmw