DM22-2002

DM22 - Obligatorisk opgave 1
Tips & hjælp

Hermed en lille disposition til jeres rapport. Af omfang forventer vi at få cirka tre-fem sider (excl. forside).

Forside
Indledning
Skriv om hvad det hele går ud på
Analyse/design
Skriv hvordan I vil lave / har lavet det hele. Herunder skal der være tidskompleksisteter for de enkelte operationer (fx. at insert kører i tid O(log n). Hvis jeres algoritme ikke er optimal, skal optimal køretid også angives.
Test
Det vigtigste er nok, at teste at de rød-sorte træer er lavet godt nok, dvs. test bl.a. efter, at alle blade har samme "sorte afstand" til roden, samt at der aldrig er to røde knuder i træk.
Men der skal også testes, at alle de andre funktioner virker...
Husk udskrift af test-program og test-kørsel.
Konklusion
Hvordan gik det hele? Evt. kort om, hvordan noget af det kan laves bedre.

Ud over rapporten, skal I aflevere en udskrift af jeres program. Derudover skal I sende en email med programmet til adressen svalle@imada.sdu.dk.

Der er flere, der har problemer med, at deres funktioner ikke virker for "tomme træer"; dette kan fx. give sig udslag i følgende fejlmeddelse:
```
  RBTree> show Nil
  ERROR - Unresolved overloading
  *** Type       : Show a => [Char]
  *** Expression : show Nil
```
Problemet skyldes at, at Hugs ikke kan finde ud af, præcis hvilken type Nil har; blot at den har typen RBTree a, hvor Hugs ikke ved, om a kan skrives ud... Derfor: Lav et type-cast af det tomme træ til en træ-type, der kan skrives ud, fx.:
```
  RBTree> show (Nil::RBTree Int)
  "Nil"
```
Kapitel 16.7 indeholder almindelige søgetræer. Brug evt. dem som udgangspunkt til de rød-sorte træer.
I får sikkert brug for at lave en funktion, der tager indholdet i jeres træ og laver en liste ud af det. Det problem har vi tidligere løst i opgave 14.25.
En god idé vil være at dele jeres program op i (mindst) tre dele:
- Et modul der implementerer rød-sorte-træer.
- Et modul der implementerer mængder (fra 16.8) oven på de rød-sorte træer.
- Et test-modul, der tester de andre to moduler.
Til testen kan det være en god idé at lave et program som flg.:
```
  module Main where
  main :: IO ()
  main =
    do t0 <- return emptyTree
       print "Empty tree: "
       print (show t0)
       ...
```
Hvis I lægger programmet i Main.hs, kan det dernæst køres som runhugs Main.