Assignment 2

Assignment 2

This assignment has to be solved individually and handed in using the fire system before Monday 17 Nov.

The system is available at https://fire.cs.chalmers.se:8018/cgi-bin/Fire

The solution should be in the form of a program (with comments). If you use Haskell you can use literate Haskell if you want.

Please, send in one text-file, not a pdf-file! They are difficult to test-run.

1. The natural numbers N are inductively defined (see for instance the lecture notes). Implement this definition as a data type in a functional programming language (so you are not going to use the built-in types integers etc).

2. Define the higher order function rec (from the lecture notes) and use this to define the function add :: N -> N -> N which implements addition ( add a b = a+b) . The definition of addmust not be recursive.

3. Give an inductive definition of the set Z of integers and implement also this as a data type. In the lecture notes we have an erroneous definition, don't use this! It is only there to discuss what properties an inductive definition should have. In the implementation you should explain how to represent the integers -1, 0, 1 and 3. The implementation should make it easy to express addition, subtraction and multiplication (but you don't have to implement these operations).

4. There is a higher order function zrec which is analogous to rec, which expresses structural recursion on Z. Implement this (and give its type).

5. A set is recursively enumerable if there is a computable function enumerating the set. Show that the integers are recursively enumerable by implementing a surjective function ntoz :: N -> Z in a functional language. Explain why this is a surjective function. If you have not been able to solve problem 3 (and have no implementation of Z) then you can write an informal program.