單子 (monad) 入門(二)讀取單子

為了進入下一個例子,我們為算式型別加上變數:

data Expr = Num Int | Neg Expr | Add Expr Expr
          | Var Name | Let Var Expr Expr

Name 是變數名稱。我們可以用 type Name = String 或著其他型別,只要能夠比較兩個變數是否相等就可以了。Var v 是出現在算式中的變數,Let 則用來宣告新的區域變數。例如:

Let "x" (Num 3) (Add (Var "x") (Num 4))

宣告變數 x 的值為 3, 因此整個算式的值是 3 + 4 = 7.

變數與環境

有了變數後,我們不能只問「Add (Var "x") (Var "y") 的值是什麼」了。有自由變數的算式得放在一個「環境」下才能談它的值。「環境」告訴我們每個變數的值,用行話說,環境是從變數到值的映射,我們可以用一個串列表示:1

type Env = [(Name, Int)]

例如 Add (Var "x") (Num 4) 在環境 [("x", 3), ("y", 6)] 下的值是 7. 我們也假設有一個「查表」函數:

lookup :: Env -> Maybe Int

例如,當 env = [("x", 3), ("y", 6)]lookup env "x" Just 3lookup env "z" 則是 Nothing.

有點得注意:雖然我們照習慣把 x 稱為區域「變數」 (local variable),x 的值一但給定了就不會改變。例如這個式子的值

Let "x" (Num 3)
    (Add (Add "x" (Let "x" (Num 4) (Var "x")))
         (Neg (Var "x")))

應該是 3 + 4 + (-3) — 內層宣告的 x 僅是暫時遮蓋到外面的 x。這和我們之後會提到的、一般指令語言中的設值運算 (assignment) 是不同的。

這麼多鋪陳之後,我們終於可以看看新的 eval 函數要怎麼寫了。我們待會兒會介紹讀取單子 (reader monad), 但顧及有些讀者可能還不習慣這樣的運算,我們先把單子放一邊,看看怎麼用最直接的方式寫 eval.

既然算式要在環境之下才有值,eval 得把環境也納為參數之一:

eval :: Expr -> Env -> Int

函數 eval 拿一個算式和一個環境,計算該算式的值。新的 eval 中,最初的三個條款基本上是一樣的,只是多了一個參數 env 得往下傳:

eval (Num n) env = n
eval (Neg e) env = - (eval e env)
eval (Add e1 e2) env = eval e1 env + eval e2 env

碰到變數時,我們到環境中查變數的值:

eval (Var x) env = case lookup env x of Just v -> v

這裡的 case 算式只處理了 Just 的情形。如果 lookup 傳回的是 Nothing,也就是變數 x 並不在環境 env 中,該怎麼辦呢? 我們等下再談。最後,碰到 Let x e1 e2 時,我們先把 e1 的值在 env 這個環境之下算出,然後算 e2:

eval (Let x e1 e2) env = 
  let v = eval e1 env
  in eval e2 ((x, v) : env)

但計算 e2 時必須使用新的環境 (x, v) : env,意謂 e2 可以用到 x, 而 x 的值是 v.

算式的語意是函數

回到單子。在單子入門(一)中,單子版的 eval 是這樣寫的:

eval :: Monad m => Expr -> m Int
eval (Num n) = return n
eval (Neg e) = eval e >>= (\v -> return (-v))
eval (Add e1 e2) = eval e1 >>= \v1 ->
                   eval e2 >>= \v2 ->
                   return (v1 + v2)

我們也提及了,單子讓我們模組化地加入新功能。我們要怎麼以這個程式為基底,靠著選用不同的單子,把「處理環境的功能」加上去呢?

函數 eval 沒有副作用時的型別是 Expr -> Int — 一個算式的「意思」就是一個整數。加上變數、考慮環境的 eval 的型別變成了 Expr -> Env -> Int. 一種讀解方式是:eval 拿一個算式,傳回一個函數。也就是說,一個算式的「意思」(用行話說,是算式的語意)成了「拿一個環境,傳回一個整數」的函數。的確,既然算式算成的那個整數必須由環境決定,算式其實不能看作一個數值,而應該是從環境到整數的函數才對。eval (Add (Var "x") (Var "y")) 是一個函數,如果給它 [("x", 3), ("y", 2)], 我們得到 5. 如果給 [("x",4), ("y", -3)], 我們得到 1.

如果我們把這個「從環境到整數的函數」叫做 Reader a, 也就是說定義 type Reader a = Env -> a,函數 eval 的型別成了 Expr -> Reader a. 我們能不能讓 Reader a 成為一個單子呢,也就是說,定義符合單子定律,並也符合我們需求的 return>>= 兩個運算元呢?

讀取單子

回顧一下 return>>= 的型別:

return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b

此處 m a = Reader a = Env -> a. 讀取單子的 return 定義是

return x = \env -> x

意即 return x 不產生副作用、僅傳回純數值 x. 環境 env 並沒有用到。回顧一下兩個版本的 eval 如何處理 Num:

原始版: eval (Num n) env = n
單子版: eval (Num n) = return n

確實後者代入 return 的定義後就成了前者。

>>= 的定義是:

r >>= f = \env -> f (r env) env

此處 r 的型別是 Env -> a, f 的型別是 a -> (Env -> b). 等號右手邊是一個函數, 拿了一個環境 envr 需要一個環境才能算出一個 a,因此我們把 env 餵給它。算出的結果送給 f. 但 f (r env) 又是一個讀取單子,仍需要一個環境才能算出 b. 因此我們把同一個環境 env 又餵給它一次。

