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

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

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

- 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*

Last modified: Fri 5 Nov 09:51:42 MEST 2004