Programowanie funkcyjne/Programowanie imperatywne/Ćwiczenia

Praca domowa

Ćwiczenie [BST]

Zastosuj metodę spaceru do sprawdzenia, czy drzewo jest drzewem BST.

Ćwiczenie [Append]

Zaimplementuj modyfikowalne listy i procedurę append, która modyfikuje daną listę przez dołączenie na jej końcu innej listy. Dołączana lista jest przy tym niszczona. Procedura append powinna działać w stałym czasie. (Lista powinna zawierać referencje do obu jej końców).

Ćwiczenie [Odwracanie listy]

Napisz procedurę, która odwraca zadaną listę modyfikowalną. Dwukrotne odwrócenie powinno dawać listę tożsamą z początkową. Należy to zrobić w stałej pamięci dodatkowej i liniowym czasie.

Ćwiczenia

Ćwiczenie [Listy cykliczne]

Zaimplementuj cykliczne listy modyfikowalne.

Ćwiczenie [Wykrywanie cykli]

Napisz procedurę sprawdzającą, czy dana lista zawiera cykl. Można to zrobić w stałej pamięci i liniowym czasie (i to na kilka sposobów!).

Laboratorium

Ćwiczenie [FIFO]

Zaimplementuj imperatywną kolejkę FIFO.

Ćwiczenie [Kolejki dwustronne]

Zaimplementuj imperatywne kolejki dwustronne z dodatkowymi operacjami odwracania i sklejania kolejek. Wszystkie operacje powinny działać w czasie stałym.

Ćwiczenie [Find-union]

Zaimplementuj drzewa find-union.

Rozwiązanie

 (* Typ klas elementów typu 'a. *)
 type 'a set = { 
   up           : 'a set ref;   (* Przodek w drzewie find-union (referencja).       *)
   mutable rank : int;          (* Ranga w drzewie find-union (modyfikowalne pole). *)
 };;
 
 (* Tworzy nową klasę złożoną tylko z danego elementu. *)
 let make_set () = 
   let rec v = { up = ref v; rank = 0; }
   in v;;
 
 (* Znajduje reprezentanta danej klasy, kompresując ścieżkę. *)
 let rec find s = 
   if s == !(s.up) then s 
     else begin
       s.up := find !(s.up);
       !(s.up)
     end;;
 
 (* Scala dwie dane (rozłączne) klasy. *)
 let union x y = 
   let fx = find x 
   and fy = find y
   in
     if not (fx == fy) then begin
       if fy.rank > fx.rank then
         fx.up := fy
       else begin
         fy.up := fx;
         if fx.rank = fy.rank then fx.rank <- fy.rank + 1
       end
     end;;