haskell - 从解析器组合器序列构造长度为n的元组

Question

题。有没有一种方法来定义一个运算符，使得由该运算符分隔的值序列产生一个平面元组？


我一直在努力寻找问题的简洁表述，因此请继续阅读以获取详细信息和示例...

描述

我正在为自己编写一些Parsec的辅助运算符，从以下内容开始：

(<@) :: GenParser tok st a -> (a -> b) -> GenParser tok st b
p <@ f = do {
    x <- p ;
    return (f x)
}

(<>) :: GenParser tok st a -> GenParser tok st b -> GenParser tok st (a, b)
p <> q = do {
    x <- p ;
    y <- q ;
    return (x, y)
 }

这些工作如下：

parseTest ((many upper) <@ length) "HELLO"
5

parseTest (many upper) <> (many lower) "ABCdef"
("ABC", "def")

不幸的是，由 <>分隔的解析器序列将导致嵌套元组，例如：

parseTest (subject <> verb <> object) "edmund learns haskell"
(("edmund", "learns"), "haskell")

而不是相对较松脆：

("edmund", "learns", "haskell")

我正在寻找一种定义 <>的方法，以便

p1 :: GenParser tok st a ; p2 :: GenParser tok st b ; p3 :: GenParser tok st c
p1 <> p2 :: GenParser tok st (a, b)
p1 <> p2 <> p3:: GenParser tok st (a, b, c)
...

我认为我从未见过Haskell程序，其中这样构造长度为 n的元组类型（在编译时已知）。而且我怀疑用这两种类型定义运算符可能很困难：

GenParser tok st a -> GenParser tok st b) -> GenParser tok st (a, b)
GenParser tok st (a, b) -> GenParser tok st c) -> GenParser tok st (a, b, c)

-在编译时如何分辨 <>生成的元组与其他解析器的预期返回类型之间的区别？我只能推测，将需要其他语法。

因此，我完全不确定这是个好主意，甚至是不可能的。即使对我的案子不是一个好主意，我也想知道该怎么做（如果不可行，我很想知道该怎么做！）。


后续问题（如果可以采用这种疯狂的方案）。如何注释一连串 <>中的一项，将其排除在结果元组之外？


例如，假设后缀注释 <#：

p1 :: GenParser tok st a
p2 :: GenParser tok st b
p1 <> keyword "is" <# <> p2 :: GenParser tok st (a, b)

背景

大约在2006年，我在大学里学习了解析器组合器。我们使用的库中存在 <@和我相信的 <>运算符，并且其执行方式与我的尝试类似。我不知道这个图书馆是什么。它可能是由一名研究生写的，用于教授我们的课程。无论如何，它似乎既不是Parsec也不是Text.Parser.Combinators中的基本解析器组合器。


奖金问题。 Text.ParserCombinators.ReadP / ReadPrec中的基本解析器组合器与Parsec中的基本解析器组合器有什么区别？


我似乎记得该库也是不确定性的，每次解析器调用都返回可能的解析集以及每个解析器的剩余未解析输入。 （成功，完整，明确的解析将导致 [(parseresult, "")]。）


最后一个问题。如果这听起来像是您听说过的事，您能否让我知道那是什么（出于怀旧之情）？

Answer 1

函子

我想引起您的注意：

(<@)      :: GenParser tok st a -> (a -> b) -> GenParser tok st b
flip fmap :: (Functor f) => f a -> (a -> b) -> f                b

您是否注意到相似之处？如果将 f的类型替换为 GenParser tok st，则得到的类型为 flip fmap。此外，这不是理论上的： (<@)是 GenParser tok st的实例。 Functor也可以以名为 fmap的运算符形式使用。因此，我们可以通过两种方式（原始方式）重写您的代码：

ghci> parseTest ((many upper) <@ length) "HELLO"
5
ghci> parseTest (fmap length (many upper)) "HELLO"
5
ghci> parseTest (length <$> (many upper)) "HELLO"
5

适用性

函子虽然不错，但功能不足以包含您的第二个示例。幸运的是，还有另一个类型类： <$>。现在， Applicative不具有形成单调动作的功能，从而产生两个单调动作中的一对，但确实提供了一些有用的构造块。特别是，它提供了 Applicative：

(<*>) :: f (a -> b) -> f a -> f b

事实证明，我们可以将其与 <*>一起编写以重写您的第二个示例：

ghci> parseTest (many upper) <> (many lower) "ABCdef"
("ABC", "def")
ghci> parseTest ((,) <$> many upper <*> many lower) "ABCdef"
("ABC", "def")

