Functional Programming

in the Maths & Natural Sciences programme (MN)

at Uppsala University, Sweden

Answer the following sub-questions:fun mystery x = ((fn y => y-1) x) * ((fn y => y+1) x) + 1

fun triple g z = (1+1) * g z

- 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`.

`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

`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

Requirement: Your function should not make more than

Hint: For the next two elements

- 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