"Programming In Haskell" error in sat function

Question

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?

Answer 1

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).

Answer 2

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

Answer 3

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"