# 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 22 Nov 2004 (deadline was 15 Nov: self-study sections 4.2-4.5 and 5.3-5.4 to get started before session 1!). 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
1. 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.
2. Give the SML value declaration that is equivalent to the SML function declaration of triple above.
3. Step-by-step explain what happens when the SML declaration val strange = triple mystery is entered.
4. Step-by-step reduce the SML expression strange 4.

## *B. Integer Sets

Give SML declarations for the following type, value, and functions:
1. 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.
2. empty: the empty set ∅
3. insert x s: the set s ∪ {x}
4. union s1 s2: the set s1 ∪ s2
5. inter s1 s2: the set s1 ∩ s2
6. diff s1 s2: the set s1 \ s2, that is the set of elements belonging to s1 but not to s2
7. card s: the cardinality of the set s, that is the number of elements of s
8. member x s: true if and only if x ∈ s
9. 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:
1. 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.
2. zero: the natural number 0
3. next n: the natural number n + 1
Example: next Zero = S(Zero)
4. natToInt n: the natural number n as an integer
Example: natToInt S(S(S(S(S(Zero))))) = 5
5. intToNat i: the non-negative integer i as a natural number
Example: intToNat 5 = S(S(S(S(S(Zero)))))
6. a plus b: the natural number a + b
Example: S(Zero) plus S(S(Zero)) = S(S(S(Zero)))
7. 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)))
8. a times b: the natural number a · b
Example: S(S(S(Zero))) times S(S(Zero)) = S(S(S(S(S(S(Zero))))))
9. 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) )
10. 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.