Functional Programming

###
Distance Course (2AD200)

in the Maths & Natural Sciences programme (MN)

at Uppsala University, Sweden

# Assignment 3

# Requirements

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 23:59 of Saturday 6
December 2003**. 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. 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.
## B. Variadic Trees

In a variadic tree, nodes can have *any* number of subtrees,
and this number *may* vary from node to node.
- Give an appropriate representation of polymorphic variadic trees.

In the following, 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^{th} subtree.

## C. Higher-Order Functions

- 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
`maxBtree`, `sumBtree`, `mirror`, and
`inorder` that compute the maximum node, the node sum, the
mirror tree (with the left and right subtrees exchanged), and the
inorder walk, respectively, of an integer binary tree.

Using `bTreeFold`, write a non-recursive predicate
`isBST` that returns `true` if an intger binary tree
is a binary *search* tree.
- Using
*standard* higher-order functions, write a predicate
`increasing` that returns `true` if the argument
integer list 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.
- Write a recursive higher-order 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]]`

Last modified: Fri 21 Nov 17:37:42 MEST 2003