[Haskell-beginners] Functional Parses

Christian Maeder Christian.Maeder at dfki.de
Tue Jul 3 16:13:50 CEST 2012


Am 03.07.2012 15:16, schrieb Robert Heumüller:
> I am sorry, I must have hit the wrong hotkey.
> My code looks like this:
>
> type Parser a = String -> [(a, String)]

This type synonym is unsuitable for a Monad instance.
Better would be:
   newtype Parser a = Parser (String -> [(a, String)])
but that would require to change your code below.

>
> result :: a -> Parser a
> result v = \inp -> [(v, inp)]
>
> zero :: Parser a
> zero = \inp -> []
>
> item :: Parser Char
> item = \inp -> case inp of
>      [] -> []
>      (x:xs) -> [(x, xs)]
>
> parse :: Parser a -> String -> [(a, String)]
> parse p inp = p inp
>
> (>>=) :: Parser a -> (a -> Parser b) -> Parser b
> (>>=) p f = \inp -> concat [f v inp' | (v, inp') <- p inp]

Such a definition (without signature and adapted to the newtype) should 
be used within a Monad instance. "instance Monad Parser where ..."

> sat :: (Char -> Bool) -> Parser Char
> sat p = do  x <- item
>              if p x then result x else zero

Without proper Monad instance you should not use "do". Instead you could 
expand it yourself manually to:

  sat p = item Main.>>= \x ->
             if p x then result x else zero

Note the clash between your ">>=" function (Main.>>=) and the one from 
the Prelude!

HTH Christian

P.S. there is a "instance Monad ((->) r))" in Control.Monad.Instances
but that does not fit your parser type, too.

>
>
> I beleive I understand how this code is meant to work, but when I run
> it in ghci I get the follwing error-message:
>
> parser.hs:21:13:
>      No instance for (Monad ((->) String))
>        arising from a do statement
>      Possible fix: add an instance declaration for (Monad ((->) String))
>      In a stmt of a 'do' block: x <- item
>      In the expression:
>        do { x <- item;
>             if p x then result x else zero }
>      In an equation for `sat':
>          sat p
>            = do { x <- item;
>                   if p x then result x else zero }
>
> parser.hs:22:18:
>      Couldn't match expected type `Char'
>                  with actual type `[(Char, String)]'
>      In the first argument of `p', namely `x'
>      In the expression: p x
>      In a stmt of a 'do' block: if p x then result x else zero
> Failed, modules loaded: none.
>
>
> Sadly I have no idea how to fix this :(
>
> Thanks again :)
>




More information about the Beginners mailing list