Functional Programming

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

Assignment 2

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 06 Dec 2004 (deadline was 29 Nov: self-study sections 7.1-7.3 to get started before session 2!). 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.

D. Binary Trees

The file bTree.sml has the beginning of the realisation of a polymorphic abstract datatype (ADT) for binary trees, specified on slides 6.19 and 6.20. 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. nbLeaves b: the number of leaves of binary tree b
    Example: nbLeaves smallIntTree = 3
  2. isLeafOf x b: true if and only if x is a leaf of binary tree b
    Example: isLeafOf 7 smallIntTree = true
  3. descendants x b: the list of descendants of x in binary tree b, and exception NotFound raised if x is not in b
    Example: descendants 2 smallIntTree = [5,3,7]
    Example: descendants 7 smallIntTree = []
    Example: descendants 9 smallIntTree raises NotFound
  4. preorder b: the preorder walk, as a list, of binary tree b
    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?
  5. preorder' b: 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?
  6. preorders Bs: the concatenation of the preorder walks of the elements of the list Bs 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?
  7. preorder'' b: same specification as preorder
    Requirement: Use preorders as a help function

*E. 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 type, value, and functions of Exercise B (Integer Sets) of Assignment 1 such that the sets can be polymorphic (instead of being restricted to integers) and that your representation 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.
    Requirement: Either of the two approaches to polymorphism on slides 7.5 to 7.8 requires changes to some of the original specifications: justify your choice of one of these two approaches, and change those specifications accordingly.
  2. After choosing appropriate representations for finite sets & binary relations and writing/re-using functions for the necessary operations, write a curried function image R S 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 finite sets & directed graphs and writing/re-using functions for the necessary operations, write a curried function reachable G n that, given a finite directed graph G and a node n, returns the set of all nodes of G that are reachable from n by following the edges of G.
    Example: The set of nodes reachable from the node 1 in the graph with edge set {(1,2),(1,3),(2,5),(3,3),(3,4)} is {2,3,4,5}.
    Requirement: Argue why your representation choices are appropriate.
Last modified: Thu 18 Nov 10:44:42 MEST 2004