接著書上教大家做 parser ，把 parser 分成兩個部分： lexical analysis `clex :: String -> [Token]`和 syntax analysis `syntax :: [Token] -> CoreProgram` 。 

`clex` 那部分就是切 token ，保留行號並移除註解（ Core 的註解竟然是 `||` 開頭，是要跟 Haskell 的 `--` 正交嗎？）。

因為沒受過教育（沒念到大三，活該），本來很怕 parser 超難，沒想到竟然是從 parser combinator 講起，而且沒有 monoid 也沒有 monad （但是還是可以看到他們的影子）！查了一下， Haskell 到了 1996 年才把 monad 用在 I/O 上，而這個問題 [Who invented Haskell's type classes?][who-type-classes] 中提到 type classes 出自 [How to make ad-hoc polymorphism less ad-hoc][type-classes] ，是 1988 年的事。

至於 Haskell 是不是從設計之初就有 type classes ，也許讀完 Being Lazy with Class 後才會知道 XD

[who-type-classes]: http://softwareengineering.stackexchange.com/questions/247023/who-invented-haskells-type-classes
[type-classes]: http://homepages.inf.ed.ac.uk/wadler/topics/type-classes.html

---

按之前的習題，現在 token 長這樣：

```
type LineNum = Int
type Token = (LineNum, String)
```

而 parser 要做的事情有：

  * 把一串 token 轉成某種結構
  * 結果可能不只一種，也有可能沒結果（失敗）
  * 得留下剩下的 token ，好交給下一棒
  * 小 parser 的結果可以組合成大的

於是 parser 長這樣：

```
type Parser a = [Token] -> [(a, [Token])]
```

想起 Learn you a Haskell 把 list 稱為 non-deterministic values ，就是這樣用吧。

---

最基本的 parser 是 `pLit` 和 `pVar` ：

```
pLit :: String -> Parser String
pVar :: Parser String
```

`pLit` 讀到跟它的 String 相同的 token 時，會成功，否則得到 `[]` 。 `pVar` 現在則是看到 token 就成功。

為了把不同可能性串在一起，有了 `pAlt` ：

```
pAlt :: Parser a -> Parser a -> Parser a
pAlt p1 p2 toks = (p1 toks) ++ (p2 toks)
```

那個 `(++)` 看起來很眼熟，如果換成 `(<>)` 就聞到了 monoid 的味道...。

這邊還有一個陷阱，是由 `type` 關鍵字造成的。明明 `pAlt` 只有兩個 `Parser a` 參數，實作時卻吃 `p1`, `p2`, `toks` 三個東西...。原來是因為 `Parser a` 實際上是 `[Token] -> [(a, [Token])]` ，所以 `pAlt p1 p2 toks` 其實可以看成 `(pAlt p1 p2) toks` 。

記得她在「實例介紹 Monad 應用設計與實作」演講中也抱怨過初學時踩過這個雷。

另外這次讀 IFL 才知道 Haskell 可以有很多怪寫法，想是把 pattern matching 跟 guard 混著用：

```
clex _ [] = []
clex lineNum (c:cs)
  | c == '\n' = clex (lineNum + 1) cs
```

還有在 Miranda 裡，

```
clex (c:cs) = c == '\n' | clex cs
```

guard 看起來像 JS 的 `||` XD

---

為了把小 parser 組合在一起，有了 `pThen` ：

```
pThen :: (a -> b -> c) -> Parser a -> Parser b -> Parser c
pThen combine p1 p2 toks
  = [ (combine v1 v2, toks2) | (v1, toks1) <- p1 toks
                             , (v2, toks2) <- p2 toks
    ]
```

要是 `p1 toks` 或是 `p2 toks` 沒結果，那整個就都沒結果，這點讓我想到 `(>>=)` 。而且 Miranda 沒有 monad 但是卻出現上述這種 list comprehension ，可見它還不是 do notation 的 syntactic sugar 。

---

還可以組合出找 0~n 個東西的 parser ：

```
pEmpty :: a -> Parser a
pEmpty a toks = [(a, toks)]

pZeroOrMore :: Parser a -> Parser [a]
pZeroOrMore p = (pOneOrMore p) `pAlt` (pEmpty [])

pOneOrMore :: Parser a -> Parser [a]
pOneOrMore p = pThen (:) (pZeroOrMore p)
```

`pEmpty` 看起來就一副 `mempty` 或 `pure` 的樣子， `pOneOrMore` 中用到的 `(:)` 則讓我想起 `mappend` ... = =|||

有趣的是，第一次寫，誤把 `pOneOrMore` 寫成：

```
pOneOrMore p = pThen (:) (pOneOrMore p)
```

成了 `pInfinite` ，對上有限長度的 `[Token]` ，自然失敗，得到 `[]` 。

還有長得像 `fmap`, `<*>` ，根本就是 `<**>` 的 `mApply :: Parser a -> (a -> b) -> Parser b` ，等這些工具都準備好，才真的開始 parse Core language 。

今天先這樣。