I’m currently working my way through this paper. The code I have developed so far is below:
-- {-# LANGUAGE NoImplicitPrelude #-}
module MonadicParsingInHaskell () where
import Data.Char
import GHC.Types
import GHC.Base (Monad)
import GHC.Base hiding (MonadPlus, (++), many)
import Data.List (concat)
import Prelude ()
newtype Parser a = Parser (String -> [(a,String)])
item :: Parser Char
item = Parser (\cs -> case cs of
"" -> []
(c:cs) -> [(c,cs)])
instance Monad Parser where
return a = Parser (\cs -> [(a,cs)])
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
instance MonadZero => MonadPlus m where
instance MonadZero m => Parser where
zero :: m a
instance MonadZero => Parser where
zero = Parser (\cs -> [])
class MonadZero m => MonadPlus m where
(++) :: m a -> m a -> m a
instance MonadZero Parser where
zero = Parser (\cs -> [])
instance MonadZero Parser where
zero = Parser (\cs -> [])
parse :: Parser a -> String -> [(a, String)]
parse (Parser p) = p
many :: Parser a -> Parser [a]
many p = many1 p +++ return []
many' :: Parser a -> Parser [a]
many' p = many p +++ return []
(+++) :: Parser a -> Parser a -> Parser a
p +++ q = Parser (\cs -> case parse (p ++ q) cs of
[] -> []
(x:xs) -> [x])
instance Monad Parser where
return a = Parser (\cs -> [(a,cs)])
p >>= f = Parser (\cs -> concat [parse (f a) cs' | (a, cs') <- parse p cs])
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)}
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 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
expr = term `chainl1` addop
addop :: Parser (Int -> Int -> Int)
addop = do {symb "+"; return (+)} +++ do {symb "-"; return (-)}
mulop :: Parser (Int -> Int -> Int)
mulop = do {symb "*"; return (*)} +++ do {symb "/"; return div}
term :: Parser Int
term = factor `chainl1` mulop
factor :: Parser Int
factor = digit +++ do {symb "("; n <- expr; symb ")"; return n}
digit :: Parser Int
digit = do {x <- token (sat isDigit); return (ord x - ord '0')}
But the error I get, which I am unable to solve and on lines 31 and 34, part of the
Instance Monad = m => Parser where
zero :: m a
And
instance MonadZero = Parser where
zero = Parser (\cs -> [])
The error message I get is as follows:
GHCi, version 9.4.8: https://www.haskell.org/ghc/ :? for help
[1 of 1] Compiling MonadicParsingInHaskell ( MonadicParsingInHaskell.hs, interpreted )
MonadicParsingInHaskell.hs:32:5: error:
The class method signature for ‘zero’ lacks an accompanying binding
Suggested fix:
Move the class method signature to the declaration site of ‘zero’.
|
32 | zero :: m a
| ^^^^
MonadicParsingInHaskell.hs:35:5: error:
‘zero’ is not a (visible) method of class ‘Parser’
|
35 | zero = Parser (\cs -> [])
The paper doesn’t mention this, as far as I can tell. So I’m not sure how to fix the error.
This has fixed one of my issues but the second issue is still occurring:
instance MonadZero => Parser where
zero = Parser (\cs -> [])
With the error being:
GHCi, version 9.4.8: https://www.haskell.org/ghc/ :? for help
[1 of 1] Compiling MonadicParsingInHaskell ( MonadicParsingInHaskell.hs, interpreted )
MonadicParsingInHaskell.hs:30:5: error:
‘zero’ is not a (visible) method of class ‘Parser’
|
30 | zero = Parser (\cs -> [])
I don’t understand, newtype is used for declaration of Parser but the error is saying:
'zero' is not a (visible) method of class ‘Parser’.
Does newtype create a class? I’m a bit confused at the moment. Any help would be appreciated.
That seems to of fixed that issue but now I have an error with instance Monad Parser. The code for the instance is as follows (copied from the paper):
instance Monad Parser where
return :: a -> Parser a
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])
And the error I am now getting is this:
GHCi, version 9.4.8: https://www.haskell.org/ghc/ :? for help
[1 of 1] Compiling MonadicParsingInHaskell ( MonadicParsingInHaskell.hs, interpreted )
MonadicParsingInHaskell.hs:22:57: error: parse error on input ‘|’
|
22 | p >>= f = Parser (\cs -> concat [parse (f a) cs` | (a,cs`) <- parse p cs])
| ^
Failed, no modules loaded.
The error seems to be coming from the following code:
instance Monad Parser where
return :: a -> Parser a
return a = Parser (\cs -> [(a,cs)]
(>>=) :: Parser a -> (a -> Parser b) -> Parser b
p >>= f = Parser (\cs -> concat [parse (f a) cs' | (a,c') <- parse p cs])
Making the changes you suggested the error is now
GHCi, version 9.4.8: https://www.haskell.org/ghc/ :? for help
[1 of 1] Compiling MonadicParsingInHaskell ( MonadicParsingInHaskell.hs, interpreted )
MonadicParsingInHaskell.hs:21:7: error:
parse error (possibly incorrect indentation or mismatched brackets)
|
21 | (>>=) :: Parser a -> (a -> Parser b) -> Parser b
| ^
Failed, no modules loaded.
That is correct, I did miss a closing parentheses.
But the program still won’t run in GHCi and the error now is saying the following:
GHCi, version 9.4.8: https://www.haskell.org/ghc/ :? for help
[1 of 1] Compiling MonadicParsingInHaskell ( MonadicParsingInHaskell.hs, interpreted )
MonadicParsingInHaskell.hs:12:10: error:
• No instance for (Applicative Parser)
arising from the superclasses of an instance declaration
• In the instance declaration for ‘Monad Parser’
|
12 | instance Monad Parser where
| ^^^^^^^^^^^^
MonadicParsingInHaskell.hs:45:40: error:
• No instance for (MonadPlus Parser) arising from a use of ‘++’
• In the first argument of ‘parse’, namely ‘(p ++ q)’
In the expression: parse (p ++ q) cs
In the expression:
case parse (p ++ q) cs of
[] -> []
(x : xs) -> [x]
|
45 | p +++ q = Parser (\cs -> case parse (p ++ q) cs of
| ^^
Failed, no modules loaded.
I think the error is coming from this instance:
instance Monad Parser where
return :: a -> Parser a
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])
In particular I think it might be this line
"No instance for (Applicative Parser)"
that is causing the errors. Though I don't exactly know what it means.
The monad class was changed a bit after that paper was written. You now also need to implement instances for Functor and Applicative for every monad you want to define. But you can do that quite easily:
import Control.Monad (liftM, ap)
instance Functor Parser where
fmap = liftM
instance Applicative Parser where
pure a = Parser (\cs -> [(a,cs)]) -- same as return
(<*>) = ap
And I see a second error message that you are missing a MonadPlus Parser instance, which can also be found in the paper:
instance MonadPlus Parser where
p ++ q = Parser (\cs -> parse p cs ++ parse q cs)
Okay. Having done all you have mentioned I am left with the finally last error message. The error is:
GHCi, version 9.4.8: https://www.haskell.org/ghc/ :? for help
[1 of 1] Compiling MonadicParsingInHaskell ( MonadicParsingInHaskell.hs, interpreted )
MonadicParsingInHaskell.hs:39:38: error:
• No instance for (MonadPlus []) arising from a use of ‘++’
• In the expression: parse p cs ++ parse q cs
In the first argument of ‘Parser’, namely
‘(\ cs -> parse p cs ++ parse q cs)’
In the expression: Parser (\ cs -> parse p cs ++ parse q cs)
|
39 | p ++ q = Parser (\cs -> parse p cs ++ parse q cs)
| ^^
Failed, no modules loaded.
It seems to have something to do with the ++ operator in the instance
instance MonadPlus Parser where
p ++ q = Parser (\cs -> parse p cs ++ parse q cs)
GHCi, version 9.4.8: https://www.haskell.org/ghc/ :? for help
[1 of 1] Compiling MonadicParsingInHaskell ( MonadicParsingInHaskell.hs, interpreted )
MonadicParsingInHaskell.hs:18:10: error:
• No instance for (MonadZero [])
arising from the superclasses of an instance declaration
• In the instance declaration for ‘MonadPlus []’
|
18 | instance MonadPlus [] where
| ^^^^^^^^^^^^
Failed, no modules loaded.
Finally! It works! There is a warning though, do you know what it means?
GHCi, version 9.4.8: https://www.haskell.org/ghc/ :? for help
[1 of 1] Compiling MonadicParsingInHaskell ( MonadicParsingInHaskell.hs, interpreted )
MonadicParsingInHaskell.hs:34:7: warning: [-Wnoncanonical-monad-instances]
Noncanonical ‘return’ definition detected
in the instance declaration for ‘Monad Parser’.
‘return’ will eventually be removed in favour of ‘pure’
Either remove definition for ‘return’ (recommended) or define as ‘return = pure’
See also: https://gitlab.haskell.org/ghc/ghc/-/wikis/proposal/monad-of-no-return
|
34 | return a = Parser (\cs -> [(a,cs)])
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Ok, one module loaded.
Because for Now Applicative is the super class of Monad and the ‘return’ in Monad does the same thing with ‘pure’ in Applicative . That means : There is already a definition of ‘pure’ in Applicative, which can also be seen as the definition of ‘return’ in monad. ’return’ should just be an alias for ‘pure’ .
As for why there is already ‘pure’ in Applicative but still a ‘return’ in Monad, this is a historical legacy issue:
Applicative was introduced later, so previously Applicative was not a superclass of Monad .
In the definition of return in your monad instance, follow the advice in the error message, namely: " Either remove definition for ‘return’ (recommended) or define as ‘return = pure’"
By the way, once it’s working, I recommend going back through this thread and looking at each of the errors. The way Haskell prints out errors in not always clear, I agree, but if you look, you’ll see that for most of your errors, the solution is actually clear (once you know how to read it) from the error message. E.g. if it says “parse error”, there’s just a syntax problem (this will be easier to spot if you’re using VSCode or similar, where there will be a visual cue). If the error is “no instance for…”, that means that a function is being called which requires its arguments to have an instance of a class that they do not presently have.
Yeah, I’ll definitely go through the comments and see what errors there are and what they probably should have said. Thanks for the explanation, I’m still trying to wrap my head around Monads, Applicatives and Functors.