1

出于教学原因，我正在实现类似于 Parsec 的功能。Motive 是在不使用 Monad 魔法的情况下定义 Functor、Applicative 和 Alternative 实例。Functor 和 Applicative 的实例很好。然而，<|>在 Alternative 中定义是磨损我的头发。

newtype Parser t = Parser (String -> [(t, String)])

parse (Parser p) s = p s

instance Functor ....
instance Applicative ....

empty1 = Parser $ \s -> []

orp :: Parser t -> Parser t -> Parser t
-- orp :: (Eq t) => Parser t -> Parser t -> Parser t  -- this works too
p1 `orp` p2 = Parser $ \s -> let p1out = parse p1 s
                                 e     = parse empty1 s
                             in
                              if p1out == e
                              then parse p2 s
                              else p1out     

{- 
instance Alternative Parser where
  empty = Parser $ \s -> []

  (<|>) = orp -- fails to compile
-}

ghc 抱怨它无法Eq从上下文中推断出来，即使我添加Eq了 orp` 的签名。显然，我不能在实例声明中添加签名以使其表现良好。单态限制没有帮助；也许我不是很了解。

我错过了什么？我应该探索存在类型吗？还是我犯了一个根本性的错误？或者这是不可能的？

4

2 回答 2

4

而不是使用 与空列表进行比较(==)，您应该进行模式匹配

orp :: Parser t -> Parser t -> Parser t
orp p1 p2 = Parser $ \s ->
    case parse p1 s of
      [] -> parse p2 s
      xs -> xs

在没有类型类约束的情况下实现相同的行为，因此可用于实例声明。

于 2012-07-27T10:36:09.077 回答
2

Daniel Fischer 提出了一个具体的解决方案；我想建议一个抽象的修复。在此过程中，我们将公开您在这里做出的设计决策，您甚至可能没有意识到自己做出了（我会证明您的决定不正确）。

众所周知，应用函子组成；许多其他类型的函子配对组成的不太为人所知（尽管肯定不是我发明的）。特别是，替代函子与任一侧的函子组合以产生新的替代函子。下面，我将使用 Haskell 语法来解释我的意思。我将编写无效的Haskell——因为我将使用type而不是newtype到处使用以避免混乱——但稍后我们将使用无效的 Haskell 来导出有效的 Haskell。

type (f :. g) a = f (g a) -- like in TypeCompose

-- (1)
instance (Applicative f, Alternative g) => Alternative (f :. g) where
    empty = pure empty
    x <|> y = liftA2 (<|>) x y

-- (2)
instance Alternative f => Alternative (f :. g) where
    empty = empty
    x <|> y = x <|> y

（这些实例重叠得非常非常多。）

从语义上讲，我们现在可以将您的类型视为类型组合的链：

-- (3)
type Parser = (String ->) :. [] :. (String,)

...在这里我们观察到这(String ->)是Applicative(4)[]的一个实例并且是Alternative(5) 的一个实例。这意味着我们应该能够Alternative通过将语义定义Parser与上面的实例耦合来从 this 中“读取”一个实例。

empty :: Parser t
= -- (3)
empty :: (String ->) :. [] :. (String,)
= -- (1)
pure (empty :: [] :. (String,)) :: (String ->) :. ([] :. (String,))
= -- (4)
const (empty :: [] :. (String,)) :: (String ->) :. ([] :. (String,))
= -- (2) to use []'s empty rather than [] :. (String,)'s empty
const (empty :: [] :. (String,)) :: (String ->) :. ([] :. (String,))
= -- (5)
const [] :: (String ->) :. ([] :. (String,))

p <|> q :: Parser t -> Parser t -> Parser t
= -- (3)
p <|> q :: ... -> ... -> ((String ->) :. [] :. (String,))
= -- (1)
liftA2 (<|>) p q
= -- (4)
\s -> p s <|> q s
= -- (2) to use []'s <|> rather than [] :. (String,)'s <|>
\s -> p s <|> q s
= -- (5)
\s -> p s ++ q s

所以，从语义上讲，我们知道我们现在想要empty和<|>如何表现Parsers，剩下的唯一技巧就是添加所有适当的 newtype 构造函数和解构函数。

instance Alternative Parser where
    empty = Parser (const [])
    Parser p <|> Parser q = Parser (\s -> p s ++ q s)

或者，如果我们感到兴奋，我们可以用更重载的语法编写同样的东西：

instance Alternative Parser where
    empty = Parser (pure empty)
    Parser p <|> Parser q = Parser (liftA2 (<|>) p q)

请注意，这个实现(<|>)实际上总是从q!返回所有结果。在您的定义中，q只有在p失败时才能返回其解析；这尤其意味着成功解析的列表将是左偏的。上面的语义驱动实现没有这样的偏见：即使 a 的左侧(<|>)解析，右侧也将被允许讲述它的胜利。而且我认为这很自然：这意味着使用此接口构建的解析器将返回所有成功的解析。

实际上有什么区别？那么上面的语义定义更健壮，你提出的定义更有效。让我们先看看“更健壮”是什么意思。

考虑一个总是只使用一个字符的解析器（它返回的内容对于本次讨论并不重要）：

oneChar = Parser (\s -> case s of
    c:cs -> [((),cs)]
    _    -> [])

...以及一个始终成功且不消耗任何字符的解析器：

epsilon = Parser (\s -> [((),s)]) -- you might recognize this as "pure ()"

现在，如果我们像这样编写一个一两个字符的解析器会发生什么？

oneOrTwo = (oneChar <|> epsilon) <* oneChar

考虑使用oneOrTwo来解析"a". 根据您对 的定义(<|>)，第一部分 ,oneChar <|> epsilon尝试使用oneChar来解析一点，它成功了，因此永远不会运行epsilon，我们得到一个解析列表，如[((),"")]. 但是现在第二部分失败了：没有一个字符可以解析了。根据我对 的定义(<|>)，第一部分改为尝试两个解析，它同时运行oneChar和epsilon，我们得到一个解析列表，如[((),""),((),"a")]. 现在第二部分在该列表的第一个元素上失败，但在第二个元素上成功，并且整体解析成功。

另一方面，由于两个原因，您的定义可能更有效：首先，它可以更快地丢弃输入的早期部分（导致与垃圾收集更好的交互），其次，它可以修剪大部分回溯搜索空间（导致更少的搜索周期）。

这种权衡是众所周知的。例如，Parsec通过try组合器提供了你的交替类型（如果它曾经消耗任何输入，它会提交它的第一个参数）和我的类型（它会回溯） 。

于 2012-07-27T19:02:02.037 回答