泛函程式設計（30）－泛函IO：Free Monad－Monad生産線

 在上節我們介紹了trampoline。它主要是為了解決堆棧溢出（stackoverflow）錯誤而設計的。trampoline類型是一種資料結構，它的設計思路是以heap換stack：對應傳統遞歸算法運作時在堆棧上寄存程式狀态，用trampoline進行遞歸算法時程式狀态是儲存在trampoline的資料結構裡的。資料結構是在heap上的，是以可以實作以heap換stack的效果。這種以資料結構代替函數調用來解決問題的方式又為泛函程式設計提供了更廣闊的發展空間。

    我們知道，任何涉及io的運算都會面臨堆棧溢出問題。這是因為io通常針對無法預計的資料量以及重複循環操作。是以io算法設計也會采用與trampoline一樣的資料結構。或者我們應該沿用trampoline資料結構和算法來設計io元件庫。如此思考那麼我們就必須對trampoline進行深度抽象了。free monad就是trampline的延伸。在介紹free monad之前我們先從一個現實的例子來展開讨論：

假設我們要編寫一個銀行轉賬的函數，我們可能先把這個函數的款式（function signature）推導出來：

首先我們在這裡采用了參數注入（parameter injection）方式：在transfer函數輸入參數中注入context object。這個context object裡包括了身份驗證、操作跟蹤、錯誤處理、資料存取等等。這算是傳統oop程式設計模式吧。對于一個泛函程式設計人員來講：通過這個context object 可以進行一系列的操作。包括io操作，也就是說可以進行一些含有副作用（side effect）的操作。那麼這個函數是無法實作函數組合（function composition）。transfer函數就不是一個泛函程式設計人員該使用的函數了。

也許我們應該從泛函程式設計角度來嘗試設計這個函數：用泛函程式設計提倡的不可蛻變（immutability）方式來設計，也就是向函數調用方傳回一些東西。

比如我們可以向函數調用方傳回一個描述操作的程式：一串指令（instruction）：

這個版本肯定是個泛函版本了。不過假如instruction類型包括了互動操作的話就不足夠了。我們先看看簡單的互動的資料類型：

如果我們按照上面的思路傳回一串指令的話：

這個程式prg是有缺陷的：無法實作互動。好像如果能把ask指令存放到一個臨時變量裡就可以達到目的了。那麼如果我們把這個prg改寫成下面這樣：

這不就是monad款式嗎？原來解決方法就是把互動類型trait interact[a]變成monad就行了。

不過要把interact變成monad就必須實作unit和flatmap兩個函數，檢查interact trait，明顯這是不可能的。

那我們把下面的努力都應該放在如何轉變成monad這方面了。既然我們在本篇命題裡提到free monad是monad生産線。那麼用free monad能不能把interact變成monad呢？

我們先看看這個free monad類型結構：

這個free結果跟trampoline簡直是太相似了。如果free是個monad，那麼我們應該必須實作它的flatmap函數：

我們可以用下面的lift函數來把interact[a]升格成free[f,a] ：

有了lift我們可以吧prg升格成monad：

這是因為implicit scope裡的類型轉換使interact升格為free，而free是個monad，是以我們可以使用for-comprehension。

好了，這個程式描述完成後應該如何運算呢？free monad包括了兩部分功能，互相之間無關聯，可以分開單獨考慮。這就是所謂的關注分離（separation of concern）。free monad的兩項功能分别是monad，和interpreter（解譯器）。我們用monad描述程式算法，用interpreter解譯程式形成針對特定運作環境的可運作代碼。

free monad的interpreter實作了算法和運算的分離考慮。interpreter程式運算是通過一個轉換函數實作的。這個函數把f[_]這樣一個算法解譯成g[_]這樣一個針對可運作環境的monad運作代碼。這種轉換就是自然轉換（natural transformation），它的函數款式如下：

很明顯，這個建構函數（constructor）把傳入的f[a]解譯成g[a]。

現在interpreter運作一段算法就是對算法f[_]中的表達式進行一對一的g[_]轉換。就像對list結構中元素進行處理的方式一樣，我們可以用折疊算法來實作f[_]結構中表達式的轉換：

我們看到，foldmap把free monad f[_]中的表達式與monad g狀态進行了對應。注意bind狀态是循環遞歸的。

現在我們可以試試最簡單的解譯：f,id轉換：

運算上面那段interact程式：由于id不産生任何效果，interact到id轉換即是直接運算interact表達式：

或者我們可以試試再複雜一點的解譯：

以上我們把運作interact中的互動資訊存入map[string,string]結構中。在這裡進行了interact到一個函數map=>(list,a）的轉換。

在上一節我們讨論了trampoline。主要目的是解決泛函算法中不可避免的堆棧溢出問題。如果我們用free monad來解決io問題的話，堆棧溢出問題也是無法避免的。我們應該考慮在free monad裡使用trampoline類型。這樣我們才可以放心地用free monad來産生任何類型的monad并在運算中以heap換stack解決堆棧溢出問題。