Homework 8: Functor and Applicative

CIS 194: Homework 8
Due Tuesday, October 25

Exercise 1: A `Functor` instance

Given the following two data type definitions:

data ComplicatedA a b
    = Con1 a b
    | Con2 [Maybe (a -> b)]

data ComplicatedB f g a b
    = Con3 (f a)
    | Con4 (g b)
    | Con5 (g (g [b]))

Implement a Functor instance for both data types. You may have to add a Functor constraint on some of ComplicatedB’s type parameters.

Exercise 2: Rewriting monadic code

The following functions are written using the Monad combinators and/or do-notation, but not all of them use the full power of Monads. Some can be rewritten to use only Applicative or even only Functor laws.

Copy the following functions into your file and rewrite them to have only a Functor or Applicative constraint, if possible. Append a ' to the name of the rewritten function, so that you can test both in GHCi. As an example, I have done it for the first function.

If it is not possible, add a small note in a comment why you think it is not possible.

The rewritten functions should behave identical for any lawful instance of Monad.

func0 :: Monad f => (a -> a) -> f a -> f a
func0 f xs = do
    x <- xs
    return (f (f x))

func0' :: Functor f => (a -> a) -> f a -> f a
func0' f xs = (f . f) <$> xs

func1 :: Monad f => f a -> f (a,a)
func1 xs = xs >>= (\x -> return (x,x))

func2 :: Monad f => f a -> f (a,a)
func2 xs = xs >>= (\x -> xs >>= \y -> return (x,y))

func3 :: Monad f => f a -> f (a,a)
func3 xs = xs >>= (\x -> xs >>= \y -> return (x,x))

func4 :: Monad f => f a -> f a -> f (a,a)
func4 xs ys = xs >>= (\x -> ys >>= \y -> return (x,y))

