Programowanie funkcyjne/Struktury danych/Ćwiczenia

From Studia Informatyczne

Praca domowa

  • Napisz procedurę dubluj, która dubluje elementy listy, na przykład dubluj [1;2;3] = [1;1;2;2;3;3].
  • Punkty (kratowe) na płaszczyźnie reprezentujemy jako pary liczb całkowitych. Prostokąty o bokach równoległych do osi układu współrzędnych reprezentujemy jako pary punktów: dolny lewy i górny prawy róg. Napisz procedurę, która dla dwóch danych prostokątów wyznacza ich przecięcie. Podaj w jaki sposób reprezentowany jest zbiór pusty.
  • Zadeklaruj wariantowy typ danych reprezentujący abstrakcyjną składnię wyrażeń arytmetycznych. Napisz procedurę obliczającą wartość wyrażenia.

Ćwiczenia

Ćwiczenie [rev]

Zaimplementuj procedurę rev odwracającą listę. (Zwróć uwagę, że rozwiązując to zadanie można korzystać z :: lub @, co daje liniową lub kwadratową złożoność czasową.)

Rozwiązanie nieefektywne, ale proste

let rec rev l = 
  match l with
    [] -> [] |
    h::t -> (rev t) @ [h];;

Ze względu na koszt operacji @ to rozwiązanie ma złożoność czasową kwadratową.

Rozwiązanie efektywne

let rev l = 
  let rec pom l w = 
    match l with
      [] -> w |
      h::t -> pom t (h::w)
  in
    pom l [];;

Ćwiczenie [Przeplot list]

Napisz procedurę shuffle: α list → α list → α list, która dla danych dwóch list postaci [x_1; x_2; \dots; x_n] oraz [y_1; y_2; \dots; y_m] wyznaczy listę postaci [x_1; y_1; x_2; y_2; \dots]. Jeżeli jedna z list jest dłuższa, to jej końcowe elementy trafiają na koniec listy wyikowej. Na przykład: shuffle [3; 2; 8; 1; 9; 3; 6] [5; 7; 0] = [3; 5; 2; 7; 8; 0; 1; 9; 3; 6].


Ćwiczenie [flatten]

Napisz procedurę flatten rozwijającą listę list do listy elementów. Na przykład, flatten [[1; 2]; []; [3; 4; 5]] = [1; 2; 3; 4; 5].

Rozwiązanie

let rec flatten l = 
  match l with
    [] -> [] |
    h::t -> h @ flatten t;;

Ćwiczenie [Średnica drzew]

Dana jest definicja typu: type tree = Node of tree * tree | Leaf. Odległością między dwoma wierzchołkami (Node) w drzewie nazywamy minimalną liczbę krawędzi jakie trzeba przejść z jednego wierzchołka do drugiego. Średnicą drzewa nazwiemy maksymalną odległość między dwoma węzłami (Node) w drzewie. Przyjmujemy, że średnica pustego drzewa (Leaf) jest równa 0. Napisz procedurę srednica: tree -> int, która oblicza średnicę danego drzewa.

Rozwiązanie

Opieramy się na następującej obserwacji:

  • Puste drzewo ma średnicę 0.
  • Jeśli drzewo jest niepuste, to przez t_1 i t_2 oznaczmy dwa poddrzewa zakorzenione w lewym i prawym synie korzenia. Odpowiednio przez d_1 i d_2 oznaczmy średnice tych poddrzew, a przez h_1 i h_2 ich wysokości. Wówczas średnica całego drzewa wynosi \max(d_1, d_2, h_1+h_2+2).

Dla każdego wierzchołka w drzewie obliczamy wysokość i średnicę drzewa zakorzenionego w tym wierzchołku. Przyjmujemy przy tym, że drzewo puste ma średnicę 0 i wysokość -1.

let rec wys_sr t = 
  match t with 
    Leaf -> (-1,0) |
    Node (t1, t2) -> 
      let (h1, d1) = wys_sr t1
      and (h2, d2) = wys_sr t2
      in (max h1 h2 + 1, max (max d1 d2) (h1+h2+2));;

let srednica t = snd (wys_sr t);;

Ćwiczenie [Drzewa dowolnego stopnia]

Zdefiniuj typ reprezentujący drzewa o wierzchołkach dowolnego (skończonego) stopnia. Zdefiniuj trochę procedur operujących na takich drzewach, np. procedury wyznaczające listy elementów w porządku prefiksowym i postfiksowym.

Laboratorium

Ćwiczenia programistyczne na listy:

Ćwiczenie [n-ty element listy]

Zaimplementuj procedurę zwracającą n-ty element listy.

Rozwiązanie

 let rec nth l n =
   match l with
     h::t ->
       if n = 0 then h else nth t (n-1);;

Ćwiczenie [Lista [0;1;\dots;n]]

Napisz procedurę tworzącą listę n pierwszych liczb naturalnych.

Rozwiązanie

 let naturalne n =
   let rec pom k =
     if k >= n then [] else k :: pom (k+1)
   in pom 0;;

Ćwiczenie [append]

Zaimplementuj procedurę append sklejającą listy.

Rozwiązanie

 let rec append l1 l2 =
   match l1 with
     []   -> l2 |
     h::t -> h :: append t l2;;

Ćwiczenie [ciąg różnicowy]

