Functional Programming

Distance Course (2AD200)
in the Maths & Natural Sciences programme (MN)
at Uppsala University, Sweden

Assignment 3


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.

the submission form!

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.
  1. 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.
  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+1th subtree.

C. Higher-Order Functions

  1. 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.
  2. 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
  3. 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.
  4. 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