解析器就是個能把 JSON 或 XML 等字串轉為 list、 map 等資料結構，
而這幾天就要用 functional programming 的概念來設計能自由組合的解析器 library，我們的解析器將會從小處著手，先著重辨識輸入中簡單的字元，然後在將這些解析器組合在一起，讓它能解析更複雜的輸入。
先設計 API 的代數性質
我們之前的 API 代數性質，都是從定義資料型態開始，一步步精煉操作用的 function 實現，然後在調整原先的資料型態，其中的定律會在我們知道該如何表達這些資料型態以及 API 如何呈現後產生，
這次的 API 設計我們先來找代數性質以及定律，來看看有什麼不一樣的感覺。
首先我們不應該考慮直接解析如 JSON 或 HTML 之類的文件，好的開始是思考該如何辨識一些無意義的字，所以讓我們從辨識簡單的字元開始吧！
def char(c: Char): Parser[Char]char function 接受字元做為輸入，然後回傳一個 Parser (解析器)，能辨識字元的話，字串也可以如法泡製，
def string(s: String): Parser[String]執行解析器不應該回傳 ture 或 false 的結果，我們比較想要得到有用的東西，假設我們把 'a' 丟入呼叫 char('a') 所回傳的解析器時，預期會得到 'a' 這個字元，若解析失敗則會回傳失敗的訊息，基於以上說明，我們可以來定義 run function，
def run[A](parser: Parser[A])(input: String): Either[ParseError, A]這裡可以先不用管 Parser 和 ParseError 怎麼定義或實作，所以我們可以先把這些統整在 trait 底下（也用了 extension 把 run 放在裡面），
trait Parsers[ParseError, Parser[+_]]:
def char(c: Char): Parser[Char]
def string(s: String): Parser[String]
extension[A] (p: Parser[A])
def run(input: String): Either[ParseError, A]extension 的說明可看 純粹的 functional 狀態 (2)，
Either 的說明可看 如何不拋出例外的處理錯誤 (1)。
可以看到我們用型態參數來表達 Parser 和 ParseError，而 Parser 的 _ 是 high-kinded 型態，代表更高一層的抽象，也就是說把 _ 型態參數當作 Parser 的型態建構子，這給了我們在設計 library 時有很大的彈性接收未來可能會用的型態，例如像 Char 那樣 Parser[Char]；
Parser[+_]和Parser[+Z]是一樣的意思，用_會比較直覺，隱含著所有 Parser 下的所有型態。
在來我們的 char function 應該要滿足以下定律，
char(c).run(c.toString) == Right(c)同樣的字串也是，
string(s).run(s) == Right(s)假設我們想辨識字串 “abra” 或 “cadbara” 的話，我們可以來用個 or function 將 2 個 Parser[String] 組合起來，
def or[A](p1: Parser[A], p2: Parser[A]): Parser[A]然後以下定律可以被滿足，
or(string("abra"),string("cadabra")).run("abra") == Right("abra")
or(string("abra"),string("cadabra")).run("cadabra") == Right("cadabra") Scala 3 有 infix 這個關鍵字，它能讓我們把 function 當作中綴運算（加減乘除）那樣來使用，所以我們可以在 extension 加入 | 符號代表 or 運算；
trait Parsers[ParseError, Parser[+_]]:
def char(c: Char): Parser[Char]
def string(s: String): Parser[String]
extension[A] (p: Parser[A])
def run(input: String): Either[ParseError, A]
def or(p2: Parser[A]): Parser[A]
infix def |(p2: Parser[A]): Parser[A] = p.or(p2)最後來考慮一下如何辨識重複字串，
def listOfN[A](n: Int, Parser[A]): Parser[List[A]]然後我們可以這樣組合使用。
listOfN(3, string("ab") | string("cad")).run("ababcad") == Right("ababcad")
listOfN(3, string("ab") | string("cad")).run("cadabab") == Right("cadabab")
listOfN(3, string("ab") | string("cad")).run("ababab") == Right("ababab")”從重複辨識找到第一個正式定律
首先來想一下如何辨識 0 到 n 次的字元 ‘a’，
def many[A](p: Parser[A]): Parser[List[A]]那如果想用 Parser[Int] 知道字元 ‘a’ 出現幾次呢？我們可以考慮用 map function 實現，
def map[A, B](a: Parser[A])(f: A => B): Parser[B]如此就能以以下組合調用來知道字元 ‘a’ 出現幾次（先假裝 many 跟 map 已經放在 extension 底下）；
val numA: Parser[Int] = char('a').many.map(_.size)
numA.run("aaa") == Right(3)
numA.run("b") == Right(0)到此，我們對 map 有個強烈的預期是它只轉換那些成功解析的 Parser，解析失敗的 Parser 不會透過 map 變成成功的，反之亦然，map 會成為各種 library 中一種必定保留的結構，因此有一個正式定律出來了。
map(p)(a => a) == p因為有了 map，char function 就能用 map 實現了，
def char(c: Char): Parser[Char] =
string(c.toString).map(_.charAt(0)) 跟其它組合用 function 類似，我們也能用 map 來實現 succeed function，空字串的 Parser 在面對任何輸入字串時都會成功。
def succeed[A](a: A): Parser[A] =
string("").map(_ => a)從 Parser 中取得解析成功的部份輸入：slice
many 和 map 的組合的確可以得出重複匹配次數，但有些沒有效率，因為我們從 List[Char] 中捨棄了值，只用到 size，這裡應該能透過一個 function 取得部份的 input 的話，就能省略了中間層資料結構 List 的產生，
def slice[A](p: Parser[A]): Parser[String]然後就能這樣使用，
slice(char('a').many).run("aaba") == Right("aa")這樣我在用 slice(char('a').many).map(_.size) 的時候，操作的會是 “aa” 這個字串，基於這點，slice 很值得放在核心 APi 之中。
非空的重複辨識
就是辨識 1 到 n 次的意思啦，我們用 many1 來表示，
def many1[A](p: Parser[A]): Parser[List[A]]感覺起來 many1 應該是 many 的子項目，而實際上，many1(p) 就是解析器 p 先執行後，然後在針對同一個輸入字串執行 many(p)，這樣就能做到辨識 “1” 到 n 次，所以我們應該需要一個 function，讓我們能執行完一個 p解析器後，在執行另一個 p2 解析器，
def product[A, B](p: Parser[A], p2: Parser[B]): Parser[(A, B)]我們也可以新增 ** 符號 function 來代表 product。
Exercise D20-1
用 product 實作 map2 function，它能用 high-order function 把 2 個 Parser 中的值轉換。
def map2[A, B, C](p: Parser[A], p2: Parser[B])(f: (A, B) => C): Parser[C]有了 many1 和 product，我們就用以下調用解析 0 到多個 ‘a’ 或 1 到多個 ‘b’。
val zeroOrMoreAFollowedByOneOrMoreB = char('a').many.slice.map(_.size) ** char('b').many1.slice.map(_.size)
zeroOrMoreAFollowedByOneOrMoreB.run("bbb") == Right(0, 3)
zeroOrMoreAFollowedByOneOrMoreB.run("aaab") == Right(1, 4)
zeroOrMoreAFollowedByOneOrMoreB.run("aaabbbab") == Right(3, 3)接下來讓我們來嘗試實現 many，
def many[A](p: Parser[A]): Parser[List[A]] =
map2(p, many(p))(_ :: _) | succeed(Nil)使用 map2 是因為我們想要先執行 p 解析器，然後在遞迴的執行 many(p)（因為 many 是要辨識 0 到 n 次），然後將值透過 :: 合併，如果一開始就辨識失敗，起碼還有 0 次的空 List 可回傳，
但這裡有個問題是，Scala function 預設是 strict，所以 map2 的調用會是無窮迴圈，
所以我們要把 map2 的第 2 個參數改為 non-strict，這樣 p2 不會立即執行，除非 p 解析成功，
def map2[A, B, C](p: Parser[A], p2: => Parser[B])(f: (A, B) => C): Parser[C]相對應的 product 的第 2 個參數也要改為 non-strict，
def product[A, B](p: Parser[A], p2: => Parser[B]): Parser[(A, B)]最後順便也把 or 改為 non-strict 吧！
extension[A] (p: Parser[A])
def or(p2: => Parser[A]): Parser[A]
infix def |(p2: => Parser[A]): Parser[A] = p.or(p2)明天繼續！
