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:
- 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?
- 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?
- 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?
- The function preorder'' has the same specification as
preorder.
Requirement: Use preorders as help function.
- 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:
- empty -- the empty set
- insert x s -- insertion of an element x
into a set s
- union s1 s2 -- set union
- inter s1 s2 -- set intersection
- diff s1 s2 -- set difference, i.e., the elements
that belong to s1 but not to s2
- card s -- set cardinality
(i.e., the number of elements in set s)
- 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):
- 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.
- Filens namn (inklusive din hemkatalogs namn; hela sökvägen alltså).
- En kort beskrivning (en rad) av vad det är för fil.
- Notera att 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.