Ciąg różnicowy ciągu (x_1, \dots, x_n) to ciąg postaci (x_2-x_1,\dots,x_n-x_{n-1}). Napisz procedurę obliczającą ciąg różnicowy żądanej listy liczb całkowitych.

Rozwiązanie

 let rec roznicowy l =
   match l with
     h1::(h2::_ as t) -> (h2-h1) :: roznicowy t |
     _                -> [];;

Rozwiązanie

 let roznicowy l =
   let rec pom a l =
     match l with
       h1::(h2::_ as t) -> pom ((h2-h1)::a) t |
       _                  -> rev a
   in pom [] l;;

Ćwiczenie [ciąg ciągów różnicowych]

Napisz procedurę obliczającą listę kolejnych ciągów różnicowych zadanej listy liczb całkowitych, tzn.: daną listę, jej ciąg różnicowy, ciąg różnicowy ciągu różnicowego itd.

Rozwiązanie

 let rec roznicowe l =
   if l = [] then [[]] else l :: roznicowe (roznicowy l);;

Ćwiczenie [minimum-maksimum]

Napisz procedurę, której wynikiem jest para: minimum i maksimum elementów z listy. Procedura ta powinna wykonywać co najwyżej \frac{3}{2} n porównań.

Ćwiczenie [last]

Napisz procedurę last, której wynikiem jest ostatni element (niepustej) listy.

Rozwiązanie

 let rec last (h::t) = 
   if t = [] then h else last t;;

Ćwiczenie [head i tail]

Napisz procedury head i tail, które dla zadanej listy l i liczby całkowitej n zwracają pierwsze/ostatnie n elementów listy l. Jeśli lista l ma mniej elementów niż n, to wynikiem powinna być cała lista l. (Nazwy pochodzą od programów head i tail w Uniksie.) Co jest wynikiem tail (head l n) 1?

 let head l n = 
   let rec head_pom l n a = 
     if (n = 0) || (l = []) then 
       rev a
     else
       head_pom (tl l) (n-1) ((hd l)::a)
   in head_pom l n [];;
 
 let tail l n = 
   let rec skip l k = 
     if k = 0 then l else skip (tl l) (k-1)
   in
     skip l (max (length l - n) 0);;  

Ćwiczenie [sortowanie]

Zaimplementuj sortowanie: przez scalanie lub quick-sort.

Ćwiczenie [arytmetyka nieograniczonych liczb całkowitych]

Zaimplementuj pakiet arytmetyczny nieograniczonych liczb całkowitych.

Ćwiczenie [lista większościowa]

Lista większościowa to taka lista, na której ponad połowa elementów jest sobie równa, a ich wartość nazywa się właśnie większością. Napisz procedurę wybierającą większość z listy większościowej; uzasadnij jej poprawność.

 let majority l = 
   let rec scan c k l = 
     match l with
       [] -> c |
       h::t -> 
         if k = 0 then scan h 1 t 
         else if c = h then scan c (k+1) t
         else scan c (k-1) t
 in scan (hd l) 0 l;;

Ćwiczenie [trójki]

Napisz procedurę trójki:int list -> (int * int * int) list, która dla zadanej listy dodatnich liczb całkowitych, uporządkowanej rosnąco, stworzy listę takich trójek (a, b, c) liczb z danej listy, że:

  • a < b < c,
  • liczby a, b i c spełniają nierówność trójkąta, czyli c < a + b.


Ćwiczenia na inne struktury danych:

Ćwiczenie [arytmetyka liczb wymiernych]

Zaimplementuj arytmetykę liczb wymiernych, reprezentując liczby wymierne jako rekordy złożone z licznika i mianownika. Implementacja może być uproszczona, np. bez skracania ułamków i bez normalizacji znaków.

Ćwiczenie [reprezentacja daty]

Zdefiniuj typ reprezentujący dni tygodnia, miesiące i datę.

Ćwiczenie [dzień tygodnia]

Zdefiniuj procedurę obliczającą na podstawie daty dzień tygodnia. Możesz założyć, że dana jest procedura sylwester, która na podstawie roku określa jakiego dnia tygodnia był Sylwester.

Ćwiczenie [słaby warunek BST]

Napisz procedurę, która dla dowolnego drzewa binarnego poprawia je tak, że spełnia ono słabszą wersję warunku BST: dla dowolnego węzła, lewy syn nie jest większy, a prawy nie jest mniejszy niż węzeł.

Ćwiczenie [wyważanie drzewa BST]

Napisz procedurę, która przekształca dane drzewo binarne w wyważone drzewo binarne, zachowując kolejność elementów w porządku infiksowym.

Ćwiczenie [zbiory jako drzewa BST]

Zaimplementuj takie operacje na zbiorach (reprezentowanych jako drzewa BST) jak suma, przecięcie i różnica.

Ćwiczenie [kolejki dwustronne]

Rozszerz implementację kolejek o wkładanie i wyjmowanie elementów z obydwu stron. Jaką własność powinna zachowywać procedura balance, aby koszt zamortyzowany operacji był stały?

Ćwiczenie [liczby naturalne]

Dany jest typ danych reprezentujący (mało efektywnie) liczby naturalne:
 type nat = ZERO | SUCC of nat;;

Zaimplementuj operacje arytmetyczne na takich liczbach.