parsing - 为什么我在这个解析器序列中出现类型错误(Erik Meijer 的第 8 课)？

Question

我正在观看 Erik Meijer 的 Functional Programming Fundamentals 系列讲座(附有 Graham Hutton 的幻灯片)。

在 lecture 8 (on functional parsers) , 在定义 Parser a 之后类型，引入了一些解析原语(包括 item 和 return ，我命名为 return' )，Erik 给出了一个 simple example他的解析器如何使用 do 语法组合成一个序列:

type Parser a = String -> [(a,String)]

item :: Parser Char                                                  
item = \inp -> case inp of                                                   
                 []     -> []                                             
                 (x:xs) -> [(x,xs)]

return' :: a -> Parser a                                                   
return' v = \inp -> [(v,inp)]

p :: Parser (Char,Char)
p = do x <- item
       item
       y <- item
       return' (x,y)

但是，当我尝试在 GHCi 中加载它时，出现以下类型错误，这是我没想到且不明白的:

Couldn't match type ‘[(Char, String)]’ with ‘Char’
Expected type: String -> [((Char, Char), String)]
  Actual type: Parser ([(Char, String)], [(Char, String)])
In a stmt of a 'do' block: return' (x, y)
In the expression:
  do { x <- item;
       item;
       y <- item;
       return' (x, y) }
Failed, modules loaded: none.

我究竟做错了什么？

Answer 1

这个错误信息有点令人困惑，因为 GHC 解压了你的 Parser输入其定义 String -> [(a, String)] .如果我们撤消此转换，它将开始变得更有意义:

Expected type: Parser (Char, Char)
  Actual type: Parser ([(Char, String)], [(Char, String)])

现在它开始变得更有意义了。看起来您将两次调用的结果带到 Parser Char (即 [(Char, String)] )然后像正常使用它们一样使用它们 Char s。错误发生在第 15 行，这是您对 return' 的调用:

return' (x, y)

这告诉我们 x和 y是两个有问题的结果。

您拥有的 do 块正在将 monad 实例用于 String -> b 类型的函数。 ;这样做是将它们组合成一个更大的函数 String -> b通过所有函数将输入( String )串起来。像 x <- item这样的线让您获得 b来自 String -> b 的元素功能，同时保持所有管道通过 String论证通过。不幸的是， item是 Parser Char ，这意味着 b实际上是 [(Char, String)]而不仅仅是 Char .

需要这个额外的返回结构才能正确解析。 String表示未用于解析 Char 的其余输入(或您正在解析的任何内容)并且整个事情都是一个列表，因为可以有多种可能的方法来有效地解析所有需要处理的输入部分。

为了让这个工作，你必须有一些方法来处理这个额外的结构。但是，由于我没有听过类(class)或看过讲座，所以我不知道它是什么。您可以定义自己的 monad 实例，而不是依赖于函数的内置实例，但是您可能对类的了解不够深入，无法自己执行此操作，或者 Meijer 可能使用非标准库来避免此问题，在这种情况下，您需要确保您的设置与类(class)期望的相符。