Applicative Parser派生Alternative without empty

Question

从阅读 this answer 中，我了解到 Alternative 中包含 empty 主要是一个设计决定，目的是使 Alternative 成为幺半群（因此更强大） .在我看来，这也是因为否则你无法表达 Alternative.

的任何定律

但是如果我有像这样的通用应用程序解析器，这会很痛苦：

newtype Parser err src target = Parser (ExceptT err (State [src]) target)
  deriving (Functor, Applicative, Alternative, Monad, MonadState [src], MonadError err)

显然，我们可以从 Control.Applicative 获得与 <|> 和 many/some 相同的行为：

option :: Parser e s t -> Parser e s t -> Parser e s t
option parserA parserB = do
  state <- get
  parserA `catchError` \_ -> put state >> parserB

many :: Parser e s t -> Parser e s [t]
many parser = some parser `option` return []

some :: Parser e s t -> Parser e s [t]
some parser = (:) <$> parser <*> many parser

尽管其中 none 使用了 empty，但似乎我不得不重新实现它们而不是派生 Alternative，因为我无法构思通用方法为它实例化 empty（当然，我仍然需要实例化 <|> 以在 parserA 错误时保留 state，但随后我可以获得 some、many、optional 和朋友免费）。

深入研究 Parsec 的源代码，它似乎颠覆了这一点，因为它不允许自定义错误类型（或者至少，Parsec 没有被自定义错误类型参数化）：

instance Applicative.Alternative (ParsecT s u m) where
    empty = mzero
    (<|>) = mplus

instance MonadPlus (ParsecT s u m) where
    mzero = parserZero
    mplus p1 p2 = parserPlus p1 p2

-- | @parserZero@ always fails without consuming any input. @parserZero@ is defined
-- equal to the 'mzero' member of the 'MonadPlus' class and to the 'Control.Applicative.empty' member
-- of the 'Control.Applicative.Alternative' class.

parserZero :: ParsecT s u m a
parserZero
    = ParsecT $ \s _ _ _ eerr ->
      eerr $ unknownError s

unknownError :: State s u -> ParseError
unknownError state        = newErrorUnknown (statePos state)

newErrorUnknown :: SourcePos -> ParseError
newErrorUnknown pos
    = ParseError pos []

从中获得灵感，似乎唯一合理的解决方法是让我的通用解析器用类似以下内容包装用户错误类型：

 data ParserError err = UserError err | UnknownError

 newtype Parser err src target = Parser (ExceptT (ParserError err) (State [src]) target)
  deriving (Functor, Applicative, Alternative, Monad, MonadState [src], MonadError err)

然后empty可以是：

empty = throwError UnknownError

不过，感觉错了。这种包装的存在只是为了满足 empty 的要求，它让这个通用解析器的消费者做更多的工作来处理错误（他们现在还必须处理 UnknownError 并解包他们的自定义错误）。有什么办法可以避免这种情况吗？

Answer 1

这是标准 base 层次结构的问题。它不是非常模块化。在一些完美的世界中，如果我们想实现最大的模块化，Alternative 将被分成三种类型类。

请参阅 PureScript 世界中的 Alternative 定义：

https://pursuit.purescript.org/packages/purescript-control/3.3.0/docs/Control.Alternative#t:Alternative

像这样：

class Functor f <= Alt f where
  alt :: forall a. f a -> f a -> f a  -- alt is (<|>)

class Alt f <= Plus f where
  empty :: forall a. f a

class (Applicative f, Plus f) <= Alternative f

因此，如果类型层次结构足够模块化，您可以为您的 Parser 类型实现 Alt（并拥有所有 <|>-only-related 功能）但不是 Alternative。如果 Alternative 是 Monoid 那么 Alt 就是 Semigroup：你可以 append 元素但是你没有空元素。

注意，之前在 GHC base 包 Applicative 中不是 Monad 的超类，Semigroup 不在 base 中，仅在 GHC-8.4.1 中 Semigroup 将是 Monoid 的超类。所以你可以期待在未来的某个时候类似的事情（模块化）会发生在 Alternative.

Applicative Parser派生Alternative without empty

Applicative Parser deriving Alternative without empty

parsing

haskell

applicative

alternative-functor