身份解析器

Question

作为练习¹，我编写了一个仅使用 char parsers and Trifecta:

的字符串解析器

import           Text.Trifecta
import           Control.Applicative            ( pure )

stringParserWithChar :: String -> Parser Char
stringParserWithChar stringToParse =
  foldr (\c otherParser -> otherParser >> char c) identityParser
    $ reverse stringToParse
  where identityParser = pure '?' -- ← This works but I think I can do better

解析器工作正常：

parseString (stringParserWithChar "123") mempty "1234"
-- Yields: Success '3'

但是，我对我申请 foldr 的具体 identityParser 不满意。必须为 pure.

选择任意字符似乎很老套

我的第一直觉是使用 mempty 但 Parser 不是幺半群。它是一个应用程序，但empty构成一个不成功的解析器²。

我正在寻找的是一个在与其他解析器结合时作为中性元素工作的解析器。它应该成功地什么也不做，即不推进光标并让下一个解析器使用该字符。

在 Trifecta 或其他库中是否有如上所述的身份解析器？或者解析器不应该用于 fold?

¹ 该练习来自 Haskell Programming from first principles.

一书的解析器组合器章节

² 与一样，Parser 是一个 Alternative，因此是一个幺半群。 empty 函数源于 Alternative，而不是 Parser 的应用实例。

Answer 1

你不想让它解析 String 吗？现在，您可以从函数签名中看出，它解析 Char，返回最后一个字符。仅仅因为你只有一个 Char 解析器并不意味着你不能制作一个 String 解析器。

我假设您想解析一个字符串，在这种情况下，您的基本情况很简单：您的 identityParser 只是 pure "".

我认为这样的事情应该可行（并且应该顺序正确，但可能会颠倒过来）。

stringParserWithChar :: String -> Parser String
stringParserWithChar = traverse char

展开，你会得到类似

的东西

stringParserWithChar' :: String -> Parser String
stringParserWithChar' "" = pure ""
stringParserWithChar' (c:cs) = liftA2 (:) (char c) (stringParserWithChar' cs)
-- the above with do notation, note that you can also just sequence the results of
-- 'char c' and 'stringParserWithChar' cs' and instead just return 'pure (c:cs)'
-- stringParserWithChar' (c:cs) = do
--   c'  <- char c
--   cs' <- stringParserWithChar' cs
--   pure (c':cs')

如果它们不起作用请告诉我，因为我现在无法测试它们……

关于幺半群的题外话

My first intuition was to use mempty but Parser is not a monoid.

啊，但事实并非如此。 Parser is an Alternative, which is a Monoid。但是您真的不需要查看 Data.Monoid 的 Alt 类型类来理解这一点； Alternative 的类型类定义看起来就像 Monoid 的：

class Applicative f => Alternative f where
  empty :: f a
  (<|>) :: f a -> f a -> f a
  -- more definitions...

class Semigroup a => Monoid a where
  mempty  :: a
  mappend :: a -> a -> a
  -- more definitions...

不幸的是，您想要的东西更像产品而不是 Alt，但这就是 Parser 的默认行为。

Answer 2

让我们将您的 fold+reverse 重写为 fold 以阐明发生了什么：

stringParserWithChar :: String -> Parser Char
stringParserWithChar =
  foldl (\otherParser c -> otherParser >> char c) identityParser
  where identityParser = pure '?'

任何时候你看到 foldl 曾经使用它的 Monad 实例构建一些东西，这有点可疑[*]。它暗示你真的想要某种 monadic 折叠。让我们看看这里...

import Control.Monad

-- foldM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
attempt1 :: String -> Parser Char
attempt1 = foldM _f _acc

这将运行陷入您之前看到的同样的麻烦：您可以使用什么作为起始值？因此，让我们使用标准技巧并从 Maybe:

开始

-- (Control.Monad.<=<)
--   :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c
stringParserWithChar :: String -> Parser Char
stringParserWithChar =
  maybe empty pure <=< foldM _f _acc

现在我们可以用 Nothing 开始弃牌，然后立即切换到 Just 并保持原样。我会让你填空； GHC 会帮助您了解它们的类型。

[*] 主要的例外是当它是 "lazy monad" 时，例如 Reader、惰性 Writer、惰性 State 等。但是解析器 monad 通常是严格的。

身份解析器

Identity parser

haskell

parser-combinators

trifecta

关于幺半群的题外话