Consider the following grammar of Boolean expressions.

<expr> ::= <term> | <expr> "|" <term>
<term> ::= <factor> | <factor> "&" <term> | “~” <factor>
<factor> ::= "0" | "1" | <proposition> | "(" <expr> ")"

where propositions have syntax given by the following regular expression.

<proposition> ::= [A-Za-z]

Problem 1 (1 mark)

Define a suitable Haskell algebraic data type for Boolean expressions.

data BE = Zero | One | Prop Char | Group BE | Not BE | And BE BE | Or BE BE
          deriving Eq

Why Eq?

Problem 2 (2 marks)

Write the Haskell type signature of the three recursive descent parsing functions required by the grammar.

parseExpr, parseTerm, parseFactor all have the follwing signature:

[Char] -> Maybe (BE, [Char])

Problem 3 (2 marks)

Implement the parseFactor function in Haskell.

parseFactor ('0':more) = Just (Zero, more)
parseFactor ('1':more) = Just (One, more)
parseFactor ('(':more) =
    case parseExpr(more) of
        Just (e, ')':yet_more) -> Just(Group e, yet_more)
        _ -> Nothing
parseFactor (c:more)
   | isAlpha c   =  Just(Prop c, more)
   | otherwise   =  Nothing
parseFactor [] = Nothing

Problem 4 (2 marks)

Implement the parseTerm function in Haskell.

This one is right-recursive, not left-recursive.

parseTerm ('~':more) =
    case parseFactor(more) of
        Just (e, yet_more) -> Just(Not e, yet_more)
        _ -> Nothing
parseTerm (s) =
    case parseFactor(s) of
        Just (e, '&':more) -> 
            case parseTerm(s) of 
                Just (e1, yet_more) -> Just(And e e1, yet_more)
                _ -> Nothing
        Just (e, more) -> Just(e, more)
        _ -> Nothing

What is wrong with the following?

parseTerm (x:'&':y:more) =
    case (parseFactor x, parseTerm y) of
         (Just (e, more), Just(e1, yet_more)) -> Just(And e e1, yet_more)
         _ -> Nothing

Problem 5 (3 marks)

Implement the parseExpr function in Haskell.

parseExpr s =
    case parseTerm(s) of
        Just (e, more) -> extendExpr(e, more)
        _ -> Nothing

extendExpr (e1, '|':more) =
    case parseTerm(more) of 
        Just(e2, yet_more) -> extendExpr(Or e1 e2, yet_more)
        _ -> Nothing
extendExpr(e1, s) = Just (e1, s)

Problem 6 (5 marks)

Implement a simplifier for Boolean expressions that systematically applies these rules through a given Boolean expression, returning a simplified expression for which no further application of the rules is possible.

simplifyBE :: BE -> BE
simplifyBE (Or f g) = makeOr (simplify f) (simplify g)
simplifyBE (And f g) = makeAnd (simplify f) (simplify g)
simplifyBE (Not f) = makeNot (simplify f)
simplifyBE (Group f)  = Group (simplify f)
simplifyBE f = f

makeOr Zero f = f
makeOr One f = One
makeOr f Zero = f
makeOr f One = One
makeOr f g
   | f == g    = f
   | otherwise = Or f g

makeAnd Zero f = Zero
makeAnd One f = f
makeAnd f Zero = Zero
makeAnd f One = f
makeAnd f g
   | f == g    = f
   | otherwise = And f g

makeNot Zero = One
makeNot One = Zero
makeNot (Not f) = f
makeNot f = Not f

Problem 7 (1 mark)

Consider the following Haskell function that returns the longest prefix of a list such that every element satisfies a given predicate p.

prefixWhile p [] = []
prefixWhile p (x : xs)
   |  p x       = x : (prefixWhile p xs)
   |  otherwise = []

What is the type signature of prefixWhile in most general form (use type variables)?

(a -> Bool) -> [a] -> [a]

Problem 8 (3 marks)

Recall that foldr combines elements of a list together using a fold function and an initial accumulator value, working from right-to-left.

foldr f a [] = a
foldr f a (x:xs) = f x (foldr f a xs)

(a) What is the type signature of foldr?

foldr :: (t -> t1 -> t1) -> t1 -> [t] -> t1

(b) Implement the function foldl that operates similarly to foldr, but working from left to right.

foldl f a [] = a
foldl f a (x:xs) = foldl f (f a x) xs

(c) Under what circumstances do you expect that these functions give different results (assuming that the lists are short)? Give an example.

When the function being folded is not associative.

• foldr (-) 0 [1,2,3] gives (1 - (2 - (3 - 0))) = 2
• foldl (-) 0 [1,2,3] gives (((0 - 1) - 2) - 3))) = -6

Problem 9 (1 mark)

What does the following Haskell function do? Write its type signature. Give an example.

map (\f->f 'c')

This function operations on a list of functions, applying each one to the character 'c' and returning a list of results. The signature is:

[(Char->b)] -> [b]

map (\f->f 'c') [(:[]), (\x -> [x, x, x])] 

gives

["c","ccc"]