parsing - Applicative Functor 中的条件循环

Question

假设 Parser x是解析 x 的解析器.这个解析器可能拥有 many组合器，它解析零次或多次出现的事物(当项目解析器失败时停止)。

如果Parser，我可以看到如何实现它形成一个单子(monad)。如果Parser，我不知道该怎么做只是一个应用仿函数。似乎没有任何方法可以检查先前的结果并决定下一步要做什么(正是 monads 添加的概念)。我错过了什么？

Answer 1

Alternative类型类提供 many组合器:

class Applicative f => Alternative f where
    empty :: f a
    (<|>) :: f a -> f a -> f a
    many  :: f a -> f [a]
    some  :: f a -> f [a]

    some = some'
    many = many'

many' a = some' a <|> pure []
some' a = (:) <$> a <*> many' a

many a组合器的意思是“零个或多个”a .

some a组合器的意思是“一个或多个”a .

因此:

some a组合器返回一个列表 a后跟 many a (即 1 + (0 or more) )。

many a组合器返回 some a或一个空列表(即 (1 or more) | 0 )。

many组合器取决于 (<|>)运算符，它可以被视为 JavaScript 等语言中的默认运算符。例如，考虑 Alternative Maybe 的实例:

instance Alternative Maybe where
    empty = Nothing
    Nothing <|> r = r
    l       <|> _ = l

本质上是 (<|>)如果它是真实的，应该返回左边的值。否则它应该返回右侧的值。

一个 Parser是一种数据结构，其定义类似于 Maybe ( applicative lexer combinators 和解析器组合器的想法基本相同):

data Lexer a = Fail | Ok (Maybe a) (Vec (Lexer a))

如果解析失败， Fail返回值。否则为 Ok返回值。由于 Fail <|> pure []是 pure [] ，这就是 many组合器知道何时停止并返回一个空列表。