Uppgift 3 -- PK2 VT04 -- Uppsala Universitet

Uppgift 3 måste lämnas in senast måndag 3 maj klockan 10:15 (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, a close syntactic variant of which is specified on slides 6.19 to 6.24. 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. Compare the functions preorder, preorder', and preorder'' in terms of run-time and memory consumption.

B. Implementation of Sets

Implement a datatype for mathematical sets (mängder in Swedish), using a representation based on binary search trees, with the following standard set-theoretic value and 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: the number of elements in set s
7. member x s -- set membership test: 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. Do not forget comments with the representation convention and the representation invariant for your set datatype.

Inlämning

Överst i din fil ska följande finnas (inom kommentartecken):
• Ditt namn och klass.
• Om du löser uppgiften tillsammans med en annan student, ange den andra studentens namn. I så fall ska endast en av er lämna in en lösning, men båda ska meddela namn, klass och labpartner via inlämningssystemet.
• En kort beskrivning (en rad) av vad det är för fil.
• Alla kommentarer och all dokumentation ska vara på engelska.
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: formulär för inlämning