Haskell 解析器排序不起作用

Question

我去过learning Haskell最近。我尝试了书中下面的代码。但它并没有按预期工作。

p :: Parser (Char, Char)
    p = do x ← item
           item
           y ← item
           return (x , y)

书上说:

>parse p "abcdef"
[ ((’a’, ’c’), "def") ]

但是当我尝试时，结果是这样的:

*Main> pp "abcde"
[(([('a',"bcde")],[('a',"bcde")]),"abcde")]

---

排序运算符 (+>>=) 有效，但 do 表示法无效。为什么？

这是完整的代码。 GHCi 8.2.2

{-# OPTIONS_GHC -fno-warn-tabs #-}
type Parser a = String -> [(a, String)]

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


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


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


(+>>=) :: Parser a -> (a -> Parser b) -> Parser b
p +>>= f = \inp -> case parse p inp of
                    [] -> []
                    [(v, out)] -> parse (f v) out


p :: Parser (Char, Char)
p = item +>>= \x -> 
    item +>>= \_ ->
    item +>>= \y ->
    return' (x,y)


pp = do  x <- item
         item
         y <- item
         return' (x,y)  --return (x,y) this won't work either

---

输出:

*Main> p "abcde"
[(('a','c'),"de")]
*Main> pp "abcde"
[(([('a',"bcde")],[('a',"bcde")]),"abcde")]

我哪里出错了？如何用 do 表示法编写函数 p？

Answer 1

对于编译器来说，您的 Parser 类型如下所示(不是实际的 Haskell 语法):

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

因此，当您将 >>= (在 do 语法调用的引擎盖下)与此类操作一起使用时，它会采用签名

(>>=) :: ______m______ α -> (α -> ______m______ β) -> ______m______ β
(>>=) :: ((->) String) α -> (α -> ((->) String) β) -> ((->) String) β

即

(>>=) :: Parser a -> ([(a,String)] -> Parser b) -> Parser b

这与 (+>>=) 的签名不同 - 你真正想要的只是

(>>=)  :: __m___ a -> (a -> __m___ b) -> __m___ b
(+>>=) :: Parser a -> (a -> Parser b) -> Parser b

IOW，使用 >>= 你实际上并没有使用 Parser 作为 monad，而是 Parser 将你重定向到另一个 monad (该函数又名 Reader monad)。

要真正让 Parser 作为 monad 本身运行，并具有 +>>= 的语义，您必须让编译器将其识别为实际的不可分解实体。这意味着，您需要 newtype 而不是 type:

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

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


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


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


(+>>=) :: Parser a -> (a -> Parser b) -> Parser b
Parser p +>>= f = Parser $ \inp -> case parse p inp of
                    [] -> []
                    [(v, out)] -> parse (f v) out


p :: Parser (Char, Char)
p = item +>>= \x -> 
    item +>>= \_ ->
    item +>>= \y ->
    return' (x,y)


pp = do  x <- item
         item
         y <- item
         return' (x,y)

这里，pp 现在将给出一个明确的编译错误 Could not derduc Monad Parser from a use of do notation...。这表明编译器实际上正在尝试做正确的事情，但要使其真正起作用，您仍然需要写出实例声明。这很容易，因为运算符(operator)已经在那里:

instance Functor Parser where
  fmap = liftM  -- makes use of the `Monad` instance below
instance Applicative Parser where
  pure = return'
  (<*>) = ap
instance Monad Parser where
  return = return'
  (>>=) = (+>>=)

不过，这有点向后定义 - 您正在使用最强大和最特殊的接口(interface)(monad)来定义仿函数类型类的更基本操作。首选实例化路径是自顶向下:

newtype Parser a = Parser (String -> [(a,String)]
  deriving (Functor)

instance Applicative Parser where
  pure v = Parser $ \inp -> [(v,inp)]
  Parser pf <*> Parser px = Parser $
     \inp -> case pf inp of
        [] -> []
        [(f,out)] -> f <$> px out

instance Monad Parser where
  return = pure
  Parser p >>= f = ...