为什么我会在这个解析器序列中遇到类型错误（Erik Meijer 的第 8 讲）？

Question

我正在观看 Erik Meijer 的 函数式编程基础知识 讲座系列（带有 Graham Hutton 的幻灯片）。

在 lecture 8 (on functional parsers), after defining the Parser a type, introducing a few parsing primitives (including item and return, which I named return'), Erik gives a 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 来使用。错误发生在第 15 行，这是您对 return':

的调用

return' (x, y)

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

您拥有的 do 块正在将 monad 实例用于 String -> b 类型的函数；这样做是通过将所有函数的输入 (String) 串起来，将它们组合成更大的 String -> b 函数。像 x <- item 这样的行允许您从 String -> b 函数中获取 b 元素，同时维护所有管道以传递 String 参数。不幸的是，item 是 Parser Char，这意味着 b 实际上是 [(Char, String)] 而不仅仅是 Char.

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

要完成这项工作，您必须有一些方法来处理这个额外的结构。但是，由于我没有听过课程或看过讲座，所以我不知道它是什么。您可以定义 您自己的 monad 实例而不是依赖函数的内置实例，但是您可能还没有深入了解 class 来自己做这个，或者Meijer 可能正在使用非标准库来避免此问题，在这种情况下，您需要确保您的设置符合 class 的预期。

Answer 2

问题是您定义的 p 中的 do 表示法没有使用您希望它使用的 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 表示法，您应该为 Parser 创建一个 newtype 或 data 声明，这样您就可以定义绑定运算符 (>> =) 有效，例如：

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

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

这是一个很好的博客 post，介绍如何使用 newtype 定义解析器 monad 实例：(link)

为什么我会在这个解析器序列中遇到类型错误（Erik Meijer 的第 8 讲）？

Why am I getting a type error in this sequence of parsers (lecture 8 by Erik Meijer)?

monads

parsing

haskell

types