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
ith subtree becomes the
n-i+1th 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 ith element is the number of elements of
the predicate list Ps that return true on the
ith 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