Tuples en associatielijsten

Tuples

Opdracht:

• Tik ("Jan", 14) in.
• OCaml antwoordt met - : string * int = ("Jan", 14). Dit is een tuple (een geordend n-tal) bestaande uit een stuk tekst en een geheel getal.
• Tik let (naam, leeftijd) = ("Jan", 14) in.
• OCaml antwoordt met naam : string = "Jan" en leeftijd : int = 14.

Opdracht:

• Tik let eerste paar = let (x, y) = paar in x in.
• Tik eerste (1, 2) in.
• OCaml antwoordt met 1.

Oefening:

• Definieer een functie splits zodanig dat splits [1;2;3;4;5] evalueert tot ([1;3;5], [2;4]), en splits [2;3;4;5;6] evalueert tot ([2;4;6], [3;5]).

Oefening:

• Definieer een functie merge (Engels voor samenvoegen) die, gegeven twee gesorteerde lijsten, de gecombineerde gesorteerde lijst berekent. Bijvoorbeeld: merge [2; 4; 6] [1; 3; 5] = [1; 2; 3; 4; 5; 6]. Zorg ervoor dat deze functie een lineaire uitvoeringstijd heeft; m.a.w., zorg ervoor dat het aantal evaluatiestappen een lineaire functie is van de lengte van de invoerlijsten. In het bijzonder mag je niet de eerder gedefinieerde functie sorteer gebruiken!

Oefening:

• Definieer een functie merge_sort die een gegeven lijst sorteert door ze eerst te splitsen in twee ongeveer even grote deel-lijsten, door middel van de functie splits, dan beide deel-lijsten te sorteren door middel van een recursieve oproep van merge_sort, en dan de resulterende gesorteerde lijsten samen te voegen met merge.

De uitvoeringstijd van de functie merge_sort is O(N*log(N)). Inderdaad: als M(N) het aantal evaluaties van merge is, gegenereerd door een evaluatie van merge_sort xs, waarbij xs een lijst van lengte N is, dan bestaat er een constante C zodanig dat voor alle voldoende grote N geldt dat M(N) <= C * N * log(N). Dit is een betere asymptotische uitvoeringstijd dan het sorteeralgoritme met invoeging dat we hierboven zagen.

Associatielijsten

Oefening:

• Definieer een functie zoek_op, zodanig dat zoek_op "Jan" [("Piet", 14); ("Jan", 16)] evalueert tot 16.

Oefening:

• Definieer een functie verwijder_associatie, zodanig dat verwijder_associatie "Jan" [("Piet", 14); ("Jan", 16)] evalueert tot [("Piet", 14)].