Scalaz（23）－ 泛函資料結構： Zipper-遊标定位

  外面沙塵滾滾一直向北去了，意識到年關到了，碼農們都回鄉過年去了，而我卻留在這裡玩弄“拉鍊”。不要想歪了，我說的不是褲裆拉鍊而是scalaz zipper，一種泛函資料結構遊标（cursor）。在函數式程式設計模式裡的集合通常是不可變的（immutable collection），我們會發現在fp程式設計過程中處理不可變集合（immutable collection）資料的方式好像總是缺些什麼，比如在集合裡左右逐漸遊動像movenext,moveprev等等，在一個集合的中間進行添加、更新、删除的功能更是欠奉了，這主要是因為操作效率問題。不可變集合隻有對前置操作（prepend operation）才能獲得可靠的效率，即對集合首位元素的操作，能得到相當于o(1)的速度，其它操作基本上都是o(n)速度，n是集合的長度，也就是随着集合的長度增加，操作效率會以倍數下降。還有一個原因就是程式設計時會很不友善，因為大多數程式都會對各種集合進行大量的操作，最終也會導緻程式的複雜臃腫，不符合函數式程式設計要求的精簡優雅表達形式。我想可能就是因為以上各種原因，scalaz提供了zipper typeclass幫助對不可變集合操作的程式設計。zipper的定義如下：scalaz/zipper.scala

它以stream為基礎，a可以是任何類型，無論基礎類型或高階類型。zipper的結構如上：目前焦點視窗、左邊一串資料元素、右邊一串，形似拉鍊，因而命名zipper。或者這樣看會更形象一點：

scalaz提供了zipper建構函數可以直接用stream生成一個zipper:

zipperend生成倒排序的zipper:

scalaz也為list，nonemptylist提供了zipper建構函數：

都是先轉換成stream再生成zipper的。zipper本身的建構函數是zipper，在nonemptylist的zipper生成中調用過：

用這些串形結構的建構函數産生zipper同樣很簡單：

有了串形集合的zipper建構方法後我們再看看一下zipper的左右遊動函數：

start,end,move,next,previous移動方式都齊了。還有定位函數：

操作函數如下：

insert,modify,delete也很齊備。值得注意的是多數zipper的移動函數和操作函數都傳回option[zipper[a]]類型，如此我們可以用flatmap把這些動作都連接配接起來。換句話說就是我們可以用for-comprehension在option的context内實作行令程式設計（imperative programming）。我們可以通過一些例子來示範zipper用法：

我在上面的程式裡在for{...}yield裡面逐條添加指令進而示範遊标目前焦點和集合元素跟随着的變化。這段程式可以說就是一段行令程式。

回到上面提到的效率和代碼品質讨論。我們提過scalaz提供zipper就是為了使集合操作程式設計更簡明優雅，實際情況是怎樣的呢？

舉個例子：有一串數字，比如：list(1,4,7,9,5,6,10), 我想找出第一個高點元素，它的左邊低，右邊高，在我們的例子裡是元素9。如果我們嘗試用習慣的行令方式用索引去編寫這個函數：

哇！這東西不但極其複雜難懂而且效率低下，重複用find索引導緻速度降到o(n * n)。如果用array會把效率提高到o(n),不過我們希望用immutable方式。那麼用函數式程式設計方式呢？

用模式比對（pattern matching）和遞歸算法（recursion），這段程式好看多了，而且效率也可以提高到o(n)。

但我們再把情況搞得複雜一點：把高點值增高一點（+1）。還是用fp方式編寫：

代碼又變得臃腫複雜起來。看來僅僅用fp程式設計方式還不足夠，還需要用一些新的資料結構什麼的來幫助。scalaz的zipper可以在這個場景裡派上用場了：

用zipper來寫程式表達清楚許多。這裡用上了zipper.positions：

positions函數傳回類型是zipper[zipper[a]]符合findnext使用。我們前面已經提到：使用zipper的成本約為o(n)。