What have you found for these years?

2009-11-01

Reader Monad (2)

updated 2009-11-07 23:13:
加個「筆記」標籤,因為 comments 很重要 @@

*

真糟,看半天試半天還是不懂 ask/asks 怎麼取到 Env 的??

data Tem = Txt String | Var Tem deriving Show
type Env = [(String, String)]

lookupVar :: String -> Env -> Maybe String
lookupVar = lookup

resolve :: Tem -> Reader Env String
resolve (Txt str) = return str

重點來了:

resolve (Var tem) = do
name <- resolve tem
val <- asks (lookupVar name)
return (maybe "" id val)
這三者是等價的,但是 ask/asks 怎麼把 Env 變出來的啊??
resolve (Var tem) = resolve tem >>= \name -> asks (lookupVar name)
>>= \val -> return (maybe "" id val)

resolve (Var tem) = resolve tem >>= \name -> (ask >>= \env -> return (lookupVar name env))
>>= \val -> return (maybe "" id val)

Reader 定義在這:
instance Monad (Reader e) where 
return a = Reader $ \e -> a
(Reader r) >>= f = Reader $ \e -> f (r e) e
明明 e 就沒有餵給 f, 怎麼變出來的 @@

是說其實可以把 ask 忘掉,然後記得 asks 可以取得目前 Env,
這樣好像也是可以寫程式..... 但背後完全不懂行嗎? @@

4 retries:

jinjing said...

不懂。。也能写,我其实一直那么写,懒得读 paper 。。 ask 不是在 readerclass 里的函数么,在 reader monad 里实例成了 id, id 作用在 env 上,返回的就是 env 了,然后 do 里面把返回值绑定在中间变量上。。 大概是这样, asks 就是在 env 上再作用一个函数,monad 里返回的就是这个 env 作用后的结果,也可以帮定。大部分 monad 的文章都很不人性化,我是看了 http://www.iterasi.net/openviewer.aspx?sqrlitid=ixx7fcluvek_9lfolsxr_g 入的门 。。

scm said...

e 有餵給 f 呀。在 Reader 定義的第二行:

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

e 不就是 f 的第二個參數嗎?

多一個 data constructor 可能變得比較難讀。我們把 Reader 這個 constructor 拿掉的話,Reader e a 就是 e -> a, 一個「拿一個 environment e, 傳回 a」的函數。Bind 的定義就是:

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

r 已經是一個型別是 e -> a 的函數了,而 f 是 a -> (e -> b). 等號右邊必須是一個 e -> b, 那顯然做法就是先把環境餵給 r 產生一個 a, 然後給 f, 得到一個 e -> b. 最後還要把環境再餵給 f (r e) 一次,才能得到 b.

scm said...

ask 可以把環境取出來,它的型別是 e -> e. 怎麼做呢?就用 ask = id 就可以了。我們把這段程式展開看看:

resolve tem >>= \name ->
(ask >>= \env -> return (lookupVar name env)) >>=
\val -> return (maybe "" id val)

根據 >>= 的 associativity 它等於:

resolve tem >>= \name ->
ask >>= \env ->
lookupVar name env >>= \val ->
return (maybe "" id val)

把 ask >>= 之後的 \env ... 簡寫成 F name:

resolve tem >>= \name ->
ask >>=
F name

然後,別忘記這整串東西本身就是一個吃一個 e 的函數。展開第一層得到:

\e -> (\name -> ask >>= F name) (resolve tem e) e

可以看到 (\name ->...) 那段的最後一個參數就是 e. 這是它得到 e 的途徑。做一下 beta reduction:

\e -> (ask >>= F (resolve tem e)) e

然後... ask >>= .. 也是一個吃一個 e 的函數:

\e -> (\e -> F (resolve tem e) (ask e) e) e
= \e -> F (resolve tem e) (ask e) e

你會看到同一個 e 被餵給了三個 sub expression: resolve tem, ask, 和 F. 這是 reader monad 和 state monad 不一樣的地方。後者要把 state 串起來,前者只是把同一個環境 copy 很多份一直往下面傳。

ask 的任務是把 e 取出來,而我們知道 ask 就只是 identity function. 化簡成

\e -> F (resolve tem e) (ask e) e
= \e -> (\env -> lookupVar ...) (ask e) e
= \e -> (\env -> lookupVar ...) e e

F 就這樣得到 e 了。其實他得到兩個 e. 第一個是 ask 的結果,剛好是 e. 第二個是要接著往下面傳的 e, F 不會直接去動它。

godfat 真常 said...

> jinjing
呵呵,你也有光顧這裡,真感榮幸 XD
感謝說明和連結,今天回去再細看 :p

> scm
真感謝如此詳細的說明 XDD
今天早上搭車的時候,忽然想到自己有兩個盲點,
現在在忙別的沒辦法確認,我回去的時候再來細看這邊

我猜 Reader 應該快要能解決了 XD
那時再貼第三篇總結 ~

Post a Comment

All texts are licensed under CC Attribution 3.0