Uppgift 3 -- AD1 VT04 -- Uppsala Universitet

Uppgift 3 måste lämnas in senast måndag 23 februari klockan 11:59 (på morgonen). Lämna in den med hjälp av inlämningssystemet (se slutet av denna sida). Se till att läsa igenom kodkonventionerna innan du börjar. Dessa skall följas.

A. The Power of Problem Generalisation

Problem generalisation is a powerful technique (a) for improving the time or space complexity of a function, and (b) for dealing with problems for which a recursively defined function cannot readily be found. In this exercise, you will apply two different generalisation techniques to the same problem, and compare the results.

The file binTrees.sml has a realisation of a polymorphic abstract datatype (ADT) 'a bTree for binary trees. The file trees.sml has sample trees for your tests and the examples below. Add the following functions to that ADT:

  1. 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?
  2. The function preorder' has the same specification as preorder.
    Requirements: Use exactly one help function, which must be obtained by introducing an accumulator. (This technique is known as descending generalisation.) Is your help function tail-recursive? Why / Why not?
  3. The function preorders takes a list of binary trees as an argument and returns the concatenation of the preorder walks of the trees in that list. (This specification was obtained 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?
  4. The function preorder'' has the same specification as preorder.
    Requirement: Use preorders as help function.
  5. Which of the functions preorder, preorder', and preorder'' is the most efficient in run-time? in memory consumption? Why?

B. Implementation of Sets

Implement a datatype for sets, using a representation based on binary search trees, with the following standard set-theoretic operations:
  1. empty -- the empty set
  2. insert x s -- insertion of an element x into a set s
  3. union s1 s2 -- set union
  4. inter s1 s2 -- set intersection
  5. diff s1 s2 -- set difference, i.e., the elements that belong to s1 but not to s2
  6. card s -- set cardinality (i.e., the number of elements in set s)
  7. member x s -- set membership test, i.e., return true if x is a member of set s, and false otherwise
Consider it an abstract datatype, but declare it as a non-abstract datatype, just to ease the testing.

Inlämning

Överst i din fil ska följande finnas (inom kommentartecken): Kontrollera att du hunnit ge svar på varje deluppgift.

Din inlämning ska vara körbar. Det som inte är kod ska vara bortkommenterat!

Glöm inte att alla funktioner ska dokumenteras enligt kodkonventionerna.

Hämta ett formulär för att lämna in uppgiften genom att fylla i fälten nedan.

ID:
PIN:
formulär för inlämning