Warning! This is the 2012 course's website! You probably want the current course website.

Laboration 3. Rödsvarta träd i Haskell

Det här laborationen går ut på att konstruera ett rödsvart träd i Haskell, för att få en jämförelse med hur det ser ut i Java.

Syftet med laborationen är att

• ge övning i att jämföra det objektorienterade synsättet med det värdeorienterade,
• ge övning i att definiera moduler i Haskell och
• ge övning i rekursiv nedstigning i rekursiva datastrukturer.

Uppgift

Uppgiften är ganska enkel att beskriva. Ni skall definiera och testköra ett rödsvart träd.

Er slutliga kod ska innehålla två filer, RedBlackTree.hs och Main.hs:

• RedBlackTree.hs är själva sökträdsmodulen. Den ska implementeras som en Haskell-modul och exportera samma funktioner som BinSearchTree och AVLTree i Haskell-kompendiet. Dessutom ska följande två funktioner exporteras:

  • size : RBTree a –> Int, ska returnera antalet noder i trädet;
  • maxheight : RBTree a –> Int, ska returnera den maximala höjden, dvs. den längsta vägen från roten till något löv.

  Ni behöver inte göra någon effektiv implementation av de två funktionerna. Det finns en skelettfil att utgå ifrån.

  I filen finns funktionen checkTree fördefinierad. Den kontrollerar att ett träd uppfyller alla krav som kan ställas på rödsvarta träd. Tyvärr så är den inte fullständigt implementerad… Ni behöver slutföra följande hjälpfunktioner:

  • isSorted : Ord a => [a] –> Bool, som kontrollerar att en lista är sorterad;
  • checkRedParents : RBTree a –> Bool, som kontrollerar att alla röda noder bara har svarta barn.

  Slutligen: Funktionen remove är frivillig, men alla andra funktioner ska implementeras!

• Main.hs är huvudprogrammet. Det ska läsa in ord från standard input och bygga ett träd av dem. Sedan ska trädets storlek (n) och höjd (h) beräknas och skrivas ut, den optimala höjden (h' = ⎡log₂(n+1)⎤), ska beräknas och skrivas ut, och kvoten (h/h') mellan den aktuella höjden och den optimala höjden ska skrivas ut. (I ett korrekt implementerat rödsvart träd är kvoten aldrig större än 2). Dessutom ska trädet testas med funktionen checkTree, och resultatet ska skrivas ut. Slutligen ska de första 20 orden i trädet skrivas ut i bokstavsordning.

  OBS! Ställ upp utskriften någorlunda snyggt, så att den blir läsbar för labrättaren.

  Orden i indata separeras av mellanslag och/eller nyrad. Ett enkelt sätt att läsa in orden är med standardfunktionerna getContents och words.

Testning

Fundera först ut några enkla testexempel, som tillsammans går igenom samtliga rotationer. Ett förslag är att testa med meningen "The quick brown fox jumps over the lazy dog", eftersom det finns ett "facit" i kursboken.

Det finns en testfil, CheckInsert.hs, som ni kan använda. Det programmet bygger träd från alla möjliga permutationer av listor upp till längd 9. Varje träd testas sedan om det uppfyller invarianterna genom att anropa funktionen checkTree.

Testa sedan mot följande två filer:

• swahili-small.txt (400KB stor): en förminskad variant av textfilen från inlämningsuppgift 2, som "bara" har ca 65 000 ord, varav 12 600 är unika
• sorted-small.txt (100KB stor): de 12 600 unika orden från swahili-small.txt, sorterade i bokstavsordning

Alla filer (både Haskell-skelettfiler och korpusar) kan hämtas som ett stort zip-arkiv.

Dokumentation

De två Haskellfilerna ska lämnas in, välkommenterade som vanligt.