Exercise set 2.

The second week of this course covers chapters 7 and 8 of Programming in Haskell by Graham Hutton. The topic is higher order functions and type classes.

The objective of the exercises is to gain some initial hands-on programming experience with Haskell. Consider reading through the entire exercise set before you start working on it.

Credits

This weeks exercises are based on an assignment, developed by Andrzej Filinski for the course Advanced Programming at The University of Copenhagen.

Simple Integer Arithmetic Expressions

Consider the following algebraic data type, which represents simple arithmetic expressions:

data Expression =
    Constant       Integer
  | Addition       Expression Expression
  | Subtraction    Expression Expression
  | Multiplication Expression Expression
  | Division       Expression Expression
  | Exponentiation Expression Expression
--   ... (additional constructors; see next section)

To be precise, a simple integer arithmetic expression is either an integer constant, or one of the following five operations on two subexpressions: addition, subtraction, multiplication, integer division or exponentiation. Note that there is no provision for including explicit parentheses in the representation, as the tree structure of an Expression-typed value already encodes the intended grouping.

Printing simple arithmetic expressions.

Define a function

showExp :: Expression -> String

that renders a simple arithmetic expression as a string, using the usual Haskell infix notation, using +, -, *, div and ^ to represent the fice arithmetic operators mentioned above.

Include enough parentheses in the output to ensure that the output string can be correctly read and evaluated as a Haskell expression, and that any two different Expressions have distinct renderings (even if they would evaluate to the same result).

If the expression to be printed is not one of the above-mentioned six forms (i.e., if it belongs to the ... part of the Expression declaration above), your code should explicitly report the problem with an appropriate message (using the standard function error), rather than crash out with a non-exhaustive pattern-match error.

Evaluating expressions

Integer arithmetic expressions can be evaluated to numeric results. For instance, div n m (for m /= 0) to be the d part of { \over m} = d + {r \over m}. Additionally, we requrire that the exponent (second subexpression) in a Exponentiation-operation is non-negative, and specify that n^0 = 1 for all integers n, including 0.

evalSimple :: Expression -> Integer

such that evalSimple e computes the value of e, under the usual Haskell interpretation of the arithmetic operators specified above. If an error occurs inside a builtin operation (e.g., a division by zero), it is fine to just abort with the relevant Haskell runtime error.

Extended arithmetic expressions

Now, consider a richer class of expressions, given by the datatype:

type Name = String
data Expression =
-- ... (6 constructors from above)
  | Variable Name
  | If  {condition, yes, no          :: Expression}
  | Let {x :: Name, definition, body :: Expression}
  | Sum {i :: Name, from, to,   body :: Expression}

Here, the expression form If e1 e2 e3 represents a conditional expression (analogous to e1 ? e2 : e3in C). That evaluates to the result of evaluating e2 if e1 evaluates to a non-zero value; or the value of e3 otherwise

The expression Let v e1 e2 is used to bind the variable name v to the value of e1, (only) the duration of evaluating e2. Afterwards, the previous binding (if any) of v is reinstantiated.

It is deliberately left unspecified (i.e., you as the implementer may decide) whether an error occurring in the defining expression e1 should be signaled if the bound variable v is not actually used in the body e2.

Finally, the expression form Sum i e1 e2 e3 corresponds to the mathematical summation notation: $$\sum_{i=e_1}^{e_2} e_3$$ That is, it first evaluates $e_1$ and $e_2$ to numbers $n_1$ and $n_2$, and then computes the sum of the results of evaluating $e_3$, where $v$ is bound to each of the values $n_1, n_1+1,...,n_2$ in turn.

To keep track of variable bindings, we introduce an environment, which maps variable names to their values (if any). An environment may be represented by a higher order function of the following type:

type Environment = Name -> Maybe Integer

That is, if r is an environment and x is a variable name, then r x should return Just n for the value that was bound to x, and Nothing otherwise. Define a function

Define a function

evalFull :: Expression -> Environment -> Integer

that evaluates an expression in a given environment. As in the previous exercise, you may signal an error using the built-in function error.

Returning explicit errors

Promptly aborting evaluation with a Haskell error is a fairly drastic step, and in particular makes it impossible to recover gracefully from a conceptually non-fatal problem. A more flexible approach makes the evaluator function return an explicit indication of what went wrong, and lets the user of the evaluator decide what to do next. Accordingly, enumerate some possible failures:

data ArithmeticError =
    Unbound  Name    -- unbound variable
  | DivisionByZero   -- attempted division by zero
  | NegativeExponent -- attempted raising to negative power
  | Other String     -- any other errors, if relevant

Define a Haskell function

type Result            = Either ArithmeticError Integer
type BetterEnvironment = Name -> Result
evalError :: Expression -> BetterEnvironment -> Result

such that evalError e r attempts to evaluate e in environment r, as in evalFull, but now returns either an error value or a proper result rather than causing a Haskell runtime error (except possibly by running out of memory).

Challenge warmup (Minimally Bracketed Expressions)

Define a function

showConcise :: Expression -> String

Such that the string showConcise e represents an equivalent Haskell expression to that of showExp e, but containing the minimal number of parenthesis and spaces.

You should assume that the arithmetic operators have the conventional precedences and associativities (Add (Cst 2) (Mul (Cst 3) (Cst 4))) should be represented as "2+3*4", whereas (Add (Cst 2) (Add (Cst 3) (Cst 4))) should be represented by "2+(3+4)".

Challenge of the week (Evaluation Strategies)

In evalError, there are two natural interpretations of an expression Let v e1 e2; We can always evaluate e1 regardless of whether v appears in e2. And, we can postpone evaluating e1 until (if at all) its value is needed in e2. We will refer to the former interpretation as the Eager evaluation strategy, and the latter strategy, we will call Lazy.

Define and implement a function

data EvaluationStrategy = Eager | Lazy
evalStrategy :: EvaluationStrategy -> BetterEnvironment -> Result

such that either evalStrategy Lazy or evalStrategy Eager is semantically equivalent to your implementation of evalError.