如果您不熟悉语法，则可以使用 <$>创建一个对。它的类型为 (,)。

但是 a -> b -> (a, b)并不止于此。您正在寻找一种扁平化元组的方法；但是您可以使用 Applicative直接创建一个三元组，而不是创建嵌套元组并将其展平。

ghci> parseTest ((,,) <$> subject <*> verb <*> object) "edmund learns haskell"
("edmund", "learns", "haskell")

碰巧 Applicative也有另一个运算符可以帮助您处理上一个请求： Applicative和 <*，它们分别忽略第二个操作数的结果或第一个操作数的结果。因此，如果您想忽略动词：

ghci> parseTest ((,) <$> subject <* verb <*> object) "edmund learns haskell"
("edmund", "haskell")

奖金问题

如果我没记错的话， *>允许在每个步骤中进行回溯。另一方面，Parsec不允许回溯，除非您使用 ReadP组合器或其他使用该组合器的组合器在解析器中直接或间接对其进行注释。因此，Parsec解析器不会回退太多，并且可以具有更好的最坏情况下的性能。



附录：几乎实现您的 try…（并非出于胆怯）

我不知道实现确切的 <>或使其适用于所有大小的元组的任何方法，但是如果您愿意启用一些Haskell扩展，则可以消除进行计数的需要到任意但固定大小的元组。首先，我们想要一个1元组的类型：

newtype One a = One a deriving (Eq, Read, Show)  -- derive more if you want

现在，我们需要具有以下类型的函数：

(<>) :: (Applicative f) => f ()        -> f a -> f (One a)
(<>) :: (Applicative f) => f (One a)   -> f b -> f (a, b)
(<>) :: (Applicative f) => f (a, b)    -> f c -> f (a, b, c)
(<>) :: (Applicative f) => f (a, b, c) -> f d -> f (a, b, c, d)
-- ...

我们如何在Haskell中使用多种类型的函数？类型类，当然！但是普通的类型类无法做到：我们需要功能依赖。另外，我想不出一个合适的名字，所以我将其命名为 <>。 （如果您想起一个更好的名字，请在评论中告诉我，我会进行编辑。）

{-# LANGUAGE FunctionalDependencies #-}
class C a b c | a b -> c, c -> a b where
    (<>) :: (Applicative f) => f a -> f b -> f c

然后，要实际实现我们的实例，我们需要 C：

{-# LANGUAGE FlexibleInstances #-}
instance C ()        a (One a)      where (<>) _ = fmap One
instance C (One a)   b (a, b)       where (<>) = liftA2 $ \(One a)   b -> (a, b)
instance C (a, b)    c (a, b, c)    where (<>) = liftA2 $ \(a, b)    c -> (a, b, c)
instance C (a, b, c) d (a, b, c, d) where (<>) = liftA2 $ \(a, b, c) d -> (a, b, c, d)
-- ...

现在，您可以像这样编写解析器：

parseTest (return () <> subject <> verb <> object) "edmund learns haskell"
("edmund", "learns", "haskell")

我们确实必须在它之前写 FlexibleInstances，这是不可取的。您可以保留先前的 return () <>实现，并将我们的新实现重命名为 <>，然后可以这样编写解析器：

parseTest (subject <+> verb <> object) "edmund learns haskell"
("edmund", "learns", "haskell")

（ <+>用于在前两个之后加入所有解析器）可能有一种方法可以使单个运算符使用 <+>进行操作，但是明显的解决方案违反了功能依赖性。

需要问的问题

如果您考虑使用后一种方法，建议您不要使用。首先，如果您要使用元组，则不难计算要解析的项目数。其次，您通常一开始就不会使用元组，并且这种方法仅在您尝试获取元组时才有效。但是，有什么比元组更有意义的呢？好吧，一个AST节点。例如，如果您正在为一种编程语言编写解析器，则可能具有以下类型：

data Expression = ...
                | IfExpression Expression Expression Expression
                | ...
                deriving (...)

然后，要解析它，可以使用 OverlappingInstances：

parseIfExpression = IfExpression
                <$> keyword "if"    *> expression
                <*  keyword "then" <*> expression
                <*  keyword "else" <*> expression

在这里，我们不需要计算商品数量；它封装在 Applicative类型构造函数的类型中。由于通常您将要解析AST，因此元组将是不相关的，因此这种复杂的解决方案似乎是不合理的，尤其是因为必须使用元组的替代方案如此简单（计算项目数并插入适当的值元组构造函数）。