为什么我在这个解析器序列中遇到类型错误(Erik Meijer的讲座8)？

Question

我正在观看Erik Meijer撰写的" 功能编程基础"系列讲座(Graham Hutton的幻灯片).

在第8讲(关于函数解析器)中,在定义了Parser a类型之后,引入了一些解析原语(包括item和return我命名的return'),Erik给出了一个简单的例子,说明如何使用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的一样.错误发生在第15行,这是您致电return':

return' (x, y)

这就告诉我们,x和y是两个问题的结果.

你所拥有的do块是使用monad实例来实现该类型的功能String -> b; 这样做是String -> b通过将input(String)串行通过所有函数将它们组合成更大的函数.类似的行x <- item允许您b从String -> b函数中获取元素,同时保持所有管道传递String参数.不幸的是,item是一个Parser Char,这意味着b它实际上是一个[(Char, String)]而不仅仅是一个Char.

需要此额外返回的结构才能正确解析.该String代表不消耗解析输入的其余部分Char(或任何你解析),整个事情是一个列表,因为可以有有效的已输入所有需要进行处理的解析一部分多种可能的方式.

为了使这项工作,你必须有一些方法来处理这个额外的结构.但是,由于我没有按照课程或观看讲座,我不知道它是什么.您可以定义自己的 monad实例,而不是依赖于函数的内置实例,但是您可能没有足够深入到自己的类中,或者Meijer可能正在使用非标准库来避免此问题,在这种情况下,您需要确保您的设置与类期望的匹配.

Answer 2

问题是您定义中的 do 符号p没有使用您希望它使用的 monad。

我可能是错的，但看起来p正在使用 Reader monad 的一个版本。

如果您使用此定义，您将看到x和y不是Char值，而是类型[(Char,String)]：

import Debug.Trace

p :: Parser (Char,Char)
p = do x <- item
       y <- item
       let foo = trace ("x = " ++ show x) 'a'
           bar = trace ("y = " ++ show y) 'b'
       return' (foo,bar)

test = p "qwe"

如果您想使用do符号，您应该创建一个newtypeordata声明，Parser以便您可以定义绑定运算符 (>>=) 的工作方式，例如：

newtype Parser a = Parser { parse :: String -> [ (a,String) ] }

instance Monad Parser where
    return   = Parser . return'
    (>>=)    = ...

这是一篇关于如何使用定义解析器 monad 实例的好博客文章newtype：（链接）