Functional Programming

Distance Course (2AD200)
in the Maths & Natural Sciences programme (MN)
at Uppsala University, Sweden

Assignment 1

Requirements

Your solution must comply with the coding convention and ethics rules of this course. You may not use any library functions in your solution to this assignment. All programs, with optional test data, should be put into one file and submitted by 23:59 of Saturday 8 November 2003. Your file must compile and execute when submitted to the Standard ML of New Jersey, Version 110.0.7, installed on the university Unix network.

ID:
PIN:
the submission form!

A. Type Inference, Reduction, and Currying

Consider the following SML declarations:

fun mystery x = ((fn y => y-1) x) * ((fn y => y+1) x) + 1 fun triple g z = (1+1) * g z

Answer the following sub-questions:

Reverse-engineer the specifications of mystery and triple. Assume that mystery has no pre-condition and that the pre-condition on triple is that its function argument must be defined on the 'other' argument. Simplify the post-conditions as much as possible.
Give the SML value declaration that is equivalent to the SML function declaration of triple above.
Step-by-step explain what happens when the SML declaration val strange = triple mystery is entered.
Step-by-step reduce the SML expression strange 4.

B. Rational Numbers

Implement some standard arithmetic operations on rational numbers, represented as (nominator, denominator) pairs, namely:

add x y - addition
sub x y - subtraction x - y
inv x - inverse
mult x y - multiplication
divide x y - division x / y
equ x y - equality

Requirement: Keep the numbers reduced; for example 4/8 = 1/2.

C. Integer Sets

Sets of integers can be represented as (increasingly) ordered lists of integers. Implement some standard set-theoretic operations, namely:

empty - the empty set
insert x s - insertion of an element x into a set s
union s1 s2 - set union
inter s1 s2 - set intersection
diff s1 s2 - set difference, i.e., the elements that belong to s1 but not to s2
card s - set cardinality (i.e., the number of elements in set s)
member x s - set membership test, i.e., return true if x is a member of set s and false otherwise

Requirements: Exploit any pre-conditions to get more efficient programs. Explain why a representation based on ordered lists is better than one based on unordered lists.

D. Min-Max Simultaneously

Write a function minmax l that computes simultaneously the minimum and the maximum of the integer list l, as a pair.
Requirement: Your function should not make more than 3n / 2 comparisons for a list of length n.
Hint: For the next two elements a and b in the list, use one comparison to compute l=min(a,b) and u=max(a,b). Now one comparison with l is needed to possibly update the current minimum, and one with u for the current maximum.

E. Peano Numbers

Towards axiomatising natural-number arithmetic the way Euclid axiomatised geometry around 300 BCE, the Italian mathematician Giuseppe Peano proposed, in 1889, the following alternative representation of natural numbers:

the number 0 is represented by the constant Zero
the number 1 is represented by S(Zero), where S can be seen as a successor function
the number 2 is represented by S(S(Zero))
and so on. In other words, the positive integer n is represented by S(p), where p is the Peano representation of n-1.

Give SML declarations for the following:

An SML datatype for natural numbers, called nat, based on Peano's representation. (Normally, an abstract datatype would be declared, but that makes testing much harder.)
A value zero, which denotes the natural number 0.
A function next, which increases a natural number by 1.
Example: next Zero = S(Zero)
A curried predicate lessEq, which returns true if and only if its 'first' natural number argument is less than or equal to its 'second' natural number argument.
Example: lessEq S(Zero) S(S(Zero)) = true
Requirement: Declare this function as a recursive value.
An infix function plus, which returns the sum of two natural numbers.
Example: S(Zero) plus S(S(Zero)) = S(S(S(Zero)))
An infix function minus, which returns the difference of two natural numbers, assuming the result is a natural number.
Example: S(S(S(S(S(Zero))))) minus S(S(Zero)) = S(S(S(Zero)))
An infix function times, which returns the product of two natural numbers.
Example: S(S(S(Zero))) times S(S(Zero)) = S(S(S(S(S(S(Zero))))))
An infix function divMod, which returns the quotient and the remainder of the division of two natural numbers, assuming the result is mathematically defined.
Example: S(S(S(S(S(Zero))))) divMod S(S(Zero)) = ( S(S(Zero)) , S(Zero) )
A function natToInt, which converts a natural number into an integer.
Example: natToInt S(S(S(S(S(Zero))))) = 5
A function intToNat, which converts a non-negative integer into a natural number.
Example: intToNat 5 = S(S(S(S(S(Zero)))))

Last modified: Tue Nov 4 10:37:42 MEST 2003