Uppgift 8 ­ PM1/PK HT-02

Uppgift 8 måste lämnas senast tisdag 19/11 kl. 08:00. Lämna in den med hjälp av inlämningssystemet i slutet av denna sidan.

Efter denna laboration ska du kunna...

• Arbeta med abstrakta datatyper

Före laborationen

• Läs igenom hela uppgiften
• Läs relevanta avsnitt i boken (kap. 8.7) och OH-bilderna (kap. 6)
• För programmeringsuppgifter. Se till att följa kodkonventionen, den skall följas.

Din inlämning

Överst i din fil ska följande finnas (inom kommentartecken):

• Ditt namn
• Filens namn (inklusive din hemkatalogs namn; hela sökvägen alltså)
• En kort beskrivning (en rad) av vad det är för fil

Uppgiften

Problem 1

En mängd är en datastruktur som fungerar som en (ändlig) matematisk mängd), det vill säga den innehåller en (godtycklig) samling element. På det sättet liknar den listor men den skiljer sig från listor på två punkter:

• Mängder är inte ordnade; listor är ordnade. (I en lista kan man fråga om ett element kommer före ett annat; i en mängd går inte detta.)
• Mängder innehåller inte dubbletter; det kan listor göra. (Om man lägger till 3 till en mängden {1, 2, 3} så innehåller den fortfarande bara tre tal.)

Du ska implementera en abstrakt datatyp ''a set som skall representera mängder som innehåller element av godtycklig (likhets-)typ. Eftersom mängder är så lika listor, förutom de nyss nämnda skillnaderna, är en enkel variant att använda listor för att hålla reda på vilka element som finns i mängden, men att skriva operationerna på den abstrakta datatypen , så man vet att listan alltid representerar en korrekt mängd.

Tänk på att det kan vara lättare använda datatype i stället för abstype under programutveckling och felsökning, och att göra om det hela till abstype först när man är klar.

OBS! Notera att körexemplen i den här uppgiften blir av en mer abstrakt typ, eftersom abstype-typer inte kan visas upp. I exemplen kommer mängder att skrivas {a, b, c}, men det är alltså inte så det faktiskt ser ut. Använder du datatype skall du få en lista istället som innehåller samma element men i godtycklig ordning. När du byter till abstype kommer du förstås inte att se något alls av hur datastrukturen egentligen ser ut.

Du ska skapa primitiver för att hantera mängder. Tänk på att en invariant för hur du representerar mängder är att den interna listan aldrig får innehåller några dubletter.

• Konstruktorer:
  • Skapa en identifierare emptySet som är bunden till en tom mängd.
  • Lägg till ett element till en mängd: addToSet: (''a * ''a set) -> ''a set. Tänk på att om ett element redan finns i mängden ska det inte läggas till till igen.
  Exempel:

  - emptySet;
  > val 'a it = { } : 'a set
  - addToSet("a" , emptySet});
  > val it =  {"a"} string set
  - addToSet("b" , it);
  > val it =  {"a", "b"} string set
  - val x = addToSet("a" , it);
  > val x =  {"a", "b"} string set
  

  Observera att x här binds till mängden {"a","b"}. Det används i exemplen nedan.
• Selektorer
  • Tag bort ett element från en mängd: removeFromSet: (''a * ''a set) -> ''a set. Om ett element inte finns i mängden skall det inte ha någon effekt att ta bort det.
  • Ta fram en lista på alla element i mängden: listOfElements: ''a set -> ''a list. Ordningen spelar ingen roll.
  • Ta fram antalet element i mängden: cardinality: ''a set -> int.
  Exempel:

  - removeFromSet("a" , x);
  > val it =  {"b"} string set
  - removeFromSet("c" , x);
  > val it =  {"a","b"} string set
  - listOfElements(x);
  > val it =  ["a", "b"] : string list
  - cardinality(x);
  > val it =  2 : int
  

• Predikat
  • Är två mängder lika, dvs innehåller de exakt samma element: equalSets: (''a set * ''a set) -> bool
  • Finns ett element i en mängd: memberOfSet: (''a * ''a set) -> bool
  Exempel:

  - addToSet("b", emptySet);
  > val it = {"b"} : string set;
  - addToSet("a", it);
  > val it = {"b,a"} : string set;
  - equalSets(x, it);
  > val it = true : bool
  - equalSets(x, emptySet);
  > val it = false : bool
  - memberOfSet("a", x);
  > val it = true : bool
  - memberOfSet("c", x);
  > val it = false : bool
  

Problem 2

Givet ovanstående primitiver, men utan att utnyttja att du vet hur mängder ser ut "inuti", definiera följande funktioner utanför datatypen:

• Är en mängd en delmängd av en annan mängd, finns den första mängdens alla element även med i den andra mängden? isSubset: (''a set * ''a set) -> bool
• En funktion listToSet: ''a list -> ''a set som givet en godtycklig lista med element returnerar en mängd med samma element.
• En funktion unionSet: (''a set * ''a set) -> ''a set som givet två mängder returnerar unionen av dem, dvs en ny mängd med de element som finns i någon av de två mängderna.
• En funktion intersectionSet: (''a set * ''a set) -> ''a set som givet två mängder returnerar snittet av dem, dvs en ny mängd med bara de element som fanns i båda de ursprungliga mängderna.

Exempel:

- isSubset(x, x);
> val it = true : bool
- isSubset(addToSet("a",emptySet), x);
> val it = true : bool
- val y = addToSet("b", addToSet("c", emptySet));
> val y = {"c", "b"} : string set
- isSubset(y, x);
> val it = false : bool
- listToSet(["a","b"])
> val it = {"a","b"} : string set
- unionSet(x, y)
> val it = {"a", "b", "c"} : string set
- intersectionSet(x, y);
> val it ={"b"} : string set

Inlämning

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