Scalaz（34）－ Free ：算法－Interpretation

  我們說過自由資料結構（free structures）是表達資料類型的最簡單結構。list[a]是個資料結構，它是生成a類型monoid的最簡單結構，因為我們可以用list的狀态cons和nil來分别代表monoid的append和zero。free[s,a]是個代表monad的最簡單資料結構，它可以把任何functor s升格成monad。free的兩個結構suspend,return分别代表了monad的基本操作函數flatmap,point，我特别強調結構的意思是希望大家能意識到那就是記憶體heap上的一塊空間。我們同樣可以簡單的把functor視為一種算法，通過它的map函數實作運算。我們現在可以把monad的算法flatmap用suspend[s[free[s,a]]來表示，那麼一段由functor s（adt）形成的程式（ast）可以用一串遞歸結構表達：suspend(s(suspend(s(suspend(s(....(return)))))))。我們可以把這樣的ast看成是一串連結的記憶體格，每個格記憶體放着一個算法adt，代表下一個運算步驟，每個格子指向下一個形成一串連續的算法，組成了一個完整的程式（ast）。最明顯的分别是free把monad flatmap這種遞歸算法化解成記憶體資料結構，用記憶體位址指向代替了遞歸算法必須的記憶體堆棧（stack）。free的interpretation就是對存放在資料結構suspend内的算法（adt）進行實際運算。不同方式的interpreter決定了這段由一連串adt形成的ast的具體效果。

free interpreter的具體功能就是按存放在資料結構suspend内的算法（adt）進行運算後最終擷取a值。這些算法的實際運算可能會産生副作用，比如io算法的具體操作。scalaz是通過幾個運算函數來提供free interpreter，包括：fold,foldmap,foldrun,runfc,runm。我們先看看這幾個函數的源代碼：

我們應該可以看出interpreter的基本原理就是把不可運算的抽象指令adt轉換成可運算的表達式。在這個轉換過程中産生運算結果。我們下面用具體例子一個一個介紹這幾個函數的用法。還是用上期的例子：

prg是一段功能描述：在提示後讀取一個數字，重複一次，再讀取一個字串，把讀取的數字和字串用來做個運算。至于怎麼提示、如何讀取輸入、如何運算輸入内容，可能會有種種不同的方式，那要看interpreter具體是怎麼做的了。好了，現在我們看看如何用fold來運算prg：fold需要兩個入參數：r:a=>b,一個在運算終止return狀态時運作的函數，另一個是s:s[free[s,a]]=>b,這個函數在suspend狀态時運算入參數adt：

注意runquiz是個遞歸函數。在suspend question狀态下，運算f(readline)産生下一個運算。在這個函數裡我們賦予了提示、讀取正真的意義，它們都是通過io操作println,readline實作的。

運作結果：

結果正是我們期待的。但這個fold方法每調用一次隻運算一個adt，是以使用了遞歸算法連續約化suspend直到return。遞歸算法很容易造成堆棧溢出異常，不安全。下一個試試foldmap。foldmap使用了monad.bind連續通過高階類型轉換（natural transformation）将adt轉換成運作指令，并在轉換過程中實施運算：

上面的natural transformation是把quiz類型轉成id類型。id[a]=a，是以高階類型quiz可以被轉換成基本類型unit（println傳回unit）。這個例子同樣用io函數來實作ast功能。我們也可以用一個模拟的輸入輸出方式來測試ast功能，也就是用另一個interpreter來運算ast，我們可以用map[string,string]來模拟輸入輸出環境：

tester必須是個monad，是以我們必須提供隐式對象testermonad。看看運算結果：

foldrun通過入參數f:(b,s[free[s,a]])=>(b,free[s,a])支援狀态跟蹤,入參數b:b是狀态初始值。我們先實作這個f函數：

運作foldrun的結果如下：

下一個是runm了，它的入參數就是一個s[_]到m[_]的轉換函數：f: s[free[s,a]]=>m[free[s,a]]。我們先實作了這個f函數：

測試運作runm：

我們曾經介紹過有些f[_]是無法實作map函數的，是以無法成為functor，如以下adt：

從calc無法擷取b類型值，是以無法實作calc.map，因而calc無法成為functor。runfc就是專門為運算calc這樣的非functor高階類型值的。runfc需要一個freec[s,a]類型入參數:

可以得出runfc是專門為coyoneda設計的。coyoneda可以替代calc[a]，又是一個functor，是以可以用free産生calc類型的monad。我們先把interpreter實作了：

這個interpreter用的是stack内元素操作的運算方式。用runfc對ast運算的結果：

以上示範了針對任何抽象的monadic programm,我們如何通過各種interpreter的具體實作方式來确定程式功能的。