2

作为练习¹，我编写了一个仅使用char解析器和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'

identityParser然而，我对我申请的具体内容并不满意foldr。必须为pure.

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

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

Trifecta 或其他库中是否有上述身份解析器？还是解析器不打算在 a 中使用fold？

¹ 该练习来自Haskell Programming from first principle一书的解析器组合器章节。

² 正如cole 所指出的，Parser是一个Alternative，因此是一个幺半群。该empty函数源于Alternative, 而不是Parser的应用实例。

4

2 回答 2

2

您不希望它解析 aString吗？现在，从函数签名中可以看出，它解析 a 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')

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

关于幺半群的题外话

我的第一个直觉是使用 mempty 但 Parser 不是幺半群。

啊，但事实并非如此。Parser是Alternative，它是Monoid。但是您实际上并不需要查看AlttypeclassData.Monoid来理解这一点；Alternative的类型类定义看起来就像 aMonoid的：

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作用。

于 2019-07-15T17:07:42.737 回答
1

让我们将您的 fold+reverse 重写为一个 fold 以澄清发生了什么：

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

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

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 将有助于向您展示他们的类型。

[*] 主要的例外是当它是一个“懒惰的 monad”时，比如Reader、lazy Writer、lazyState等。但是解析器 monad 通常是严格的。

于 2019-07-15T17:38:43.070 回答