从一系列解析器组合器构造长度为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")

而不是相对更多的cromulent:

("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)

- 在编译时,如何判断由此产生的元组<>与来自任何其他解析器的预期返回类型之间的区别？我只能推测需要额外的语法.

所以,我完全不确定这是一个好主意,甚至可能.即使对我的情况不是一个好主意,我也很想知道该怎么做(而且我很想知道如果这是不可能的!).

• 后续问题(如果这个疯狂的计划是可能的).如何在一个<>s 链中注释一个项目被排除在结果元组之外？

例如,假设一个后缀注释<#:

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没有一个函数可以形成一个monadic动作,从两个monadic动作中产生一对,但它确实提供了一些有用的构建块.特别是,它提供<*>:

(<*>) :: 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元组的类型:

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中使用多种类型的函数？当然是Typeclasses!但普通的类型类不会这样做:我们需要功能依赖.另外,我想不出一个合适的名字,所以我只是称之为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,所以元组是无关紧要的,所以这样一个复杂的解决方案似乎是不合理的,特别是因为你必须使用元组的替代方案是如此简单(计算项目的数量并插入适当的元组构造函数).