Applicative Functor中的条件循环

Question

假设这Parser x是一个解析的解析器x.这个解析器可能拥有一个many组合器,可以解析零次或多次出现的事情(当项解析器失败时停止).

如果Parser形成一个monad ,我可以看到如何实现它.如果Parser只是一个Applicative Functor,我无法弄清楚如何做到这一点.似乎没有任何方法可以检查以前的结果并决定下一步该做什么(正是monad添加的概念).我错过了什么？

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

1. 该many a组合子的意思是"零个或多个" a.
2. 该some a组合子的意思是"一个或多个" a.

因此:

1. 该some a组合子返回一个列表a之后many a(即1 + (0 or more)).
2. 该many a组合子要么返回some a一个空列表(即(1 or more) | 0).

该many组合子取决于(<|>)它可以被看作是像JavaScript语言的默认操作员操作.例如,考虑以下Alternative实例Maybe:

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

基本上(<|>)应该返回左侧值,如果它是真的.否则它应返回右侧值.

A Parser是一个类似于Maybe(应用词法分析器组合器和解析器组合器的思想基本相同)的数据结构:

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

如果解析失败,Fail则返回该值.否则Ok返回一个值.由于Fail <|> pure []IS pure [],这是如何many组合子知道何时停止,并返回一个空列表.