从解析器组合器序列构建长度为n的元组

Question

从解析器组合器序列构建长度为n的元组

haskellparser-combinators

3

问题. 是否有一种方法可以定义一个操作符，使得由该操作符分隔的一系列值产生一个扁平的元组？

我一直在寻找一个简洁的表达我的问题的方式，所以请继续阅读详细信息和示例...

描述

我正在为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, "")]。)

最后一个问题。 如果你听说过这个，能告诉我它是什么吗？(为怀旧之情)

- Edmund

1

做得好，思考得很正确，引发了一个出色的答案。 - AndrewC

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- icktoofay · Accepted Answer

函数对象

现在请注意以下内容:

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

你有没有注意到相似之处？如果我们在 flip fmap 的类型中将 f 替换为 GenParser tok st，我们就得到了 (<@) 的类型。此外，这不仅是理论上的： 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）。现在，应用函子没有一个函数可以生成一个由两个单子动作组成的二元组，但它提供了一些有用的构建块。特别是它提供了<*>：

(<*>) :: 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并不止于此。你正在寻找一种将元组展平的方法；但是，与其创建嵌套元组并展平它们，你可以使用Applicative直接创建三元组：

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

而且恰好 Applicative 有另一个运算符可以帮助你实现最后一个要求，那就是：<* 和 *>，分别忽略第二个操作数的结果或第一个操作数的结果。因此，如果你想忽略动词：

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

奖励问题

如果我没记错，ReadP 允许在每一步进行回溯。而另一方面，Parsec 只有在您直接或间接地使用 try 组合子或其他使用该组合子的组合子来注释您的解析器时，才允许回溯。因此，Parsec 解析器不会回溯得太多，可以具有更好的最坏情况性能。

附录：实现你的 `<>`……几乎 ^{_{(不适合新手)}}

我不知道有没有什么方法可以实现你的确切的 <>，或使其对所有元组大小都有效，但是如果你愿意启用一些 Haskell 扩展，你就可以消除计数的需求，以任意但固定的元组大小工作。首先，我们需要一个类型来表示 1-tuple：

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中，我们如何拥有具有多种类型的函数？当然是通过类型类！但是，一个普通的类型类不足以胜任：我们需要函数依赖。此外，我想不出一个合适的名称，所以我将其命名为C。^{_{（如果您能想到更好的名称，请在评论中告诉我，我会进行编辑。）}}

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

然后，为了实际执行我们的实例，我们需要使用 FlexibleInstances：

{-# 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")

在这之前我们必须写 return () <>，这样做并不理想。你可以保留你以前的实现方式 <>，并将我们的新实现方式重命名为 <+>，然后你可以像这样编写解析器：

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

(<+>用于连接前两个解析器之后的所有解析器) 可能有一种方法可以使用OverlappingInstances使单个运算符执行此操作，但明显的解决方案违反了功能依赖关系。

需要提出的问题

如果您正在考虑使用后一种方法，我建议您不要这样做。首先，如果您要使用元组，则很容易计算要解析的项数。其次，您通常不会首先使用元组，而且只有在尝试获取元组时才使用此方法。但是，什么比元组更有意义呢？好吧，是AST节点。例如，如果您正在编写一个编程语言的解析器，您可能会有一个像这样的类型：

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

然后，为了解析它，您可以使用 Applicative ：

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

在这里，我们不需要计算项目的数量；它被封装在IfExpression类型构造函数中。由于通常你会解析AST，元组是无关紧要的，所以这样一个复杂的解决方案似乎是不合理的，特别是当你必须使用元组时，替代方案是如此简单（计算项目的数量并插入适当的元组构造函数）。

从解析器组合器序列构建长度为n的元组

描述

背景

函数对象

应用函子

奖励问题

附录：实现你的 <>……几乎 (不适合新手)

需要提出的问题

附录：实现你的 `<>`……几乎 ^{_{(不适合新手)}}