Haskell类型错误

Question

考虑以下Haskell代码片段：

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

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

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

 parse :: Parser a -> String -> [(a, String)]
 parse p inp = p inp

 pseq :: Parser (Char, Char)
 pseq = do x <- item
           item
           y <- item
           ret (x, y)

 ac = parse pseq "abcdef"

尝试在Hugs中运行上述代码（版本为2006年9月），我收到以下错误信息：

Type error in explicitly typed binding
*** Term           : pseq
*** Type           : [Char] -> [(([(Char,[Char])],[(Char,[Char])]),[Char])]
*** Does not match : Parser (Char,Char)

当我删除“pseq”的类型声明时，会出现以下错误消息：

Unresolved top-level overloading
*** Binding             : pseq
*** Outstanding context : Monad ((->) [Char])

- reprogrammer

Answer 1

问题在于您试图使用do符号来操作Parser，但它并不完全是一个Monad。虽然r ->有一个Monad实例，但这使得->右侧的类型成为Monad的“元素”类型，而在这里，您希望元素类型是[(a,String)]中的a。您需要将Parser的定义作为newtype，并编写自定义的Monad实例（或将其组合成现有的monad/transformer，如ListT和StateT）。

- GS - Apologise to Monica

Answer 2

使解析器成为单子很容易，我认为在这里使用ListT或StateT可能过于复杂。

newtype Parser a = Parser (String -> [(a, String)])
    -- make this a distinct type
    -- now the function is "wrapped", though at no run-time cost

instance Monad Parser where
    return = ret    -- you already had it defined
    (>>=) = bind    -- added below
    -- this instance makes Parser a Moand, and lets it work with do notation

item :: Parser Char
item = Parser $ \ inp -> case inp of
                         [] -> []
                         (x:xs) -> [(x, xs)]
    -- need to "wrap" up the function as a Parser value

ret :: a -> Parser a
ret v = Parser $ \ inp -> [(v, inp)]
    -- need to "wrap" up the function as a Parser value

bind :: Parser a -> (a -> Parser b) -> Parser b
bind p f = Parser $ \ s -> case parse p s of
                           [] -> []
                           [(a, s')] -> parse (f a) s'
    -- the only function you were missing
    -- it is worth making sure you understand how it works

parse :: Parser a -> String -> [(a, String)]
parse (Parser p) inp = p inp
    -- needs to "unwrap" the newtype here

pseq :: Parser (Char, Char)
pseq = do x <- item
          item
          y <- item
          ret (x, y)

ac = parse pseq "abcdef"
    -- you probably meant pseq here, not seq

最后，你使用了返回类型[(a, String)]，以便指示无法解析的内容。但是该列表始终只有零个或一个项目。在这种情况下，您应该研究Maybe和Either类型，这可能更清晰明了。

- MtnViewMark