PLT11 course -- assignment 8

(C) Ralf Lämmel, Andrei Varanovich, University of Koblenz Landau



The following tasks require the following skills:

  • recursive function definitions
  • data-type declarations
  • use of Eq, Ord, Show potentially
  • everything else as of the previous assignment

1st option

Declare a data type for the syntax of NB. Write a predicate (i.e., a Boolean function) that determines whether a given NB term is in normal form. Further, implement the evaluation rules and the type system. To this end, you need recursive functions that presumably use the Maybe data-type constructor—-because these are partial functions. (That is, not every term is well-typed and ill-typed terms can get stuck, in which case you need to return Nothing.)

2nd option

Declare a data type for the syntax of set-theoretic operations union, intersection, difference, empty, and singleton set. Make sure that the syntax (and hence the data type) is polymorphic. That is, the data type must be parametric in the element type of the set. Define a function eval to interpret expressions over the syntax. You can reuse a module for set-theoretic operations. In particular, module Data.Set comes with Haskell.

3rd option

Declare a data type for the syntax of arithmetic expressions such that the following forms are supported: literal (Int); unary negation; binary addition. Further define a data type for the syntax of a stack machine with fitting operations: push an Int; apply unary negation to the top-of-stack (TOS); apply binary addition to TOS and second TOS. Define a function that "transforms" an arithmetic expression into a list of stack operations.