和之前一樣，選了Brainfuck Interpreter這個題目開刀。這也是我第一次寫Haskell application，coding手法上還很生疏。以下的例子分成三個版本。第一個版本是簡單的實作，第二個版本加入了State Monad。第三個版本是最完整的實作，加入了Monad Transformer, Unit Test並切分模組。
編程環境：GHC 6.10.3
首先，我試著完全不使用Monad，實作了第一個版本的Brainfuck Interpreter (實作一源碼)。先來看看資料結構：
data BFData = BFData {
curr :: Word8,
left :: [Word8],
right :: [Word8]
} deriving(Show)
data BFState = BFState {
codeLeft :: [Char],
codeRight :: [Char],
bfData :: BFData
} deriving(Show)
BFData表示Brainfuck運行時的Memory，Word8是Haskell中的8-bit unsigned integer。Brainfuck在運行時，記憶體像是被單一指標指著的陣列，我使用兩個list及一個數值表示這樣的資料結構：curr表示目前的值，right表示指標位置右側的值，left表示指標位置左側的值。當指標向右移動的時候，將curr的值塞到left的前端，將right的head塞到curr中。眼尖的人或可發現：left中的值排放順序是相反的。這樣可以在常數時間內做完指標移動的動作。
BFState為整個Brainfuck interpreter的狀態。codeLeft和codeRight使用了和data相似的資料表示方式：未執行及已執行的code。BFState裡也包括了BFData的資料結構。
再來是函數的定義，版本一中盡量都是以pure function去操作資料。我們先略去函式的定義，觀察一些函式的型別
fwd :: BFData -> BFData -- 資料指標前進
back :: BFData -> BFData -- 資料指標後退
modifyValue :: Word8 -> BFData -> BFData -- 修改資料指標
output :: BFData -> Char -- 讀取資料指標
blockBack :: BFState -> BFState -- 遇到右括號 (branch on nonZero) 時回退
可以發現，底層大部份的操作都寫成pure function。將一個資料轉為令一個資料，no side-effect, no implicit state。
在這個版本中我刻意的不做兩件事：不使用Monad記住狀態，不使用function呼叫的轉移來表示程式進行的狀態轉移(Erlang idiom)。寫一寫我才理解到為什麼Monad是重要的。Haskell是一個Single-assignment，大部份變數immutable的語言 (如同Erlang) 。在這樣的語言中，要修改一個複雜的狀態常常是很麻煩的，會出現x' = f(x); x'' = g(x'); x''' = h(x'')之類的敘述。另外就是錯誤狀態的傳遞 (ex. Maybe Monad)。這些東西通常使用Imperative Language更容易描述。
* Update: 這段話我寫的不夠好。剛剛回去看Josh Ko部落格，他做了更精確的解釋。引述一下他的說法：「把全部的 states 都寫出來，就不會為了顧及 implicit states 而在推理轉換時絆手絆腳；但當 state 規模變大時，處理起來就不那麼順手了，此時 imperative programs 的專門語法反而比較方便。」
在下一個例子我們可以看到如何使用State Monad來打造Imperative的環境，但再更高階的地方仍保有Pure functional的性質。
接下來，我實作了第二個版本，這個版本使用了State Monad (實作二源碼) 。
節錄一部份的Code來討論好了：
我先簡化了一下資料結構，將code及data都放在BFState的資料結構中。為了實作方便，這個版本不吃standard input，而把output丟到一個字串當中(bfOutput)。這個偷吃步可以完全隔離IO，並簡單地直接使用State Monad。
再來，觀查fwdCode, backCode, fwdData, backData四個函式，其型別都是State BFState ()。State其實是Control.Monad.State提供的Type Constructor。State s a即是一個內部狀態為s，回傳值為a的State Monad。這些東西我就不細述了，有興趣的話請去參考文件吧。
stepBF函式負責將直譯器推進一個指令。看看
c <- currCode
d <- getData
fwdCode是不是回到了我們熟悉的Imperative programming的寫法？fwdCode看似造成了side effect (雖然這個side effect是被封裝在monad內的) 。
進ghci觀查一下型别，我們可以發現一下有趣的事。
*Main> :t bfOutput . snd . execBF
bfOutput . snd . execBF :: [Char] -> [Char]
我們可以將這些函式串起來，將State Monad的型別消掉，得到一個顯然的pure function：給定一個brainfuck code的字串，得到一個輸出的字串。而Pure function對測試顯然是有利的，我們可以保證每次的運行結果都一樣，不會受外在環境影響。
這個版本的缺點是：沒有辦法綁定標準IO。如果可能，我們會希望BFState的狀態機與輸入輸出可以解除耦合，透過形別系統可以同時綁定在標準IO/模擬的IO上。BFState綁定在標準IO時當然是Impure的：程式運行會受外部輸入影響。當透過模擬的IO時，我們可以將整個BFState的運行化為Pure Function。下個範例會顯示如何做到這一點。
(註：前兩個版本的Brainfuck interpreter algorithm其實是錯的：左括號當值為零的時候忘了向右branch，只是跑hello, world的例子剛好會對，我也懶得修了。另外輸入的指令其實沒有實作)
接下來應該要講正題了，第三個範例：
- Haskell Brainfuck Interpreter
- Monad Transformer：以Control.Monad.State.StateT為例
- 使用StateT切割IO，同時以IO及pure function形式執行brainfuck interpreter
- 在Unit Test中以pure function運行brainfuck interpreter
先放source code：有稍微切一下module，應該沒有前兩個範例那麼亂
source code available at Github
