# 單子 (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))``

### 變數與環境

``type Env = [(Name, Int)]``

``lookup :: Env -> Maybe Int``

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

``eval :: Expr -> Env -> Int``

``````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``

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

### 算式的語意是函數

``````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)``````

### 讀取單子

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

``return x = \env -> x``

`>>=` 的定義是：

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

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

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

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

### Ask 與 Local

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

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

``````ask :: Reader Env
ask env = env``````

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

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

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

### 討論

``type Reader e a = e -> a ``

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

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

``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
``````

### 附註

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)

``````

### 10 thoughts on “單子 (monad) 入門（二）讀取單子”

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

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

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

2. 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. 也許是一個笨問題… `ReaderMaybe` 是不是要自己寫？
像是 `instance Monad (ReaderMaybe a) where`
`instance MonadReader a (ReaderMaybe a) where`
也因此 monad transformer 可以幫你做這件事？

1. 是的，如果 `ReaderMaybe` 是自己定的型別，這些 instance 宣告（和 method 定義）也都得自己寫了。寫錯的責任也自己擔。 🙂 所以才用 monad transformer.

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

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

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