Functional Programming

###
Distance Course (2AD200)

in the Maths & Natural Sciences programme (MN)

at Uppsala University, Sweden

# Assignment 3

## 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 13 Dec
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.
## *F. Tail-Recursion

Write a function `average` that computes the average of a list
of real numbers.

Example: `average [1.0,4.0,10.0] = 5.0`

Requirement: Use exactly one help function, which must be tail-recursive.
## G. Variadic Trees

In a variadic tree, nodes have *any* number of subtrees, but
they must all be non-empty, and this number *may* vary from
node to node.
- Give an appropriate datatype for polymorphic variadic trees.
Consider it an ADT, but declare it as a
*non-abstract*
datatype, just to ease the testing.
- Write a function
`preorder` that returns the preorder walk,
as a list, of a variadic tree.
- Write a function
`nbLeaves` that returns the number of
leaves of a variadic tree.
- Write a function
`height` that returns the height of a
variadic tree.
- Write a function
`reflect` that returns the reflection of a
variadic tree: for every node of *n* subtrees, the
*i*^{th} subtree becomes the
*n−i*+1^{st} subtree.

Requirement: Implement the functions using *recursion*.
## *H. Higher-Order Functions

- Write a recursive higher-order curried function
`indirectMap f
Xs` that applies the function `f` to every element of
every element of the list of lists `Xs`.

Example: `indirectMap (fn x => x * 2) [[1,2],[4,5,6]] = [[2,4],[8,10,12]]`
- Write a curried higher-order function
`bTreeFold f s b`,
performing for binary trees what `foldl` and `foldr`
do for lists, namely applying a 3-ary function `f` to the
root of the binary tree `b` and the results of applying
`f` to the left and right subtrees of `b`, in this
order, given a start value `s`.
- Using
`bTreeFold`, write non-recursive functions for:
`maxBtree b`: the maximum node of integer binary tree
`b`
`sumBtree b`: the sum of the nodes of integer binary
tree `b`
`mirror b`: the mirror tree (with the left and right
subtrees exchanged) of binary tree `b`
`inorder b`: the inorder walk of integer binary tree
`b`
`isBST b`: `true` if and only if `b` is
an integer binary *search* tree

- Using
*standard* higher-order functions, write a predicate
`increasing Xs` that returns `true` if and only if the
list `Xs` is in strictly increasing order.

Example: `increasing [1,2,3,4,5,6,7,9] = true`

Example: `increasing [1,2,3,4,4,6,7,9] = false`
- Using your own or standard higher-order functions, write a curried
function
`countPreds Ps Xs` that returns an integer list
whose *i*^{th} element is the number of elements of
the predicate list `Ps` that return `true` on the
*i*^{th} element of the list `Xs`.

Example: `countPreds [Char.isLower,Char.isUpper] [#"a",#"A",#"1"] = [1,1,0]`

Example: `countPreds [fn x => x mod 2 = 0, fn x => x mod 3 = 0] [1,2,3,4,5,6] = [0,1,1,1,0,2]`

Requirement: Recursion may only occur in your own higher-order functions.

Last modified: Wed 20 Oct 10:45:42 MEST 2004