Parse function not defined

Question

I am following the following paper and struggling to implement. The code does not mention the implementation of parse or ord. I tried to do it without implementing Prelude, but this is my next exercise, hence the comment at the top.

My code is as follows, copying directly from the Paper:

{- {-# 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)}

The problem is that the parse function is not defined anywhere, and when trying to compile using GHCi, I get the following error:

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.

I have tried to get the code from the paper to compile but had no luck. I think I need to define the parse and ord functions myself, but I'm not sure if I am have just implemented the code incorrectly -- I am almost certain I haven't.

Answer 1

parse is in fact defined in the paper on page 438. It's also guessable from the type signature GHC tells you it should have.

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

ord and isSpace are in Data.Char.

Other notes: Please avoid reimplementing language primitives (like Char) in real code. By convention, anything with a # in its name is to be considered "low-level" and an implementation detail, can't even be named without the MagicHash extension, and should not be touched in >90% of cases. NoImplicitPrelude is not useful except in the very rare case that you want to avoid importing instances from Prelude. Otherwise a simple (and standard!) import Prelude() causes all names from Prelude to be out of scope. You add individual names to the import list instead of reimplementing stuff that you really shouldn't. Also, * as a kind is obsolete and should be replaced with Data.Kind.Type