func5 :: Monad f => f Integer -> f Integer -> f Integer
func5 xs ys = do
    x <- xs
    let x' = x + 1
    y <- (+1) <$> ys
    return (x' + y)

func6 :: Monad f => f Integer -> f (Integer,Integer)
func6 xs = do
    x <- xs
    return $ if x > 0 then (x, 0)
                      else (0, x)

func7 :: Monad f => f Integer -> f (Integer,Integer)
func7 xs = do
    x <- xs
    if x > 0 then return (x, 0)
             else return (0, x)

func8 :: Monad f => f Integer -> Integer -> f Integer
func8 xs x = pure (+) <*> xs <*> pure x

func9 :: Monad f => f Integer -> f Integer -> f Integer -> f Integer
func9 xs ys zs = xs >>= \x -> if even x then ys else zs

func10 :: Monad f => f Integer -> f Integer
func10 xs = do
    x <- xs >>= (\x -> return (x * x))
    return (x + 10)

Exercise 3: A parser monad

A great example for the convenience and usefulness of monads is parser combinators. In this exercise, you will build a small parser combinator library yourself. In the end, the following code will, for example, parse CSV files:

parseCSV :: Parser [[String]]
parseCSV = many parseLine
  where
    parseLine = parseCell `sepBy` char ',' <* char '\n'
    parseCell = do
        char '"'
        content <- many (anyCharBut '"')
        char '"'
        return content

Try to understand the above code! The operator <* comes with the Applicative class. Read the documentation to see what it does.

Some of the code you will write will bear resemblence with the Supply monad code from last week.

Define the type Parser of kind * -> *:
```
data Parser a = P (…)
```
A value of type Parser a is a function that takes a string (the remaining input at this point) and returns either Nothing, if parsing failed, or otherwise returns a value of type a and the remaining input.

Also define
```
runParser :: Parser a -> …
runParser (P p) = p
```
to remove the P constructor. Use this rather than explicit pattern matches in the functions below, as otherwise some recursive definitions will loop, because pattern matching (and hence evaluation) happens too early.
Define the function
```
parse :: Parser a -> String -> Maybe a
```
which is the main entry point to run a parser. It shall return successfully only if the parser consumed the whole input, i.e. if the function inside the Parser a returns a value of type a along with the empty string.
Implement a function
```
noParser :: Parser a
```
which represents the always failing parser.

You should have
```
parse noParser input == Nothing
```
for all inputs input, even the empty string.

Implement a function

pureParser :: a -> Parser a

which represents the parser that consumes no input and returns its argument.

You should have

parse (pureParser x) "" == Just x
xs ≠ "" ⇒ parse (pureParser x) xs == Nothing

Declare

instance Functor Parser where
    fmap …

You should have

parse (fmap f p) input == fmap f (parse p input)

for all f, p and input.

Declare
```
instance Applicative Parser where
    pure = pureParser
    fp <*> fx = …
```
which applies the left parser to the input first to get the function. If it succeeds, it applies the right parser to the remaining input to get the argument, and returns the function applied to the argument, and the leftover input by the right argument.

Declare

instance Monad Parser where
    return = pureParser
    fa >>= k = …

which works quite similar to <*>.

Define the primitive parser

anyChar :: Parser Char

that fails if the input is empty, and takes one character off the input otherwise:

parse anyChar "" == Nothing
parse anyChar [c] == Just c
length xs > 1 ⇒ parse anyChar xs == Nothing

Define the functions
```
char :: Char -> Parser ()
anyCharBut :: Char -> Parser Char
```
without breaking the abstraction introduced by the Parser data type, i.e. using only the combinators introduced above. You can use do-notation if you want.

Define the combinator

orElse :: Parser a -> Parser a -> Parser a

which tries the left parser. If it succeeds, it uses that, otherwise it runs the second parser on its input. This implements backtracking in a very naive way (so don’t expect this parser to have the best performance characteristics – there are highly optimized parser libraries out there).

You should have

parse (noParser `orElse` p) input == parse p input
parse (pureParser x `orElse` p) input == parse (pureParser x) input
parse (anyChar `orElse` pureParser '☃') "" == Just '☃'
parse (anyChar `orElse` pureParser '☃') [c] == Just c
length xs > 1 ⇒ parse (anyChar `orElse` pureParser '☃') xs == Nothing

Define the combinator
```
many :: Parser a -> Parser [a]
```
which applies the given parser as often as possible until it fails, and then returns all results as a list. Implement this again without breaking the abstraction, using the combinators above.

You should have
```
parse (many anyChar) xs = Just xs
parse (many noParser) "" = Just []
not (null xs) ⇒ parse (many noParser) xs = Nothing

-- if no '\n' in xs, then also:
parse (many anyCharBut '\n' <* char '\n') (xs++"\n") = Just xs
```
Fun facts about many that you should ponder (not part of the homework):
- The parser many p never fails.
- The expression many (pure x) is not very useful. Do you see why?
- What happens if you apply many to many?
Define the combinator
```
sepBy :: Parser a -> Parser () -> Parser [a]
```
so that p1 sepBy p2 applies the p1, then p2, then p1 and so on. Succeeds if the very first invocation of p1 fails, returning the empty string. Also succeeds if any invocation of p2 fails, returning the results of all p1 invocations as a list. Implement this again without breaking the abstraction, using the combinators above.

You should have
```
-- if xs is non-empty and does not end with '\n', then
parse (many (anyCharBut '\n') `sepBy` char '\n') xs = Just (lines xs)
```

With all this in place, test the CSV parser:

parse parseCSV "\"ab\",\"cd\"\n\"\",\"de\"\n\n"
    == Just [["ab", "cd"],["","de"],[]]

Exercise 4: Parsing an INI file

Here is a specification of an INI-like file format.

The file consists of one or more sections. Each section starts with a section header, which is a line consisting of just the section title enclosed in square brackets. Section titles are identifiers.

The body of each section is a (possibly empty) list of declarations, which is an identifier, followed by any number of space character, followed by the = sign, followed by more spaces, followed by the value. The value is the remaining content of the line, and may contain any characters except for the newline character ‘’, which terminates the line.

The body of each section may contain empty lines and comment lines (lines starting with #). These are to be ignored.

An identifier consists of letters or digits (see isAlphaNum in Data.Char) and must be non-empty.

And here is an example file:

[requests]
desiredFood = cookies
desiredQuantity = 20

[supply]
flour = 20 ounzes

sugar = none!
[conclusion]
# none!

Write a parser for this file format:

type Identifer = String
type Declaration = (Identifer, String)
type Section = (Identifer, [Declaration])
type INIFile = [Section]
parseINI :: Parser INIFile

The above file should parse as

[ ("requests",[("desiredFood","cookies"),("desiredQuantity","20")])
, ("supply",[("flour","20 ounzes") ,("sugar","none!")])
, ("conclusion",[])]

You might want to add further general combinators to your parser library, e.g. a variant many1 that works similar to many but fails if it cannot parse at least once, and maybe letterOrDigit :: Parser Char might be useful.

You can use this main function as a driver (and learn from it):

import System.Environment
import System.IO
import System.Exit

main :: IO ()
main = do
    args <- getArgs
    input <- case args of
        [] -> getContents
        [fileName] -> readFile fileName
        _ -> hPutStrLn stderr "Too many arguments given" >> exitFailure
    case parse parseINI input of
        Just i -> print i
        Nothing -> do
            hPutStrLn stderr "Failed to parse INI file."
            exitFailure

Homework 8: Functor and Applicative

Exercise 1: A Functor instance

Exercise 2: Rewriting monadic code

Exercise 3: A parser monad

Exercise 4: Parsing an INI file

Exercise 1: A `Functor` instance