Lijsten

Lijsten

Opdracht:

• Tik [10; 20; 30; 40] in.
• OCaml antwoordt met - : int list = [10; 20; 30; 40]. Het type int list is het type van lijsten van gehele getallen.

Opdracht:

• Tik 10::20::30::40::[] in.
• OCaml antwoordt met - : int list = [10; 20; 30; 40]. De uitdrukking e::l betekent: de lijst bestaande uit het element e gevolgd door de lijst l. Het eerste element van een (niet-lege) lijst noemen we het hoofd en de elementen ná het eerste element de staart. De uitdrukking e::l betekent dus: de lijst met hoofd e en staart l.

Opdracht:

• Tik let aftelling_0 = [0] in.
• OCaml antwoordt met aftelling_0 : int list = [0].
• Tik let aftelling_1 = 1::aftelling_0 in.
• OCaml antwoordt met aftelling_1 : int list = [1; 0].
• Tik let aftelling_2 = 2::aftelling_1 in.
• OCaml antwoordt met aftelling_2 : int list = [2; 1; 0].
• Tik let aftelling_3 = 3::aftelling_2 in.
• OCaml antwoordt met aftelling_3 : int list = [3; 2; 1; 0].

Oefening:

• Definieer een functie aftelling zodanig dat aftelling 2 evalueert tot [2; 1; 0] en aftelling 4 evalueert tot [4; 3; 2; 1; 0].

Opdracht:

• Tik let leeg xs = match xs with [] -> true | hoofd::staart -> false in.
• Tik dan leeg [] in.
• OCaml antwoordt met - : bool = true.
• Tik dan leeg [10] in.
• OCaml antwoordt met - : bool = false. Je kan een match-uitdrukking gebruiken om verschillende berekeningen te doen afhankelijk van de vorm van een lijst. Meer bepaald: de uitdrukking match xs with [] -> U1 | hoofd::staart -> U2 evalueert tot de waarde van U1 als xs een lege lijst is, en tot de waarde van U2, waarbij hoofd gebonden wordt aan het hoofd (eerste element) van xs en staart aan de staart van xs (de lijst die je krijgt door het eerste element van xs weg te laten), als xs niet leeg is.

Opdracht:

• Tik let som_eerste_twee xs = match xs with eerste::tweede::_ -> eerste + tweede in.
• Tik dan som_eerste_twee [10; 20; 30] in.
• OCaml antwoordt met - : int = 30.
• Tik dan som_eerste_twee [10] in.
• OCaml antwoordt met Exception: Match_failure. Als je in een match-uitdrukking niet alle gevallen behandelt, krijg je een waarschuwing. Als je dan de uitdrukking evalueert voor een geval dat niet behandeld wordt, krijg je een uitzondering (exception in het Engels).

Opdracht:

• Tik let hoofd_van xs = match xs with hoofd::staart -> hoofd in.
• Tik dan hoofd_van [1;2;3] in.
• OCaml antwoordt met - : int = 1.
• Tik dan hoofd_van [10;20] in.
• OCaml antwoordt met - : int = 10.

Opdracht:

• Tik let staart_van xs = match xs with hoofd::staart -> staart in.
• Tik dan staart_van [1;2;3] in.
• OCaml antwoordt met - : int list = [2;3].
• Tik dan staart_van [10;20] in.
• OCaml antwoordt met - : int list = [20].

Oefening:

• Definieer een functie lengte zodanig dat lengte [true; false] evalueert tot 2 en lengte ["Hallo"] evalueert tot 1 en lengte [1.0; 2.0; 3.0] evalueert tot 3.

Merk op:

lengte ["a"; "b"; "c"]
= lengte ("a"::"b"::"c"::[])
= lengte ("a"::("b"::("c"::[])))
= 1 + lengte ("b"::("c"::[]))
= 1 + (1 + lengte ("c"::[]))
= 1 + (1 + (1 + lengte []))
= 1 + (1 + (1 + 0))
= 3

Oefening:

• Definieer een functie som zodanig dat som [1; 2; 3] evalueert tot 6 en som [7; 3; 11] evalueert tot 21.

Oefening:

• Definieer een functie filter_pos zodanig dat filter_pos [10; -3; 5] evalueert tot [10; 5] en filter_pos [-7; 0; 8] evalueert tot [8].

Oefening:

• Definieer een functie negatie zodanig dat negatie [10; -20] evalueert tot [-10; 20].

Oefening:

• Definieer een functie aan_elkaar zodanig dat aan_elkaar [1; 2] [3; 4] evalueert tot [1; 2; 3; 4].

Oefening:

• Definieer een functie alles_aan_elkaar zodanig dat alles_aan_elkaar [[10; 20]; [30; 40]; [50]] evalueert tot [10; 20; 30; 40; 50].

Oefening:

• Definieer een functie voeg_in die, gegeven een geheel getal en een gesorteerde lijst van gehele getallen, de gesorteerde lijst berekent die je bekomt als je het element op de juiste plaats invoegt in de gegeven gesorteerde lijst.

Oefening:

• Definieer een functie sorteer zodanig dat sorteer [3; 1; 2] evalueert tot [1; 2; 3]. Hint: gebruik de functie voeg_in.

Merk op dat de functie sorteer een kwadratische uitvoeringstijd heeft: het aantal evaluaties van voeg_in gegenereerd door een evaluatie van sorteer xs, waarbij xs een lijst van lengte N is, is in het slechtste geval N + (N - 1) + ... + 1 = N*(N+1)/2. Dit betekent dat de uitvoeringstijd sterk toeneemt naarmate de lengte van de te sorteren lijst toeneemt. Later zullen we efficiëntere sorteeralgoritmes zien.