為了進入下一個例子,我們為算式型別加上變數:
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 3
,lookup 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)
. 等號右手邊是一個函數, 拿了一個環境 env
。r
需要一個環境才能算出一個 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
我們還得加上處理 Var
和 Let
兩個情況的條款。遇到 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
. 函數 eval
的 Let
條款便可寫成
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)」為止。以後我們希望能談到。
下次我們會繼續介紹另一個有用的單子 — 狀態單子。
附註
- 其實既然環境是一個映射,我們用的又是函數語言,更方便的做法是用函數表示環境:
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)
Monad transformer真的解决问题了吗?我始终觉得只是一个临时性的解法。正好这里最近有一个讨论:http://scienceblogs.com/goodmath/2009/11/philosophizing_about_programmi.php
Hi,
Good Math, Bad Math 是蠻好看的 blog. 謝謝提供消息。
那篇文章也很值得一看。裡頭說到的幾個點我都同意:
1. 函數編程的最大優點是便於做分析推理。我其實想在本 blog 上的函數編程簡介慢慢把這點帶出來,但照這個進度不知道要何時才會寫得到了。Mark Chu-Carroll 是個有實務經驗的工程師,從他口裡說出這點更是難得。
2. 而確實,lazy evaluation 會有一些問題。我對 lazy evaluation 的疑慮倒是基於另外一個理由:要談它需要一個不同的數學模型。Mark CC 說的問題也都成立。
3. 最後,monad 使得程式的分析比較難。說真的,我並沒有看過很多分析推導含有 monad 的程式、或著證明含 monad 的程式的性質的有趣例子。如果有的話我很想看看。
MarkCC 最後兩段提出的問題似乎是:A. 很多種 monad 不知道怎麼結合 B. 結合之後更不知道怎麼分析。目前對 A. 的解答似乎就是 monad transformer. 我蠻好奇有什麼後續論述。但他寫到這裡裡就暫停了。下面的回應中也只有一兩篇有談到 A 的層次(其他很多回應談到使用 monad 的困難,我覺得其實是在抱怨他們不懂 monad)。只能期待下集了。
我的印象是,做函數語言的人之中有些做推理分析,有些比較重實務。Monad transformer 對後者組織大程式時比較有用 — 我是最近看了一些大程式才體驗到這點的。而前者對 monad 比較少碰觸,更別說 monad transfomer. 前陣子與人聊起,還有人很驚訝地說「原來真有人在用 monad transformer 呀。」所以我覺得 monad transfomer 的問題是
不知道您所說的「monad transformer 真的解決問題了嗎?」是指哪類問題呢?除了 monad transformer 您還知道其他的方式嗎?
我的感觉与MarkCC及一些评论者相同,就是Monad Transformers不是compositional的。为了组合不同的monads,需要注意组合的顺序,然后为了使用内层的操作,还要通过一级一级的lift来达到目的。而在mtl的实现中,为了让使用者不需要插入lift,库的实现者只好为N种monad transformer定义了O(N*N)个instance。有评论提到,可以从category theory中找到灵感,不过我对category theory就是一窍不通了。如果您能在blog中普及一下category theory,就真是太好了。
Monad 不是 compositional 的問題,從代數的角度去看可能比較明顯,所有的 monad 都一一對應一個代數理論(algegraic theory),如果是 finitary monad 的話,則對應 finitary algebraic theory 也就是所有的代數操作都只拿有限個元件,例如 Maybe monad 有兩個 operator 這樣,Just 只拿一個元素,Nothing 什麼都沒拿。大部分在 Haskell 的 monad 都是 finitary 的,但是 continuation monad 例外。
兩個 finitary monad 的合成(其實只要 operator 是 bounded 就好,但在 Haskell 上談有限多個以外的參數好像沒意義?),則對應兩個 algebraic theories 的合成,theory 的合成目前已之有幾種方式,一種是直接加在一起,兩邊的 operator 沒有互相影響,第二種則說兩個 theory 的 operator 互相交換(commutes),第三則說是一個 theory 中的 operator 分配到另一個理論的 operator 也就是 a x (b * c) = (a * b) x (a * c) 這樣的。第一種是對任何理論都可以這樣做,後面兩種則有條件的。
而一般給定 monad T, S 若 TS 仍是一個 monad 的話,對應著是 T 的理論分配到 S 上;相對地,ST 則是 S 理論分配到 T 理論上,當然跟 ST 會不一樣。這些在 M. Hyland 02 年的論文中有提到,雖然這篇很數學。J. Power 這些人最幾年很愛談這個東西,我也是最近才發現這套東西的威力,不過似乎還沒有被實作出來。
如果要做 monad 上的 equational reasoning ,我想還是得把 monad 的操作跟滿足的等是淬取出來,這部分 J. Gibbons 跟 R. Hinze 今年(2011)的論文似乎就是在做這個。
monad transformer 我則是還不知道它對應 category theory 上什麼東西 …
也許是一個笨問題…
ReaderMaybe
是不是要自己寫?像是
instance Monad (ReaderMaybe a) where
和
instance MonadReader a (ReaderMaybe a) where
也因此 monad transformer 可以幫你做這件事?
是的,如果
ReaderMaybe
是自己定的型別,這些 instance 宣告(和 method 定義)也都得自己寫了。寫錯的責任也自己擔。 🙂 所以才用 monad transformer.不好意思 我想問一下haskell的一些問題 haskell本身的log好像是以2.7…….為底 要怎麼讓他以2為底??另外haskell可以自行產生變數嗎??
抱歉前陣子在忙,沒注意到多了新留言。現在回可能晚了,anyway…
Haskell Standard Prelude 的
log
函數是以 e 為底。如果要用其他底可用logbase
. 所謂產生變數所指為何呢?為何會需要這項功能呢?Pingback: Tweets that mention 單子 (monad) 入門(二)讀取單子 -- Topsy.com
太精采了,我都看的入迷了,怎么没了呢?