Functional Programming MN1

Distance Course (1DL027)
Uppsala University, Sweden

Assignment 3

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

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

H. Increasing

Using standard higher-order functions (such as map, filter, reduce and foldr), write a non-recursive 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

Higher-order 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 non-recursive functions for
  1. countBtree b: the number of nodes of the integer binary tree b
  2. maxBtree b: the maximum node of the integer binary tree b
  3. sumBtree b: the sum of the nodes of the integer binary tree b
  4. inorder b: the inorder walk of the integer binary tree b
  5. 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