單子 (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

  1. roy_hu
    Posted 十一月 20, 2009 at 1:29 下午 | Permalink

    Monad transformer真的解决问题了吗?我始终觉得只是一个临时性的解法。正好这里最近有一个讨论:http://scienceblogs.com/goodmath/2009/11/philosophizing_about_programmi.php

    • Posted 十一月 20, 2009 at 10:01 下午 | Permalink

      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 您還知道其他的方式嗎?

      • roy_hu
        Posted 十一月 21, 2009 at 4:10 上午 | Permalink

        我的感觉与MarkCC及一些评论者相同,就是Monad Transformers不是compositional的。为了组合不同的monads,需要注意组合的顺序,然后为了使用内层的操作,还要通过一级一级的lift来达到目的。而在mtl的实现中,为了让使用者不需要插入lift,库的实现者只好为N种monad transformer定义了O(N*N)个instance。有评论提到,可以从category theory中找到灵感,不过我对category theory就是一窍不通了。如果您能在blog中普及一下category theory,就真是太好了。

      • Posted 十二月 6, 2011 at 7:35 上午 | Permalink

        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 上什麼東西 …

  2. Posted 十一月 23, 2009 at 12:50 上午 | Permalink

    也許是一個笨問題… ReaderMaybe 是不是要自己寫?
    像是 instance Monad (ReaderMaybe a) where
    instance MonadReader a (ReaderMaybe a) where
    也因此 monad transformer 可以幫你做這件事?

    • Posted 十一月 24, 2009 at 11:23 下午 | Permalink

      是的,如果 ReaderMaybe 是自己定的型別,這些 instance 宣告(和 method 定義)也都得自己寫了。寫錯的責任也自己擔。 :) 所以才用 monad transformer.

  3. snow
    Posted 六月 6, 2010 at 11:14 上午 | Permalink

    不好意思 我想問一下haskell的一些問題 haskell本身的log好像是以2.7…….為底 要怎麼讓他以2為底??另外haskell可以自行產生變數嗎??

    • Posted 六月 23, 2010 at 9:39 下午 | Permalink

      抱歉前陣子在忙,沒注意到多了新留言。現在回可能晚了,anyway…

      Haskell Standard Prelude 的 log 函數是以 e 為底。如果要用其他底可用 logbase. 所謂產生變數所指為何呢?為何會需要這項功能呢?

  4. Fergon
    Posted 十月 26, 2011 at 11:20 下午 | Permalink

    太精采了,我都看的入迷了,怎么没了呢?

One Trackback

  1. [...] This post was mentioned on Twitter by 刘鑫, Alex Dong and haohaolee, zhasm. zhasm said: RT @marchliu: http://is.gd/hyLk6 http://is.gd/hyLlD 两篇非常好的haskell monad 教程,至少我学了这么久,读了这两篇才算会用。当然,这毕竟是haskell,文章还要涉及解释器和抽象代数…… [...]

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>