Haskell解析器，Monad和MonadPlus

Question

    module Parser where

import           Control.Monad (MonadPlus, mplus, mzero)
import           Tagger        (Tag, Token)


newtype Parser a = Parser ([(Token, Tag)] -> [(a, [(Token, Tag)])])

parse :: Parser a -> [(Token, Tag)] -> [(a, [(Token, Tag)])]
parse (Parser p) = p

instance Functor Parser where
    fmap f p = do
        result <- p
        return (f result)

instance Monad Parser where
    return a = Parser (\cs -> [(a,cs)])
    p >>= f = Parser (\cs -> concat [parse (f a) cs' | (a,cs') <- parse p cs])

instance MonadPlus Parser where 
    p `mplus` q = Parser (\cs -> parse p cs ++ parse q cs)
    mzero = Parser (const [])

{-

这是我的解析器代码。显然，我用了“老方法”，无法使用新方法使其正常工作。你能告诉我需要修复哪些问题才能使其正常工作吗？我阅读了这篇文章（https://wiki.haskell.org/Functor-Applicative-Monad_Proposal），并尝试更改我的代码，但我认为我在这里做错了什么。

我得到的编译错误：

Parser.hs:56:10:
    No instance for (Applicative Parser)
      arising from the superclasses of an instance declaration
    In the instance declaration for ‘Monad Parser’

Parser.hs:60:10:
    No instance for (GHC.Base.Alternative Parser)
      arising from the superclasses of an instance declaration
    In the instance declaration for ‘MonadPlus Parser’

编辑 //

当前的代码：

module Parser where

import           Control.Applicative
import           Control.Monad (mplus, mzero, liftM, ap)
import           Tagger        (Tag, Token)

-- type Token = String 
-- type Tag = String

newtype Parser a = Parser ([(Token, Tag)] -> [(a, [(Token, Tag)])])

parse :: Parser a -> [(Token, Tag)] -> [(a, [(Token, Tag)])]
parse (Parser p) = p

instance Functor Parser where
    fmap = liftM

instance Applicative Parser where
    pure a = Parser (\cs -> [(a,cs)])
    (<*>) = ap

instance Monad Parser where
    p >>= f = Parser (\cs -> concat [parse (f a) cs' | (a,cs') <- parse p cs])

instance MonadPlus Parser where --64
    p `mplus` q = Parser (\cs -> parse p cs ++ parse q cs)
    mzero = Parser (const [])

instance Alternative Parser where
    (<|>) = mplus
    empty = mzero

(+++) :: Parser a -> Parser a -> Parser a
p +++ q = Parser (\cs -> case parse (p `mplus` q) cs of
                           [] -> []
                           (x:_) -> [x])

错误：

Parser.hs:64:10:
Not in scope: type constructor or class ‘MonadPlus’

- katyp

---

您可以按照迁移指南进行操作：https://ghc.haskell.org/trac/ghc/wiki/Migration/7.10 - zakyggaps

我猜你还需要手动实例化 Applicative（这将非常容易）和 Alternative。 - Bartek Banachewicz

谢谢建议！@zakyggaps 我尝试按照你链接中的说明操作，但不幸的是现在出现了新错误，我不确定应该如何解决。我可能还需要改变一些东西吗？ - katyp

在你最初的“>>=”定义中，你有参数“p”和“f”。但是在你的“*>”定义中，你不再有这些参数了。如果你用“p > f”替换“(>)”，会发生什么？在你新的“>>=”定义中也存在类似的混淆。你确定你理解运算符语法的工作原理吗？ - Paul Johnson

@PaulJohnson 我已经替换了它，现在它不再抱怨它们了，谢谢！现在它只抱怨 a (56), p (66) 和 q (66)。我对 Haskell 还非常非常新，并且没有使用过它，所以有时仍然会对很多事情感到困惑。我正在尽力学习，但这非常不同。 - katyp

@katyp 好的，现在尝试将相同的更改应用到其他函数上。考虑“纯”和“返回”：它们实际上是同一件事情。 - Paul Johnson

Answer 1

你可以按照 迁移指南 进行操作。它很简单明了：将 return 的定义移动到 pure 中，添加 <*> 的样板定义，并从 monad 实例中删除 return。

instance Functor Parser where
    fmap = liftM

instance Applicative Parser where
    pure a = Parser (\cs -> [(a,cs)])
    (<*>) = ap

instance Monad Parser where
    p >>= f = Parser (\cs -> concat [parse (f a) cs' | (a,cs') <- parse p cs])

对于Alternative，这只是样板文件而已，没有别的东西：

instance Alternative Parser where 
    (<|>) = mplus 
    empty = mzero

整体的工作代码如下：

module Parser where

import           Control.Monad
import           Tagger        (Tag, Token)
import           Control.Applicative

newtype Parser a = Parser ([(Token, Tag)] -> [(a, [(Token, Tag)])])

parse :: Parser a -> [(Token, Tag)] -> [(a, [(Token, Tag)])]
parse (Parser p) = p

instance Functor Parser where
    fmap = liftM

instance Applicative Parser where
    pure a = Parser (\cs -> [(a,cs)])
    (<*>) = ap

instance Monad Parser where
    p >>= f = Parser (\cs -> concat [parse (f a) cs' | (a,cs') <- parse p cs])

instance MonadPlus Parser where
    p `mplus` q = Parser (\cs -> parse p cs ++ parse q cs)
    mzero = Parser (const [])

instance Alternative Parser where
    (<|>) = mplus
    empty = mzero

- zakyggaps

---

@PaulJohnson 抱歉，已修复。 - zakyggaps

这个修复只会出现错误“Parser.hs:56:29: Not in scope: ‘a’”，所以纯函数= Parser (\cs -> [(a,cs)])或者其他什么地方似乎有问题？我对此非常陌生，不确定问题的根源在哪里。 - katyp

@zakyggaps 非常感谢您的帮助！现在ghci仍然为MonadPlus给出编译错误。我编辑了原始帖子。 - katyp

@katyp 你忘记从 Control.Monad 导入它了。现在列表中没有它：import Control.Monad (mplus, mzero, liftM, ap)。 - zakyggaps

@zakyggaps 你说得对！问题已经解决了，现在我不再遇到错误了 :) 非常感谢你！ - katyp