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.
  1. 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.
  2. Write a function preorder that returns the preorder walk, as a list, of a variadic tree.
  3. Write a function nbLeaves that returns the number of leaves of a variadic tree.
  4. Write a function height that returns the height of a variadic tree.
  5. 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+1st subtree.
Requirement: Implement the functions using recursion.

*H. Higher-Order Functions

  1. 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]]
  2. 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.
  3. Using bTreeFold, write non-recursive functions for:
    1. maxBtree b: the maximum node of integer binary tree b
    2. sumBtree b: the sum of the nodes of integer binary tree b
    3. mirror b: the mirror tree (with the left and right subtrees exchanged) of binary tree b
    4. inorder b: the inorder walk of integer binary tree b
    5. isBST b: true if and only if b is an integer binary search tree
  4. 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
  5. 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.
Last modified: Wed 20 Oct 10:45:42 MEST 2004