Functional Programming MN1
Distance Course (1DL027)
Uppsala University, Sweden
Assignment 3
F. TailRecursion
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 tailrecursive.
G. IndirectMap
Write a recursive higherorder 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]]
H. Increasing
Using standard higherorder functions
(such as map, filter, reduce and
foldr),
write a nonrecursive 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
I. bTreeFold
Higherorder functions can also be defined for trees. Consider for
example the following fold function for binary trees (as defined in Assignment 2).
fun bTreeFold f s Void = s
 bTreeFold f s (Bt(r,L,R)) =
f( r , bTreeFold f s L , bTreeFold f s R )
What does bTreeFold compute? Explain in words and
write a specification for the function.
J. Using bTreeFold
Using bTreeFold, write nonrecursive functions for

countBtree b: the number of nodes of the integer binary tree
b

maxBtree b: the maximum node of the integer binary tree
b

sumBtree b: the sum of the nodes of the integer binary
tree b
 inorder b: the inorder walk of the integer binary tree
b

isBST b: true if and only if b is
an integer binary search tree
Hint: There is a hard way to write isBst, and an
easy way. The easy way is not the most efficient, and will require the
construction of intermediate data structures.
Last modified: Mon Nov 26 16:46:43 MET 2007