Practice Problems (Week 9)

These practice problems (unlike the exercises) are not assessed. Use them to test your understanding, to challenge yourself, or whatever floats your boat.

1 Poor man's DataKinds

The lecture illustrates the use of the DataKinds language extension to constrain the possible instantiations of phantom type variables. This made it impossible to write nonsense like Sq [ Bool ] where a unit of measure was expected.

Another language mechanism that can restrict type instantiation is type classes. Here's how you might try to achieve the same effect using type classes. The idea is that Unit is the set of all types that represent units of measure. This type class has no methods because it's only used for marking.

data Km
data Mile
data Sq a

class Unit a

instance Unit Km
instance Unit Mile
instance Unit a => Unit(Sq a)

data Distance a = Distance Double deriving(Eq,Show)

km5 :: Distance Km
km5 = Distance 5

mile5 :: Distance Mile
mile5 = Distance 5

times :: Unit a => Distance a -> Distance a -> Distance(Sq a)
times (Distance x) (Distance y) = Distance(x*y)

plus :: Unit a => Distance a -> Distance a -> Distance a
plus (Distance x) (Distance y) = Distance(x+y)

How does this approach compare with the DataKinds approach? Which one does a better job of making illegal states unrepresentable? If there are any shortcomings, are there any strategies to overcome or mitigate them that you can think of?

2 Parser combinators

Use the parser combinator library from the Assignment 2 template to write a parser for Boolean algebra expressions Exp , that can parse boolean expressions involving || (or), && (and), T (true), F (false), negation ( ! ), and variable names (lower-case strings).

To simplify matters, write a parser that assumes the input is in the following highly restrictive format:

• No whitespace anywhere
• Conjunction and disjunction operators always have parentheses around them, like this: (e1&&e2) resp. (e1||e2)

Write a parser parseExp :: Parser Exp to accomplish this task:

data Exp = TrueE
         | FalseE
         | VarE String
         | OrE Exp Exp
         | AndE Exp Exp
         | NotE Exp deriving (Eq,Show)

parseExp :: Parser Exp
parseExp = undefined -- TODO

For example, you'd expect the following behaviour:

λ> runParser parseExp "(!x&&(y||F))"
Just (AndE (NotE (VarE "x")) (OrE (VarE "y") FalseE)) 

For example, you'd expect the following behaviour:

λ> runParser parseExp "(!x&&(y||F))" Just (AndE (NotE (VarE "x")) (OrE (VarE "y") FalseE)) 

For an extra challenge, you can try relaxing some of these syntactic restrictions. If you do, you have to deal with e.g:

• Relative presedence of operators: should a||b&&c be parsed as (a||b)&&c or a||(b&&c)
• Associativity of operators: should a||b||c be parsed as (a||b)||c or a||(b||c)

3 Maze game

Pick up the following writing prompt from the lectures: Design a game that reads in an n by n maze from a file. The player starts at position (0, 0) and must reach position (n-1, n-1) to win. The game accepts keyboard input to move the player around the maze. Note that this involves deciding on a file format to represent mazes.