实现Haskell单子解析器遇parse/ord未定义等编译错误求助

参考一篇单子解析相关论文实现代码时遇到编译错误，论文未提及parse、ord等函数的实现，尝试不依赖Prelude（顶部注释为后续练习预留），直接复制论文代码如下：

{- {-# LANGUAGE NoImplicitPrelude #-}

type String :: *
type String = [ Char ]

type Char :: *
data Char = GHC.Types.C# GHC.Prim.Char#
-}

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

item :: Parser Char
item = Parser (\cs -> case cs of
    ""     -> []
    (c:cs) -> [(c,cs)])

class Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b

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

p :: Parser (Char,Char)
p  = do {c <- item; item; d <- item; Main.return (c,d)}

class Main.Monad m => MonadZero m where
      zero :: m a

class MonadZero m => MonadPlus m where
    (++) :: m a -> m a -> m a

instance MonadZero Parser where
      zero :: Parser a
      zero   = Parser (\cs -> [])

instance MonadPlus Parser where
      p ++ q = Parser (\cs -> parse p cs Main.++ parse q cs)

(+++)  :: Parser a -> Parser a -> Parser a
p +++ q = Parser (\cs -> case parse (p Main.++ q) cs of
                               []     -> []
                               (x:xs) -> [x])

sat  :: (Char -> Bool) -> Parser Char
sat p = do {c <- item; if p c then Main.return c else zero}

char :: Char -> Parser Char
char c = sat (c ==)

string       :: String -> Parser String
string ""     = Main.return ""
string (c:cs) = do {char c; string cs; Main.return (c:cs)}

many   :: Parser a -> Parser [a]
many p  = many1 p +++ Main.return []

many1  :: Parser a -> Parser [a]
many1 p = do {a <- p; as <- many p; Main.return (a:as)}

sepby         :: Parser a -> Parser b -> Parser [a]
p `sepby` sep  = (p `sepby1` sep) +++ Main.return []

sepby1 :: Parser a -> Parser b -> Parser [a] 
p `sepby1` sep = do a <-p
                    as <- many (do {sep; p})
                    Main.return (a:as)

chainl :: Parser a -> Parser (a -> a -> a) -> a -> Parser a 
chainl p op a = (p `chainl1` op) +++ Main.return a

chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
p `chainl1` op = do {a <- p; rest a}
                    where
                       rest a = (do f <- op
                                    b <- p
                                    rest (f a b))
                                +++ Main.return a

space :: Parser String
space = many (sat isSpace)

token  :: Parser a -> Parser a
token p = do {a <- p; space; Main.return a}

symb :: String -> Parser String
symb cs = token (string cs)

apply  :: Parser a -> String -> [(a,String)]
apply p = parse (do {space; p})

expr  :: Parser Int
addop :: Parser (Int -> Int -> Int)
mulop :: Parser (Int -> Int -> Int)

expr = term `chainl1` addop
term = factor `chainl1` mulop
factor = digit +++ do {symb "("; n <- expr; symb ")"; Main.return n}
digit = do {x <- token (sat isDigit); Main.return (ord x - ord '0')}

addop = do {symb "+"; Main.return (+)} +++ do {symb "-"; Main.return (-)}
mulop = do {symb "*"; Main.return (*)} +++ do {symb "/"; Main.return (div)}

使用GHCi 9.4.8编译时出现如下错误：

GHCi, version 9.4.8: https://www.haskell.org/ghc/  :? for help
[1 of 2] Compiling Main             ( MonadicParsingInHaskell.hs, interpreted )

MonadicParsingInHaskell.hs:24:41: error:
    Variable not in scope: parse :: Parser b -> t0 -> [(b, String)]
   |
24 |       p >>= f  = Parser (\cs -> concat [parse (f a) cs' |
   |                                         ^^^^^

MonadicParsingInHaskell.hs:25:47: error:
    Variable not in scope: parse :: Parser a -> String -> [(a, t0)]
   |
25 |                                    (a,cs') <- parse p cs])
   |                                               ^^^^^

MonadicParsingInHaskell.hs:41:31: error:
    Variable not in scope: parse :: Parser a -> String -> [(a, String)]
   |
41 |       p ++ q = Parser (\cs -> parse p cs Main.++ parse q cs)
   |                               ^^^^^

MonadicParsingInHaskell.hs:41:50: error:
    Variable not in scope: parse :: Parser a -> String -> [(a, String)]
   |
41 |       p ++ q = Parser (\cs -> parse p cs Main.++ parse q cs)
   |                                                  ^^^^^

MonadicParsingInHaskell.hs:44:31: error:
    Variable not in scope: parse :: Parser a -> String -> [(a, String)]
   |
44 | p +++ q = Parser (\cs -> case parse (p Main.++ q) cs of
   |                               ^^^^^

MonadicParsingInHaskell.hs:84:19: error:
    Variable not in scope: isSpace :: Char -> Bool
    Suggested fix: Perhaps use ‘space’ (line 84)
   |
84 | space = many (sat isSpace)
   |                   ^^^^^^^

MonadicParsingInHaskell.hs:93:11: error:
    Variable not in scope: parse :: Parser a -> String -> [(a, String)]
   |
93 | apply p = parse (do {space; p})
   |           ^^^^^

MonadicParsingInHaskell.hs:102:29: error:
    Variable not in scope: isDigit :: Char -> Bool
    |
102 | digit = do {x <- token (sat isDigit); Main.return (ord x - ord '0')}
    |                             ^^^^^^^

MonadicParsingInHaskell.hs:102:52: error:
    Variable not in scope: ord :: Char -> b
    Suggested fix:
      Perhaps use one of these:
        ‘or’ (imported from Prelude), ‘odd’ (imported from Prelude)
   |
102 | digit = do {x <- token (sat isDigit); Main.return (ord x - ord '0')}
    |                                                    ^^^

MonadicParsingInHaskell.hs:102:60: error:
    Variable not in scope: ord :: Char -> b
    Suggested fix:
      Perhaps use one of these:
        ‘or’ (imported from Prelude), ‘odd’ (imported from Prelude)
   |
102 | digit = do {x <- token (sat isDigit); Main.return (ord x - ord '0')}
    |                                                            ^^^
Failed, no modules loaded.

推测需要自行定义parse和ord函数，但不确定是否存在其他实现错误，请求解决编译问题。

核心问题修复点 #

1. 实现parse函数
   Parser是newtype包装器，需要一个函数提取内部的解析逻辑：

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

2. 解决MonadPlus中运算符命名冲突
   论文里用(++)作为MonadPlus的组合运算符，但Prelude里已有列表的(++)，会导致冲突。将MonadPlus的运算符改为(<++>)，避免命名冲突：

   class MonadZero m => MonadPlus m where
       (<++>) :: m a -> m a -> m a
   
   instance MonadPlus Parser where
       p <++> q = Parser (\cs -> parse p cs ++ parse q cs)
   
   (+++)  :: Parser a -> Parser a -> Parser a
   p +++ q = Parser (\cs -> case parse (p <++> q) cs of
                                  []     -> []
                                  (x:xs) -> [x])
   

3. 补充依赖函数
   如果要继续使用NoImplicitPrelude，需要手动导入isSpace、isDigit、ord，最简单的方式是从Data.Char导入：

   {-# LANGUAGE NoImplicitPrelude #-}
   import qualified Data.Char as C
   

   然后将代码中的isSpace改为C.isSpace，isDigit改为C.isDigit，ord改为C.ord。

   若暂时不需要严格禁用Prelude，可去掉NoImplicitPrelude注释，直接使用Prelude中的这些函数。

4. 简化Main.return引用
   因为已经在当前模块定义了Monad实例，直接用return即可，无需Main.return。

修改后的完整代码 #

{-# LANGUAGE NoImplicitPrelude #-}
import qualified Data.Char as C

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

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

item :: Parser Char
item = Parser (\cs -> case cs of
    ""     -> []
    (c:cs) -> [(c,cs)])

class Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b

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

p :: Parser (Char,Char)
p  = do {c <- item; item; d <- item; return (c,d)}

class Monad m => MonadZero m where
      zero :: m a

class MonadZero m => MonadPlus m where
    (<++>) :: m a -> m a -> m a

instance MonadZero Parser where
      zero :: Parser a
      zero   = Parser (\cs -> [])

instance MonadPlus Parser where
      p <++> q = Parser (\cs -> parse p cs ++ parse q cs)

(+++)  :: Parser a -> Parser a -> Parser a
p +++ q = Parser (\cs -> case parse (p <++> q) cs of
                               []     -> []
                               (x:xs) -> [x])

sat  :: (Char -> Bool) -> Parser Char
sat p = do {c <- item; if p c then return c else zero}

char :: Char -> Parser Char
char c = sat (c ==)

string       :: String -> Parser String
string ""     = return ""
string (c:cs) = do {char c; string cs; return (c:cs)}

many   :: Parser a -> Parser [a]
many p  = many1 p +++ return []

many1  :: Parser a -> Parser [a]
many1 p = do {a <- p; as <- many p; return (a:as)}

sepby         :: Parser a -> Parser b -> Parser [a]
p `sepby` sep  = (p `sepby1` sep) +++ return []

sepby1 :: Parser a -> Parser b -> Parser [a] 
p `sepby1` sep = do a <-p
                    as <- many (do {sep; p})
                    return (a:as)

chainl :: Parser a -> Parser (a -> a -> a) -> a -> Parser a 
chainl p op a = (p `chainl1` op) +++ return a

chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
p `chainl1` op = do {a <- p; rest a}
                    where
                       rest a = (do f <- op
                                    b <- p
                                    rest (f a b))
                                +++ return a

space :: Parser String
space = many (sat C.isSpace)

token  :: Parser a -> Parser a
token p = do {a <- p; space; return a}

symb :: String -> Parser String
symb cs = token (string cs)

apply  :: Parser a -> String -> [(a,String)]
apply p = parse (do {space; p})

expr  :: Parser Int
addop :: Parser (Int -> Int -> Int)
mulop :: Parser (Int -> Int -> Int)

expr = term `chainl1` addop
term = factor `chainl1` mulop
factor = digit +++ do {symb "("; n <- expr; symb ")"; return n}
digit = do {x <- token (sat C.isDigit); return (C.ord x - C.ord '0')}

addop = do {symb "+"; return (+)} +++ do {symb "-"; return (-)}
mulop = do {symb "*"; return (*)} +++ do {symb "/"; return (div)}

验证编译 #

将上述代码保存为MonadicParsingInHaskell.hs，在GHCi中加载：

ghci MonadicParsingInHaskell.hs

可以正常编译，测试示例：

apply expr "1 + 2 * 3"
-- 应该返回 [(7,"")]

内容的提问来源于stack exchange，提问作者Luke McCartney