parsing - 应用仿函数中的条件循环

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

我可以看到，如果Parser形成了monad，那么如何实现。如果Parser只是一个Applicative Functor，我不知道该怎么做。似乎没有任何方法可以检查先前的结果并决定下一步要做什么(准确地说是monad所添加的概念)。我想念什么？

最佳答案

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组合器知道何时停止并返回空列表的方式。

关于parsing - 应用仿函数中的条件循环，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27211930/