8 單子與副作用

8.4 狀態單子

沿用第 8.1 節之中的型別：

data Expr = Num Int | Neg Expr | Add Expr Expr | Div Expr Expr

這次我們暫且忽略分母為零的可能，而考慮另一個應用：我們想知道計算過程中做了多少次除法。 指令式語言中，一個常見的作法是用一個可變變數來計數。 在函數語言中我們怎麼模擬這種行為呢？

在指令式語言中，可變變數的值常用來表示整個系統目前的「狀態(state)」：諸如已處理過的資料個數、處理中的元素號碼、棋盤上每個棋子的位置... 等等。因此我們把「存取可變變數」的能力稱作狀態(state)副作用。

經過前幾節的熟悉，我們現在應可以更抽象地、由上而下地想像單子了：對於一個我們需要的副作用，先假設其單子存在，考慮它該有哪些運算子、這些運算子該滿足什麼性質、用它們如何寫程式。 然後才考慮這個單子的實作。對於狀態這個副作用，我們該怎麼設計其運算子呢？

在命令式語言中，x := x + 1 這行指令把可變變數 x 的值遞增。這一行看似單純的指令其實包含幾項特性：

  • 變數是有名字的；

  • 當變數名字出現在 := 的右手邊，表示讀取變數的值；

  • 當變數名字出現在 := 的左手邊，表示將值寫入該變數。

函數語言中討論狀態副作用時偏好用單純些、使用時比較繁瑣、但比較好討論性質的設計：變數沒有名字，並且把「讀取」與「寫入」兩個動作分為單獨的運算子。

具體說來，令 State s a 表示一個結果型別為 a, 但在執行時可讀寫一個型別為 s 的可變變數的計算。我們要求 State s 是一個單子 --- 意謂存在著滿足單子律的 return :: a -> State s a 和 (>>=) :: State s a -> (a -> State s b) -> State s b。 一個型別為 State s a 的運算中隱藏的可變變數沒有名字，只能用下述兩個運算子存取：

get  :: State s s  
put  :: s -> State s ()

運算子 get 和第 8.3 節中的 ask 類似，讀出該可變變數的值；put e 則把 e 的值寫到可變變數中，並傳回 ()。 例如，當 s = Int, 我們可以定義如下的操作 inc，把可變變數加一：

inc :: State Int ()
inc = get >>= \v -> put (1+v)

關於 put 有幾件事情可提醒。首先，當我們呼叫 put e, 其中的 e 已經是一個型別為 s 的純數值，不含副作用。 例如在 inc 之中，我們必須先將變數的值 get 出來（這是一個有副作用的動作），才能計算新的值並寫回去。 這讓程式寫起來很繁瑣，但也使得推論程式的性質容易許多。 其次，關於 put e 的型別 State s (). 回想：() 是一個只有一個值的型別，該值在 Haskell 中也寫作 (). 給定 e :: s 後，put e :: State s () 是一個會存取型別為 s 的可變變數，並傳回 () 的計算。在此，「傳回 ()」可理解為傳回一個不帶資訊的值，僅表達「我做完了」。

這個傳回值既然沒有資訊，通常不會被用上。因此當 put 不是函數的最後一個動作時，程式常有如下的模樣：

   ... put e >>= \_ -> ...

由於「執行一段程式，但只需要它的副作用，不需要它的結果」這件事在本章還會常常發生，我們另外訂一個運算元：

(>>) :: m a -> m b -> m b
p >> q = p >>= \_ -> q

如此一來 put e >>= \_ -> q 可以簡寫成 put e >> q. （注意： p >> q 並不要求 p 的傳回值型別為 ().）

回到 get 與 put。 如果它們的某個實作確實表達了我們前面口述的意圖，該實作應該會滿足以下的規則：

  • get-put:   get >>= put = return ()

  • put-get:   put e >> get = put e >> return e

  • put-put:   put e0 >> put e1 = put e1

以及一個和第 8.3 節中的 ask 類似的性質：

get >>= \v0 -> get v1 >>= \v1 -> f v0 v1  =  get >>= \v -> f v v     (8.4 )

其中，get-put 意謂：將可變變數的值讀出後立刻寫入相當於什麼都不做。 規則 put-get 意謂：剛做完 put e 之後立刻讀取可變變數的值，必定得到 e. 規則 put-put 意謂：連做兩個 put 之後，只有第二個 put 寫入的值會被留下。 規則 get-get 則意謂：連做兩次 get 所得到的值必定相同，可以只 get 一次就好。

如前所述，用 get 與 put 可定義出 inc, 而我們只需在 eval 遇到 Div 的情況中呼叫 inc，就可記錄做了多少次除法了：

eval (Div e0 e1) =  eval e1  >>= \v1 ->
                    eval e0  >>= \v0 ->
                    inc >>
                    return (v0 `div` v1)

函數 eval 的其他條款可完全不變，只需把所用單子的型別改成 State Int. 由於單子捕捉了含副作用的程式的共通模式，我們只需選用不同的副作用運算子，就可在不更動大部分程式的情況下使用我們需要的副作用。

8.4.1 河內塔問題

本節以河內塔問題為例子，示範狀態單子的推論。

hanoi 0        = return ()
hanoi (Suc n)  = hanoi n >> inc >> hanoi n

hanoi n = put (2^n -1).