環境 env 是被兩個運算共用的。這可解釋為何我們把 eval 的 Add 條款

eval (Add e1 e2) = eval e1 >>= (\v1 ->
                   eval e2 >>= (\v2 ->
                   return (v1 + v2)))

展開後,會得到 eval e1 env + eval e2 env. 我們仔細看看讀取單子在此如何運作:整個等號右手邊是個拿一個環境的函數。根據 >>= 的定義,環境會丟給 eval e1,算出的值交給 >>= 右邊的函數 (\v1 -> ...)。因此右手邊成了:

\env -> (eval e2 >>= (\v2 ->
         return (eval e1 env + v2)) env

內層的 eval e2 >>= ... 也用同樣的原則化簡:它也是期待一個環境的函數,剛好把外面的 env 接受。化簡後得到

\env -> return (eval e1 env + eval e2 env) env

最後把 return 展開就成了 eval e1 env + eval e2 env.

Ask 與 Local

我們還得加上處理 VarLet 兩個情況的條款。遇到 Var x 時我們得到環境中查詢的值。原有的寫法是:

eval (Var x) env = case lookup env x of Just v -> v

此處這麼寫也是可以的。但標準的讀取單子定義中提供了一個函數 ask, 方便我們把環境給取出來用:

eval (Var x) = ask >>= \env ->
               case lookup env of Just v -> v

函數 ask 可定義為:

ask :: Reader Env
ask env = env

也就是說 ask 拿到一個環境後直接傳回該環境。

而處理 Let x e1 e2 的條款需在擴充過的環境中求 e2 的值。。為了這類的需求,標準讀取單子也提供了一個方法:

local :: (Env -> Env) -> Reader a -> Reader a 
local f r = \env -> r (f env)

其中 f 是產生新環境用的函數。local f r拿到一個環境 env,但在環境 f env 中執行 r. 函數 evalLet 條款便可寫成

eval (Let x e1 e2) = 
    eval e1 >>= \v1 ->
    local (\env -> (x,v1) : env) (eval e1)

意義很清楚:先算出 e1 的值,稱作 v1, 而 e2 的值須在區域環境 (x,v1) : env 中計算。其中 \env -> (x,v1) : env 還可稍微簡寫一下:

eval (Let x e1 e2) = 
    eval e1 >>= \v1 ->
    local ((x,v1) : ) (eval e1) 

討論

結束本文前,我們再提幾件事情。

首先,上述討論中為了說明方便,假設環境的型別固定為 Env. 我們當然可以把這部份也抽象掉:

type Reader e a = e -> a 

return, >>=, ask, local 的型別也隨之改變,但其定義原就沒有預設環境的型別,仍可沿用。

其次,如同單子入門(一)中的單位單子一樣,如果要使用 type class, Haskell 要求我們必須把 Reader 定義成一個新資料型別(type 定義的僅是別名)。目前標準函示庫中的定義請見附錄。

最後,我們稍早曾遇到這個問題:如果給這樣的式子

eval (Var "x") [("y",0)]

變數 "x" 並不在環境中,lookup 將傳回 Nothing,這時該怎麼辦?

我們可以再擴充 Reader 的型別,讓 eval 也可以傳回一個 Maybe 結果:

type ReaderMaybe a = Env -> Maybe a

return>>= 也得隨之擴充:

return a = \env -> Just a
rm >>= f = \env -> case rm env of
                    Just v -> f v env
                    Nothing -> Nothing

這個 ReaderMaybe 型別綜合了讀取單子與 Maybe 單子的功能,其 return>>= 定義也像是兩個單子定義的混合。它也是一個 MonadPlus, eval 在碰到上述情況可以傳回 mzero. 這時 mzero 的定義應該是 \env -> Nothing.

但這並不是令人相當滿意的做法。ReaderMaybe 比起 Reader 又更複雜了一點。日後我們也許會想要有更多功能,例如狀態、輸出入等。ReaderMaybe 已經夠抽象難解了,我們並不希望設計、維護越來越龐大的單子。

既然 Maybe 單子讓一個程式加上「例外」的副作用,讀取單子讓一個程式加上可存取環境的功能,我們能否把這兩項功能分別模組化地加入呢?

也就是說,給了兩個單子 M1 和 M2, 能否把他們的功能加在一起,產生另一個新單子呢?

這曾經是困擾函數編程學者的難題,直到出現了「單子轉換器 (monad transformer)」為止。以後我們希望能談到。

下次我們會繼續介紹另一個有用的單子 — 狀態單子。

附註

  1. 其實既然環境是一個映射,我們用的又是函數語言,更方便的做法是用函數表示環境:
    type Env = Name -> Maybe Int

    為了避免不習慣高次函數的初學者搞到困惑,本文還是用比較「摸得到」的串列表示 Env.

附錄:以 newtype 定義的讀取單子

newtype Reader e a = Reader { runReader :: (e -> a) }
 
instance Monad (Reader e) where 
    return a         = Reader $ \e -> a 
    (Reader r) >>= f = Reader $ \e -> f (r e) e 

class MonadReader e m | m -> e where 
    ask   :: m e
    local :: (e -> e) -> m a -> m a 
 
instance MonadReader (Reader e) where 
    ask       = Reader id 
    local f c = Reader $ \e -> runReader c (f e) 

This entry was posted in 函數編程簡介, 計算算計 and tagged , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

9 Comments