身份解析器

Question

作为练习，我编写了一个字符串解析器，它只使用char解析器和三联

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应用到的特定foldr并不满意。不得不为pure选择一个任意的字符似乎很麻烦。

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

相反，我要寻找的是一个解析器，它在与其他解析器组合时作为一个中性元素工作。它不应该成功地执行任何操作，即不提前游标并让下一个解析器使用该字符。

是否有上面描述的标识解析器在Trifecta或其他库中？或者解析器不应用于fold中。

这个练习来自于“Haskell第一原理编程”一书的解析器组合器一章。

作为一个有用的科尔指出，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')

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

关于一元的离题

我的第一直觉是使用mempty，但Parser不是一个单样体。

啊，但事实并非如此。解析器是替代方案，它是莫尼特。但是，您并不需要看一下Alt的Data.Monoid类型来理解这一点；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重写为一个折叠，以澄清所发生的事情：

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会帮你显示它们的类型。

*主要的例外是，当它是像Reader、惰性Writer、懒惰State等“懒散的单子”时，但是解析器单元通常是严格的。