haskell - Haskell Alternative 中 "some"和 "many"函数的定义是什么意思

Question

我一直想用 Haskell 编写一个词法分析器，并偶然发现了这些函数。

If defined, some and many should be the least solutions of the equations:

some v = (:) <$> v <*> many v

many v = some v <|> pure []

我知道 (:)在some被提升并应用于 v 的值为了将其添加到 many v 返回的列表中。

但是为什么 many 的定义是这样的从 some 开始？为什么它会与 pure [] 连接起来？

这两个函数有什么关系或区别？ some 意味着什么？和many是这些方程的最小解？递归如何停止？救命!

Answer 1

• some p表示一个 p 的一个或多个匹配
• many p表示零个或多个p匹配

输入"abc" , many letter和some letter都会解析abc .

但对于输入"123" , many letter将输出空字符串 "" 。 some letter会报错。

根据定义。 some v至少需要 1 场 v 的匹配，所以我们可以先解析v那么我们需要 v 的 0 个或多个匹配项，即many v 。它是这样的:

some v = do
    first_match <- v
    rest_matches <- many v
    return $ first_match : rest_matches

与 some v = (:) <$> v <*> many v 相同.

但是对于 many v 。它将匹配 some v (1 个或多个)或什么都没有(纯 [])。

many v = if matches (some v) then return (some v) else return nothing .

你可以尝试解决writing applicative parsers from scratch来自代码 war 。

Functional pearls也是关于解析组合器的非常好的引用。

---

1. https://www.codewars.com/kata/writing-applicative-parsers-from-scratch
2. http://www.cs.nott.ac.uk/~pszgmh/pearl.pdf