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

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

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

return a         = Reader \$ \e -> a
(Reader r) >>= f = Reader \$ \e -> f (r e) e

local :: (e -> e) -> m a -> m a

local f c = Reader \$ \e -> runReader c (f e)

``````

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

• 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 說的問題也都成立。

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

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

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

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

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

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

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

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

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

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

太精采了，我都看的入迷了，怎么没了呢？