5

I'm in chapter 8 of Graham Hutton's Programming in Haskell and I'm copying the code and testing it in GHC.

See the slides here: http://www.cis.syr.edu/~sueo/cis352/chapter8.pdf in particular slide 15

The relevant code I've copied so far is:

type Parser a = String -> [(a, String)]
pih_return :: a -> Parser a
pih_return v = \inp -> [(v, inp)]
failure :: Parser a
failure = \inp -> []
item :: Parser Char
item = \inp -> case inp of
                    [] -> []
        (x:xs) -> [(x,xs)]
parse :: Parser a -> String -> [(a, String)]
parse p inp = p inp
sat :: (Char -> Bool) -> Parser Char
sat p = do x <- item
           if p x then pih_return x else failure

I have changed the name of the return function from the book to pih_return so that it doesn't clash with the Prelude return function.

The errors are in the last function sat. I have copied this directly from the book.

As you can probably see p is a function from Char to Bool (e.g. isDigit) and x is of type [(Char, String)], so that's the first error.

Then pih_return takes a value v and returns [(v, inp)] where inp is a String. This causes an error in sat because the v being passed is x which is not a Char.

I have come up with this solution, by explicitly including inp into sat

sat :: (Char -> Bool) -> Parser Char
sat p inp = do x <- item inp
               if p (fst x) then pih_return (fst x) inp else failure inp

Is this the best way to solve the issue?

2
  • Slide 11 in that deck points to the full library version, which @Rüdiger Hanke, below, has given the link to. Indeed, the slide deck doesn't make it clear that all the code before slide 11 is just a first version, and all the code after slide 11 is meant to be used with the Monadic version in the library file. Apr 9, 2010 at 15:11
  • Ah. Thanks, MntViewMark. That explains things. It's not properly mentioned in the book either, only in the remarks at the end of the chapter where he says, "For technical reasons concerning the monadic nature of parsers, a number of the basic definitions in [the] library are slightly different to those given here".
    – Matt Ellen
    Apr 9, 2010 at 15:25

4 Answers 4

5

The first sat can't work, Parser must be a monad in order to use the do notation. In order to make it a monad instance, newtype would have to be used.

I don't own the book, but I suppose the author wanted to start with a simple parser type and later extend it to a full monad and I suspect that you have mixed up definitions of the non-monadic versions with one of the Parser monad (sat) and missed the monad instance declaration along the way.

There's code from the chapter available on the author's web site where a monad instance has been defined for Parser.

If you must write a sat function for the simple Parser type I'd rather do it in lambda-style (as item) and avoid monads entirely (you noticed that the original sat's doblock was a Parsermonad and yours is a List monad?). And I think you have a bug in your sat version: rather than pih_return (fst x) inp, I think it should be pih_return (fst x) (snd x).

2
  • Thanks for pointing that out. Looking at the code from the website, it is noticeably different from the book. The book doesn't mention monads at this point.
    – Matt Ellen
    Apr 9, 2010 at 15:27
  • Also, thanks for pointing me to the website. Google hasn't found it and it has the errata in there.
    – Matt Ellen
    Apr 9, 2010 at 16:35
2

You can't use do notation without a monad, and you can't make a monad instance unless you use data or newtype, and you can't use data or newtype unless you introduce an annoying value constructor. Undoubtedly the value constructor has been omitted just because it is annoying.

In the example below you can see that I've used newtype and have introduced the annoying value constructor Parser. This is what makes the instance declaration work, and at this point you can use not only do-notation but also the standard monadic return and fail.

This code compiles without errors or warnings:

module P
where

newtype Parser a = Parser (String -> [(a, String)])
instance Monad Parser where
  return a = Parser $ \inp -> [(a, inp)]
  fail _   = Parser $ \_   -> []
  Parser f >>= k = Parser $ \inp -> 
     [(b, inp'') | (a, inp') <- f inp, let Parser g = k a, (b, inp'') <- g inp']

item :: Parser Char
item = Parser $ \inp -> case inp of
                          [] -> []
                          (x:xs) -> [(x,xs)]
parse :: Parser a -> String -> [(a, String)]
parse (Parser p) inp = p inp
sat :: (Char -> Bool) -> Parser Char
sat p = do x <- item
           if p x then return x else fail "predicate not satisfied"
1

The slides are missing the implementation of the Monad typeclass for the type Parser.

With that declaration, the do notation is correct; x <- item actually does the correct unwrapping from [(Char, String)] to (Char, String).

I can't seem to get this definition without compiling it to see the error but it's a start:

instance Monad (Parser a) where
  return x = pih_return x
  -- (>>=) :: Parser a -> (a -> Parser b) -> Parser b
  p >>= f = \inp -> case p inf of
                      [] -> []
                      (x:xs) -> (f x) xs -- this line is probably wrong
  fail message = [] -- message is ignored
1
  • Thanks Nathan. The book mentions p >>= f using a slightly different syntax, but I imagine that is due to monads not being explicitly mentioned.
    – Matt Ellen
    Apr 9, 2010 at 15:43
1

I'm reading the very same book and arrived at the same problem when trying to do the excercises. I reverted from using the 'do ...' notation to the >>=. For anyone interested I enclosed my code up to using the nat function. I prepended all my functions with a and changed >>= to >>>= in order to avoid name collisions with prelude.

type AParser a = String -> [(a, String)]
areturn :: a -> AParser a
areturn v = \inp -> [(v, inp)]
afailure :: AParser a
afailure = \inp -> []
aitem :: AParser Char
aitem = \inp -> case inp of
                  [] -> []
                  (x:xs) -> [(x, xs)]
aparse :: AParser a -> String -> [(a, String)]
aparse p inp = p inp
(>>>=) :: AParser a -> (a -> AParser b) -> AParser b
p >>>= f = \inp -> case aparse p inp of
                    [] -> []
                    [(v, out)] -> aparse (f v) out
(+++) :: AParser a -> AParser a -> AParser a
p +++ q = \inp -> case aparse p inp of
                    [] -> aparse q inp
                    [(v, out)] -> [(v, out)]
asat :: (Char -> Bool) -> AParser Char
asat p = aitem >>>= (\x -> if p x then areturn x else afailure)
adigit :: AParser Char
adigit = asat isDigit
amany :: AParser a -> AParser [a]
amany p = amany1 p +++ areturn []
amany1 :: AParser a -> AParser [a]
amany1 p = p >>>= (\v -> (amany p) >>>= (\vs -> areturn (v:vs)))
anat :: AParser Int
anat = amany1 adigit >>>= (\xs -> areturn (read xs))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.