Search code examples
haskell

Implementing Alternative instance of Parser in Haskell

I've been working through the CIS 194 Haskell course (https://www.seas.upenn.edu/~cis1940/spring13/lectures.html) and have gotten stuck on HW 10. I haven't been able to find a solution online. Any help would be appreciated!

The Parser is provided:

newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }

In addition, the HW provides satisfy, char, and posInt:

satisfy :: (Char -> Bool) -> Parser Char
satisfy p = Parser f
  where
    f [] = Nothing    -- fail on the empty input
    f (x:xs)          -- check if x satisfies the predicate
                        -- if so, return x along with the remainder
                        -- of the input (that is, xs)
        | p x       = Just (x, xs)
        | otherwise = Nothing  -- otherwise, fail

char :: Char -> Parser Char
char c = satisfy (== c)

posInt :: Parser Integer
posInt = Parser f
  where
    f xs
      | null ns   = Nothing
      | otherwise = Just (read ns, rest)
      where (ns, rest) = span isDigit xs

Following along in the homework I've defined the following for questions 1-4:

instance Functor Parser where
  fmap :: (a -> b) -> Parser a -> Parser b
  fmap f parser = Parser (\inString -> case runParser parser inString of
    Nothing -> Nothing
    Just (result, rest) -> Just (f result, rest))

instance Applicative Parser where
  pure f = Parser (\input -> Just (f, input))
  pa <*> pb = Parser (\input -> case runParser pa input of
    Nothing -> Nothing
    Just (f, rest) -> runParser (f <$> pb) rest)

abParser :: Parser (Char, Char)
abParser = (,) <$> char 'a' <*> char 'b'

abParser_ :: Parser ()
abParser_ = const () <$ char 'a' <*> char 'b'

intPair :: Parser (Integer, Integer)
intPair = selector <$> posInt <*> char ' ' <*> posInt where
  selector x y z = (x, z)

instance Alternative Parser where
  empty :: Parser a
  empty = Parser f where f _ = Nothing
  (<|>) :: Parser a -> Parser a -> Parser a
  (<|>) pa pb = Parser (\inputString -> runParser pa inputString <|> runParser pb inputString)

So far, all of this has worked as expected, but I'm now stuck on Exercise 5:

Implement a parser intOrUppercase :: Parser () which parses either an integer value or an uppercase character, and fails otherwise. cis 194: homework 10 4

*Parser> runParser intOrUppercase "342abcd"
Just ((), "abcd")
*Parser> runParser intOrUppercase "XYZ"
Just ((), "YZ")
*Parser> runParser intOrUppercase "foo"
Nothing

My initial attempt was this:

intOrUppercase :: Parser ()
intOrUppercase = const () <$ (\inputString -> (satisfy isUpper inputString) <|> (posInt inputString))

However, I get an error because of the type mismatch; the left Parser is Char and the right Parser is Integer, so this violates (<|>) :: Parser a -> Parser a -> Parser a

How can I implement the intOrUppercase Parser without violating this? Did I mess up somewhere else, or am I going about intOrUppercase the wrong way?

Solution

  • Most* Alternative instances have a distributive property: whenever both sides of the equation are well-typed, we have:

    f <$> (a <|> b) = (f <$> a) <|> (f <$> b)

    Although your starting point isn't well-typed, we can try using this property just for fun anyway. Taking f = const (), a = satisfy isUpper, and b = posInt, we get:

    const () <$> (satisfy isUpper <|> posInt) =
(const () <$> satisfy isUpper) <|> (const () <$> posInt)

    And what do you know, our fun has led us to an ending point that is well-typed!

    * My intuition is that parametricity actually guarantees this property for all Alternative instances, but I'm hedging because I haven't verified this.