caasih.net

Re: Build Your Own Haskell Compiler #1.2

明明只是入門,卻讓苦惱了半年,程度真差。

instance Functor Desugar where
  fmap f (D (info, term)) = D (info, f term)

instance Applicative Desugar where
  pure term = D (0, term)
  D (info, f) <*> D (info', t) = D (info + info', f t)

上次讓 Desugar 成為了 Functor 還有 Applicative ,於是可以讓一個函式作用在被 Desugar 包起來的 Term 上面(fmap :: (a -> b) -> f a -> f b)。也有了最小最小的 context (pure :: a -> f a),跟將收在 Desugar 中的函式作用在被包起來的其他東西的辦法((<*>) :: f (a -> b) -> f a -> f b)。

再來我好奇的是,他們符合各自該符合的 laws 嗎?LYaH 教我 Functor 和 Applicative 得符合某些規定,而那些規定是 compiler 沒辦法幫忙驗證的。

Functor Laws

fmap id = id
famp (p . q) = fmap p . fmap q

Functor Laws 有兩個,一是 fmap idid 作用起來是一樣的。 Desugarfmap 對裡面的 Term 和藏起來的 Info 沒有做多餘的事情,很明顯滿足這點。另外一條是 fmap (p . q)fmap p . fmap q 作用起來是一樣的,如果從「打開...做事情...關起來」的角度看,那前者是打開來做兩件事然後關起來,後者是打開做一件事,關起來,然後再打開做一件事情,再關起來。也很明顯滿足了。

注意到 fmap 的數量,在第一條 law 裡,從 1 個變成 0 個,在第二條 law 裡,從 1 個變成 2 個,我還不知道該怎麼理解這件事、或是這件事有沒有什麼意義。

Applicative Functor Laws

pure id <*> v = v
pure f <*> pure x = pure (f x)
u <*> pure y = pure ($ y) <*> u
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

第一條 pure id <*> v = v 可以說是 fmap id = id 的進階版(或者寫成 fmap id a = a 比較一致?),只是前者的 id 先放在一個最小的 context 中了。

第二條 pure f <*> pure x = pure (f x) ,也算明顯。對 Desugar 來說,最小 context 裡的 Info 都是 0,相加和本來一樣沒有變化,也符合這條 law 。

第三條 u <*> pure y = pure ($ y) <*> u ,我想重點也不是在 u 裡面的函式怎麼作用在 y 上,而是在 pure 從右邊換到左邊的過程中,是不是不造成多餘的改變?在 Desugar 中, pure 在右邊會變成 info + 0 ,和 pure 在左邊的 0 + info 是一樣的。

第四條我一開始是看不明白的,現在看來,對 Desugar 來說,是表示 0 + u的info + v的info + w的infou的info + (v的info + w的info) 不該有差別。


再來想加上被 [] 包起來的 Term ,然後需要讓 Desugar 也是個 Monad ,接著配上個和 do notation 合作起來更融洽的 increase ,就可以把這一切用在 haskell-src-exts 給我們的 AST 上了。

由 Isaac Huang 發佈於