泛函程式設計（31）－泛函IO：Free Monad－Running free

 在上節我們介紹了free monad的基本情況。可以說free monad又是一個以資料結構替換程式堆棧的執行個體。實際上free monad的功能絕對不止如此，以heap換stack必須成為free monad的運算模式，這樣我們才可以放心的使用free monad所産生的monadic程式設計語言了。前面我們介紹了trampoline的運算模式可以有效解決堆棧溢出問題，而上節的free monad介紹裡還沒有把free monad與trampoline運算模式挂上鈎。我們先考慮一下如何在free monad資料類型裡引入trampoline運算模式。

我們先對比一下tranpoline和free這兩個資料類型的基本結構：

這兩個資料類型的設計目的都是為了能逐漸運作算法：按照算法運算的狀态确定下一步該如何運作。這個f[free[f,a]]就是一個循環遞歸結構，裡面儲存了運算目前狀态和下一步運算。

我們曾說如果一個資料類型能有個functor執行個體，那麼我們就可以用它來産生一個free monad。這個要求從上面free[f,a]類型裡的map,flatmap可以了解：我們用了implicit f: functor[f]參數，因為必須有個functor執行個體f才能實作map和flatmap。

為了實作free monad在運作中采用trampoline運作機制，我們可以像trampoline資料類型一樣來實作resume,這個确定每一步運算方式的函數：

free類型的resume函數與trampoline的基本一緻，隻有傳回類型和增加了參數implicit f: functor［f]，因為free[f,a]的f必須是個functor：用functor f可以産生free[f,a]。

我們用個實際例子來體驗一下用functor産生free：

我們可以用上一節的interact類型：

這個類型太簡單了，太單純了。我還沒想到如何得出它的functor執行個體。好像沒辦法實作那個map函數。那麼如果修改一下這個interact類型：

這個新類型的兩個狀态ask,tell都增加了個參數next，代表下一步操作。實際上我們是用map來運作next的。這樣我們就可以得出interact的functor執行個體。

從上面的functor執行個體中我們可以看到如何通過map的f(n)來運作下一步驟next。

接下來我們要把interact類型升格到free類型：

看，把interact升格後就可以使用for-comprehension了。

還是那句話：用一個有functor執行個體的類型就可以産生一個free monad。然後我們可以用這個産生的monad來在for-comprehension裡面編寫一個算法。

解譯運算(interpret)是free monad的interpreter功能。我們說過要把trampoline運作機制引入free monad運算：

foldmap通過調用resume引入了trampoline運作機制。

前面介紹的free monad相對都比較簡單。實際上free monad的suspend處理可以是很複雜的，包括傳回結果及接受輸入等任何組合。下面我們再看一個較複雜的例子：我們可以把state視為一種簡單的狀态轉變程式設計語言，包括讀取及設定狀态兩種操作指令：

我們先看看嫩不能擷取statef的functor執行個體：

既然有了functor執行個體，那麼我們可以用來産生free monad:

free[f,a]裡的functor f隻接受一個類型參數。statef[s,a]有兩個類型參數，我們必須用type lambda來解決類型參數比對問題。

現在我們已經得到了一個freestate monad。下面接着實作freestate的基礎元件函數：

注意類型比對。我們可以寫個函數來運算這個freestate：

這個運算方式還是調用了resume函數。注意：get(f) 傳回 statef[s,a]，statef是個functor, f[free[f,a]]那麼a就是free[f,a]

還是試試運算那個zipindex函數：

沒錯，這段程式不但維護了一個狀态而且使用了trampoline運算模式，可以避免stackoverflow問題。

下面我們再用一個例子來示範free monad的monadic program和interpreter各自的用途：

我們用一個stack操作的例子。對stack中元素的操作包括：push,add,sub,mul,end。這幾項操作也可被視作一種stack程式設計語言中的各項操作指令：

我們先推導它的functor執行個體：

 這裡的next看起來是多餘的，但它代表的是下一步運算。有了它才可能得到functor執行個體，即使目前每一個操作都是完整獨立步驟。

有了functor執行個體我們就可以實作stackops的monadic programming:

我們用lisftstackops函數把stackops升格到free[stackops,a]後就可以用for-comprehension進行monadic programming了。如果不習慣add(())這樣的表達式可以這樣：

這樣從文字意思上描述就清楚多了。但是，這個stkprg到底是幹什麼的？如果不從文字意義上解釋我們根本不知道這段程式幹了些什麼，怎麼幹的。換句直白的話就是：沒有意義。這正是free monad功能精妙之處：我們用monad for-comprehension來編寫一段monadic program，然後在interpreter中賦予它具體意義：用interpreter來确定程式具體的意義。

那我們就進入interpreter來運算這段程式吧。

先申明stack類型： type stack = list[int]

在上面我們有個interpreter, foldmap:

但是運作stkprg必須傳入stack起始值，foldmap無法滿足。那麼我們再寫另一個runner吧：

foldrun也是個折疊算法：給予一個起始值及一個對資料結構内部元素的處理函數然後可以開始運作。這個函數剛好符合我們的需要。下一步就是給予stkprg意義：确定push,add...這些指令具體到底幹什麼：

啊。。。在這裡我們才能具體了解每一句stackops指令的意義。這就是free monad interpreter的作用了。我們試着運算這個stkprg：

跟蹤一下操作步驟，最終結果是正确的。

我們再試一下用natural transformation原理的foldmap函數。我們可以用state的runs來傳入stack初始值：

這個stackstate類型就是一個state類型。我們能夠推導它的monad執行個體，那我們就可以調用foldmap了。我們先編寫interpreter功能：

通過natural transformation把stackops轉成stackstate狀态維護。stackops具體意義也在這裡才能得到體驗。我們用foldmap運算stkprg：

我們得到了同樣的運算結果。

希望通過這些例子能把free monad的用途、用法、原了解釋清楚了。