Functional Programming

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

Assignment 2

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 22 November 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.

ID:
PIN:
the submission form!

A. Function Tabulation

Write a function tabulate (n,f) that, given a natural number n and a function f on natural numbers, produces the list [f(0),f(1),...,f(n-1),f(n)]. Your function should apply equally well to functional arguments like abs or fn n => Math.sin(real n).
Hint: To force SML/NJ to print long lists, insert the following into your program:
(* Set the length of lists at which ellipsis begins *)
Compiler.Control.Print.printLength := 500 ;

B. Subset Sum

Write a predicate sss l n that, given a list of integers l and an integer n, returns true if and only if the sum of the elements of some sublist of l equals n.
Example: For l=[1,2,3,4,7] and n=6, the sublist [2,4] has the sum 6.

C. Binary Trees

The file bTree.sml has the beginning of the realisation of a polymorphic abstract datatype (ADT) for binary trees. The file trees.sml has sample trees for your tests and the examples below. Extend that ADT with the following functions, but declare it as a non-abstract datatype, just to ease the testing:
  1. The function nbLeaves counts the number of leaves of a binary tree.
    Example: nbLeaves smallIntTree = 3
  2. The curried predicate isLeafOf returns true if and only if its 'first' argument is a leaf of its 'second' argument.
    Example: isLeafOf 7 smallIntTree = true
  3. The curried predicate equalBtrees returns true if and only if its two binary tree arguments have the same inorder walk.
    Example: equalBtrees smallIntTree anotherSmallIntTree = false
  4. The curried function descendants returns a list with all the descendants of its 'first' argument in its 'second' argument, and raises the exception NotFound if that node is not in that tree.
    Example: descendants 2 smallIntTree = [5,3,7]
    Example: descendants 7 smallIntTree = []
    Example: descendants 9 smallIntTree raises NotFound
  5. The function preorder returns the preorder walk, as a list, of a binary tree.
    Example: preorder smallIntTree = [1,2,5,7,3,6,10,13]
    Requirements: Do not use any help functions. Is your function tail-recursive? Why / Why not?
  6. The function preorder' has the same specification as preorder.
    Requirements: Perform a descending generalisation, that is use a help function employing the accumulator technique. Is your function tail-recursive? Why / Why not?
  7. The function preorders returns the concatenation of the preorder walks of a list of binary trees.
    Note: This specification was obtained from the one for preorder by performing a tupling generalisation.
    Example: preorders [smallIntTree,anotherSmallIntTree] = [1,2,5,7,3,6,10,13,2,1,7,5,13,3,6,10]
    Requirements: Do not use any help functions. Each clause must have at most one recursive call. Is your function tail-recursive? Why / Why not?
  8. The function preorder'' has the same specification as preorder.
    Requirement: Use preorders as help function.
  9. Which of the functions preorder, preorder', and preorder'' is the most efficient in run-time? in memory consumption? Why?

D. Sets, Relations, and Graphs

For every representation of sets below, add a function toSet that converts a list into a set, as well as a function toList that converts a set into a list:
  1. Re-implement the set-theoretic operations of exercise C (integer sets) of Assignment 1 such that the sets can be polymorphic (instead of being restricted to integers) and that your datatype is based on binary search trees (instead of ordered lists). Consider it an ADT, but declare it as a non-abstract datatype, just to ease the testing.
  2. After choosing appropriate representations for sets & binary relations and writing efficient functions for the necessary operations, write a curried function image that, given a finite binary relation R and a finite set S, returns the set of all y such that R(x,y) holds for some x in S.
    Example: The image of the set {1,3} in the relation {(1,2),(1,3),(2,5),(3,3),(3,4)} is the set {2,3,4}.
    Requirement: Argue why your representation choices are appropriate.
  3. After choosing appropriate representations for sets & directed graphs and writing efficient functions for the necessary operations, write a curried function reachable that, given a finite directed graph G and a vertex v, returns the set of all vertices of G that are reachable from v by following the edges of G.
    Example: The set of vertices reachable from the vertex 1 in the graph with edge set {(1,2),(1,3),(2,5),(3,3),(3,4)} is {1,2,3,4,5}.
    Requirement: Argue why your representation choices are appropriate.
  4. After choosing an appropriate representation for binary relations and writing efficient functions for the necessary operations, write a predicate isTransitive that, given a finite binary relation R, returns true if and only if R is transitive.
    Example: The relation {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)} is transitive.
    Requirement: Argue why your representation choice is appropriate.

Last modified: Wed 12 Nov 12:37:42 MEST 2003