Functional Programming
Distance Course (2AD200)
in the Maths & Natural Sciences programme (MN)
at Uppsala University, Sweden
Assignment 1
Requirements
Only the starred exercises are mandatory. 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. You may only use higher-order functions where
explicitly requested. All programs, with optional test data, should
be put into one file and submitted by 07:59 of Mon
Nov 2004 (). 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.
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. Integer Sets
Give SML declarations for the following type, value, and functions:
- An SML datatype for finite integer sets, called
iset, based on increasingly ordered lists of integers.
Declare it as a non-abstract datatype, just to ease the
testing.
- empty: the empty set ∅
- insert x s: the set s ∪ {x}
- union s1 s2: the set s1 ∪ s2
- inter s1 s2: the set s1 ∩ s2
- diff s1 s2: the set s1 \ s2, that is the set of
elements belonging to s1 but not to s2
- card s: the cardinality of the set s, that is
the number of elements of s
- member x s: true if and only if x ∈ s
- Explain why a representation based on ordered lists is better than
one based on unordered lists.
Requirements: The functions must be recursive. Exploit any
pre-conditions to get more efficient functions.
C. 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 finite natural numbers:
- the natural number 0 is represented by the constant Zero
- the natural number 1 is represented by S(Zero), where
S can be seen as a successor function
- the natural 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 representation of n−1.
Give SML declarations for the following type, value, and functions:
- An SML datatype for finite natural numbers, called
nat, based on Peano's representation. Declare it as a
non-abstract datatype, just to ease the testing.
- zero: the natural number 0
- next n: the natural number n + 1
Example: next Zero = S(Zero)
- natToInt n: the natural number n as an integer
Example: natToInt S(S(S(S(S(Zero))))) = 5
- intToNat i: the non-negative integer i as a
natural number
Example: intToNat 5 = S(S(S(S(S(Zero)))))
- a plus b: the natural number a + b
Example: S(Zero) plus S(S(Zero)) = S(S(S(Zero)))
- a minus b: the natural number a - b,
assuming this result is a natural number
Example: S(S(S(S(S(Zero))))) minus S(S(Zero)) = S(S(S(Zero)))
- a times b: the natural number a · b
Example: S(S(S(Zero))) times S(S(Zero)) = S(S(S(S(S(S(Zero))))))
- a divMod b: the natural number quotient and remainder of
a ÷ b, assuming this division is
mathematically defined
Example: S(S(S(S(S(Zero))))) divMod S(S(Zero)) = ( S(S(Zero)) , S(Zero) )
- lessEq a b: true if and only if a ≤ b
Example: lessEq S(Zero) S(S(Zero)) = true
Requirement: Declare this function as a value
Requirement: The functions must be recursive, except next.
Last modified: Fri 5 Nov 09:51:42 MEST 2004