Obligatorisk uppgift 1: Dubbla paradigm

Ni ska implementera den abstrakta datatypen mängd.Er mängdska ha
följande funktioner:

Empty

Ger en tom mängd.

isempty s

Testar om mängden s är tom.

memberof v s

testar om v tillhör mängden s

equal s t

testar om mängderna s och t är lika

single v

bildar en mängd med v som enda element

insert v s

sätter in elementet v i mängden s

remove v s

tar bort elementet v i mängden s

choose s

väljer ut ett godtyckligt element ur mängden s

union s t

slår ihop mängderna s och t

intersection s t

ger snittmängden av mängderna s och t

difference s t

ger mängddifferensen av mängderna s och t

subset s t

testar om mängden s är en delmängd av mängden t

Tips:
1. Även om en mängd egentligen är oordnad så underlättas t ex equal om din underliggande
implementation är ordnad.
2. "godtyckligt" i beskrivningen av choose betyder inte slumpartad (dvs att mängden ska välja
godtyckligt) utan att dukan välja godtyckligt, t ex alltid det första bland dina ordnade element.
3. Leta upp DoA- och diskmatte-böckerna och repetera hur mängder fungerar!

Ni ska göra en implementation i dels ett valfritt funktionellt språk (t ex ML eller
Haskell) dels i ytterligare ett språk, valfri paradigm. Se till att implementationerna
är så modulära och modifierbara som möjligt (använd t ex abstype i ML). Försök
att göra implementationen så oberoende som möjligt av vilken datatyp som ska
lagras . Obs! Handledarna förbehåller sig rätten att endast ge god handledning i
språk de har ett hum om. ;-)

Den viktigaste delen i rapporten är att ni ska jämföra de två implementationerna
och diskutera språkens brister och möjligheter när det gäller stöd för dataabst-
raktion och modularisering. Rapporten skall också innehålla en beskrivning av
datatypens representation, koden och några testexempel som visar att din imple-
mentation fungerar.

Diskussioner kring följande punkter måste finnas med, men
det är bra om ni kan komma med fler och mer uttömmande åsikter:

• Hur lätt var det att implementera? Är det lätt att "läsa" programmet?
• Hur väl stöder språket dataabstraktion? Måste typen på elementen
  i mängden bestämmas i förväg?
• Hur gör man om man vill använda fler mängder i sitt program, där typen
  på elementen är olika? Finns det några begränsningar på vilka typer som
  kan användas för elementen i mängden?
• Hur skyddad är den interna representationen? Är det lätt att byta ut den?
• Vilka alternativa interna representationer finns det? Vilka brister och/eller
  fördelar har din lösning? Skulle en annan representation vara bättre?
• Vilka inslag i språken underlättar respektive hindrar olika lösningar?

OBS! Det är diskussionen som är det viktigaste i uppgiften, inte själva
implementationerna. Men implementationerna ska naturligtvis ändå vara
korrekta och lättlästa. Förutom diskussionen ska rapporten innehålla algoritmer
och systembeskrivning.

OBS! Skriv gärna ned dina synpunkter på laborationen i sig. Var den svår/lätt?
Hur länge höll du på med den? Tycker du att den tog för mycket/lite tid? Har du
lärt dig något när du gjorde den? Fick du den hjälp du behövde? osv.

Laborationen ska utföras enskilt och vara inlämnad senast den 18/11 1999
kl. 12.00, och vara godkänd senast den 21/1 2000.