# Monadic Parsing in Haskell
**URL:** https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596
**Category:** Learn
**Created:** [January 19, 2024, 1:05pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596 "2024-01-19T13:05:05Z")
**Posts on this page:** 20
**Page:** 1
### Author:  [@lukemccartney](https://discourse.haskell.org/u/lukemccartney)
#### Post date: [January 19, 2024, 1:05pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/1 "2024-01-19T13:05:06Z")
I’m currently working my way through [this paper](https://www.cmi.ac.in/%7Espsuresh/teaching/prgh15/papers/monadic-parsing.pdf). The code I have developed so far is below:
```haskell
-- {-# 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
```haskell
Instance Monad = m => Parser where
zero :: m a
```
And
```haskell
instance MonadZero = Parser where
zero = Parser (\cs -> [])
```
The error message I get is as follows:
```haskell
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.
Thanks in advance
---
### Author:  [@jaror](https://discourse.haskell.org/u/jaror)
#### Post date: [January 19, 2024, 1:09pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/2 "2024-01-19T13:09:06Z")
You’ve mixed up a bunch of things in your definition. The paper has this:
```haskell
class Monad m => MonadZero m where
zero :: m a
```
Whereas you wrote:
```haskell
instance MonadZero m => Parser where
zero :: m a
```
---
### Author:  [@lukemccartney](https://discourse.haskell.org/u/lukemccartney)
#### Post date: [January 19, 2024, 4:47pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/3 "2024-01-19T16:47:17Z")
This has fixed one of my issues but the second issue is still occurring:
```haskell
instance MonadZero => Parser where
zero = Parser (\cs -> [])
```
With the error being:
```haskell
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:
```haskell
'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.
---
### Author:  [@jaror](https://discourse.haskell.org/u/jaror)
#### Post date: [January 19, 2024, 4:49pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/4 "2024-01-19T16:49:36Z")
OK, the error messages here are terrible, but here’s what the paper says:
```haskell
instance MonadZero Parser where
zero = Parser (\cs -> [])
```
So you simply should remove that `=>` in this case.
---
### Author:  [@lukemccartney](https://discourse.haskell.org/u/lukemccartney)
#### Post date: [January 19, 2024, 5:08pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/5 "2024-01-19T17:08:11Z")
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):
```haskell
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:
```haskell
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.
```
Again, thanks for the help.
---
### Author:  [@jaror](https://discourse.haskell.org/u/jaror)
#### Post date: [January 19, 2024, 5:18pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/6 "2024-01-19T17:18:34Z")
You can’t use backticks (```) in names , you can fix it by using normal ticks:
```haskell
p >>= f = Parser (\cs -> concat [parse (f a) cs' | (a,cs') <- parse p cs])
```
---
### Author:  [@lukemccartney](https://discourse.haskell.org/u/lukemccartney)
#### Post date: [January 19, 2024, 5:19pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/7 "2024-01-19T17:19:55Z")
Yeah I tried that and it still didn’t work. I’ll try it again though.
---
### Author:  [@lukemccartney](https://discourse.haskell.org/u/lukemccartney)
#### Post date: [January 19, 2024, 6:33pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/8 "2024-01-19T18:33:16Z")
The error seems to be coming from the following code:
```haskell
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
```haskell
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.
```
Which I still don’t fully understand.
---
### Author:  [@jaror](https://discourse.haskell.org/u/jaror)
#### Post date: [January 19, 2024, 6:34pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/9 "2024-01-19T18:34:05Z")
> [@lukemccartney](#):
>
> ` return a = Parser (\cs -> [(a,cs)]`
You’re missing a closing paren `)` on this line.
---
### Author:  [@lukemccartney](https://discourse.haskell.org/u/lukemccartney)
#### Post date: [January 19, 2024, 7:05pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/10 "2024-01-19T19:05:38Z")
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:
```haskell
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:
```haskell
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.
---
### Author:  [@jaror](https://discourse.haskell.org/u/jaror)
#### Post date: [January 19, 2024, 7:10pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/11 "2024-01-19T19:10:26Z")
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:
```haskell
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:
```haskell
instance MonadPlus Parser where
p ++ q = Parser (\cs -> parse p cs ++ parse q cs)
```
---
### Author:  [@lukemccartney](https://discourse.haskell.org/u/lukemccartney)
#### Post date: [January 19, 2024, 8:50pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/12 "2024-01-19T20:50:05Z")
Okay. Having done all you have mentioned I am left with the _finally_ last error message. The error is:
```haskell
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
```haskell
instance MonadPlus Parser where
p ++ q = Parser (\cs -> parse p cs ++ parse q cs)
```
---
### Author:  [@jaror](https://discourse.haskell.org/u/jaror)
#### Post date: [January 19, 2024, 8:52pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/13 "2024-01-19T20:52:18Z")
Ah, then you also need to write your own `MonadPlus []` instance, for example:
```haskell
instance MonadPlus [] where
[] ++ ys = ys
(x : xs) ++ ys = x : (xs ++ ys)
```
---
### Author:  [@lukemccartney](https://discourse.haskell.org/u/lukemccartney)
#### Post date: [January 19, 2024, 8:58pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/14 "2024-01-19T20:58:30Z")
Adding this code lead to a new error…
```haskell
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.
```
---
### Author:  [@jaror](https://discourse.haskell.org/u/jaror)
#### Post date: [January 19, 2024, 8:59pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/15 "2024-01-19T20:59:18Z")
Ah, of course you also need `MonadZero []`:
```haskell
instance MonadZero [] where
zero = []
```
---
### Author:  [@lukemccartney](https://discourse.haskell.org/u/lukemccartney)
#### Post date: [January 19, 2024, 9:02pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/16 "2024-01-19T21:02:57Z")
Finally! It works! There is a warning though, do you know what it means?
```haskell
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.
```
Thanks for all the help by the way!
---
### Author:  [@leolee0101](https://discourse.haskell.org/u/leolee0101)
#### Post date: [January 19, 2024, 11:14pm UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/17 "2024-01-19T23:14:29Z")
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 .
---
### Author:  [@lukemccartney](https://discourse.haskell.org/u/lukemccartney)
#### Post date: [January 20, 2024, 10:42am UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/18 "2024-01-20T10:42:13Z")
Okay, so in order to avoid seeing that error what would I have to do? I already have instances for `Monad` and `Applicative` in my code.
---
### Author:  [@reuben](https://discourse.haskell.org/u/reuben)
#### Post date: [January 20, 2024, 11:09am UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/19 "2024-01-20T11:09:16Z")
> [@lukemccartney](#):
>
> ```haskell
> Either remove definition for ‘return’ (recommended) or define as ‘return = pure’
>
> ```
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.
---
### Author:  [@lukemccartney](https://discourse.haskell.org/u/lukemccartney)
#### Post date: [January 20, 2024, 11:56am UTC](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596/20 "2024-01-20T11:56:24Z")
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.
[Next page](https://discourse.haskell.org/t/monadic-parsing-in-haskell/8596.md?page=2)