Ćwiczenia 9 i 10: Procedury wyższych rzędów i listy

Ćwiczenia na listy z elementami procedur wyższych rzędów:

  1. Napisz procedurę exists, która dla danego predykatu i listy sprawdzi, czy na liście jest element spełniający predykat.
    Wykorzystaj wyjątki tak, aby nie przeglądać listy, gdy to już nie jest potrzebne.
  2. Napisz procedurę negującą predykat non: (α → bool) → (α → bool).
    Za pomocą tej procedury oraz procedury exists zdefiniuj procedurę forall,
    która sprawdza, czy dany predykat jest spełniony przez wszystkie elementy danej listy.
    Czy zastosowanie wyjątków w implementacji procedury exists nadal powoduje, że przeglądane są tylko niezbędne elementy listy?
  3. Zapisz procedurę append za pomocą fold_right/fold_left.
  4. Napisz procedurę obliczającą funkcję będącą złożeniem listy funkcji.
  5. Zapisz za pomocą map i flatten procedurę heads,
    której wynikiem dla danej listy list, jest lista pierwszych elementów niepustych list składowych.
    Puste listy składowe nie powinny wpływać na wynik.
  6. Napisz procedurę sumy : int list → int list, która dla danej listy \([x_1;\dots; x_n]\)
    oblicza listę postaci: \([x_1; x_1 + x_2; x_1+x_2+x_3; \dots; x_1+x_2+\cdots+x_n]\).

    Przykład: sumy [1; 5; 2; 7; 12; 10; 5] = [1; 6; 8; 15; 27; 37; 42].
  7. Napisz procedurę codrugi : α list → α list, która z danej listy wybiera co drugi element (zaczynając od drugiego).
    Na przykład codrugi [1; 2; 3; 4; 5] = [2; 4].
  8. Listę nazwiemy ciekawą jeśli żadne dwa kolejne jej elementy nie są sobie równe.
    Napisz procedurę podzial : α list → α list list, która daną listę podzieli na
    minimalną liczbę spójnych fragmentów (zachowując ich kolejność), z których każdy jest ciekawy.
    Na przykład, podzial [3;2;2;5;7;5;4;4;3;1] = [[3;2];[2;5;7;5;4];[4;3;1]].
  9. Dana jest lista liczb całkowitych. Element tej listy nazwiemy prextremum jeśli jest ostro większy lub ostro mniejszy od wszystkich elementów poprzedzających go na danej liście.
    Napisz procedurę \(\mathtt{prextrema}: \mathtt{int~list} \to \mathtt{int~list}\), która dla danej listy zwraca listę wszystkich jej prextremów.
    Elementy na liście wynikowej powinny być w takiej samej kolejności, w jakiej występowały na danej liście.
    Na przykład:
    prextrema [-2; 1; 0; 1; 3; 2; -1; 5; 4; -3; 2; 1; 7] = [-2; 1; 3; 5; -3; 7]
  10. Napisz procedurę \(\mathtt{wzrost}: \mathtt{int~list} \to \mathtt{int~list}\), która dla danej listy liczb całkowitych
    znajduje w niej najdłuższy spójny fragment ściśle rosnący i zwraca go.
    Na przykład:

     
          wzrost [3; 4; 0; -1; 2; 3; 7; 6; 7; 8] = [-1; 2; 3; 7]
          wzrost [] = []
     
  11. Dana jest lista \([x_1; x_2; \dots; x_n]\) reprezentująca kolejne chwile w czasie -- tzn. $x_i\) reprezentuje chwilę \(i\).
    Dane są też dwa predykaty \(p\) i \(q\).
    Powiemy, że w chwili \(i\) zachodzi ,,\(p\) dopóki \(q\)'', jeżeli istnieje takie \(0 \le k \le n-i\), że
    zachodzi \(p\ x_i, p\ x_{i+1}, \dots, p\ x_{i+k-1}\), oraz \(q\ x_{i+k}\).
    Inaczej mówiąc, począwszy od chwili \(i\) musi zachodzić \(p\), dopóki nie zajdzie \(q\).
    W szczególności, jeżeli zachodzi \(q\ x_i\), to \(p\) nie musi w ogóle zachodzić.

    Napisz taką procedurę dopoki : α list → (α → bool) → (α → bool) → int list, że wynikiem
    \(\mathtt{dopoki}\ [x_1; x_2; \dots; x_n]\ p\ q\) jest lista tych chwil w czasie, w których zachodzi \(p\) dopóki \(q\).

    Na przykład, dla następujących \(p\) i \(q\):

    \(i\) 1 2 3 4 5 6 7 8 9 10 11 12
    \(p\ x_i\) false true true true false false true true true false false false
    \(q\ x_i\) false false true false true false false true false false true false


    poprawnym wynikiem jest: \([2; 3; 4; 5; 7; 8; 11]\).
  12. Dla danej listy liczb całkowitych \(l = [x_1; x_2; \dots; x_n]\), minimum (maksimum) nazwiemy
    taki fragment listy \(x_i = x_{i+1} = \dots = x_j\), że:

    • \(1 \le i \le j \le n\),
    • jeśli \(i > 1\), to \(x_{i-1} > x_i\) (\(x_{i-1} < x_i\)),
    • jeśli \(j < n\), to \(x_j < x_{j+1}\) (\(x_j > x_{j+1}\)).

    Ekstremum oznacza minimum lub maksimum.
    Napisz procedurę ekstrema :int list → int, która dla danej listy policzy ile jest na niej ekstremów.

  13. System -2-kowy jest podobny do systemu binarnego, ale podstawą tego systemu jest liczba -2. Są dwie możliwe cyfry: 0 i 1.
    Ciąg cyfr postaci \(c_k c_{k-1} \dots c_1 c_0\) reprezentuje liczbę \(\sum_{i=0}^k c_i(-2)^i\).
    Na przykład, liczbę 42 reprezentujemy jako \(1111110_{-2}\).

    Napisz procedurę inc : int list → int list, która dla danej listy będącej reprezentacją liczby \(x\),
    wyznaczy reprezentację liczby \(x+1\).
    Przyjmujemy, że lista pusta reprezentuje 0.

  14. Maksymalne plateau w liście (bez rekurencji).
    Napisz procedurę plateau : α list → int, która oblicza długość najdłuższego stałego (spójnego) fragmentu danej listy.
  15. Zdefiniuj, za pomocą @ i filter uproszczoną wersję algorytmu quick-sort.
    W algorytmie tym elementy sortowanej listy dzielimy na nie większe i większe od pierwszego elementu listy,
    po czym obie listy wynikłe z podziału rekurencyjnie sortujemy.
  16. Ciąg różnicowy ciągu \([x_1; x_2; \dots; x_n]\), to ciąg postaci \([x_2-x_1; x_3-x_2; \dots; x_n-x_{n-1}]\).
    Oblicz ciąg różnicowy zadanej listy liczb całkowitych.
  17. Oblicz listę złożoną z pierwszych elementów kolejnych ciągów różnicowych danej listy,
    tzn.: głowy danej listy, gowy jej ciągu różnicowego, głowy ciągu różnicowego jej ciągu różnicowego itd.
  18. Dana jest lista liczb zmiennopozycyjnych \([x_1; x_2; \dots; x_n]\).
    Jej uśrednienie, to lista postaci: \([\frac{x_1 +. x_2}{2.0}; \dots; \frac{x_{n-1} +. x_n}{2.0}]\).
    Uśrednieniem listy jednoelementowej oraz pustej jest lista pusta.

    Napisz procedurę usrednienie : float list → float list, która dla danej listy obliczy jej uśrednienie.

  19. Napisz funkcję od_końca_do_końca : int list → int, która dla danej niepustej
    listy \([a_1;...;a_n]\) obliczy \(\min_{i=1,2,\dots,n} |a_i - a_{n+1-i}|\).
  20. Załóżmy, że dana jest lista \([x_1; x_2; \dots; x_n]\).
    Sufiksem tej listy nazwiemy każdą listę, którą można uzyskać przez usunięcie pewnej liczby (od 0 do \(n\)) jej początkowych elementów.
    Tak więc sufiksami danej listy będzie n.p. ona sama, pusta lista, a także \([x_3; x_4; \dots; x_n]\).

    Napisz (za pomocą fold_left/fold_right) procedurę tails : α list → α list list,
    która dla danej listy tworzy listę wszystkich jej sufiksów, uporządkowaną wg malejących ich długości.
  21. Rozważmy listę liczb całkowitych \([x_1; x_2; \dots; x_n]\).
    Dołkiem na tej liście nazwiemy taki indeks \(1 < i < n\), że \(x_i < \max(x_1, \dots, x_{i-1})\) oraz \(x_i < \max(x_{i+1}, \dots, x_n)\).
    Głębokość takiego dołka to \(\min(\max(x_1, \dots, x_{i-1}) - x_i, \max(x_{i+1}, \dots, x_n) - x_i)\).
    Napisz procedurę \(\mathtt{dolek}: \mathtt{int~list} \to \mathtt{int}\), która dla danej listy liczb całkowitych wyznaczy maksymalną głębokość dołka na tej liście.
    Jeśli na danej liście nie ma żadnego dołka, to poprawnym wynikiem jest 0.
  22. Lista trójek \([(l_1,s_1,r_1); \dots; (l_k,s_k,r_k)]\) : (α list * int * int) list} reprezentuję listę
    elementów typu α w następujący sposób.
    Trójka \((l,s,r)\), gdzie \(l = [x_1; x_2; \dots; x_s]\) jest \(s\)-elementową listą elementów typu α,
    reprezentuje ciąg \(r\)-elementowy, poprzez cykliczne powtarzanie elementów ciągu \(l\):
    \[\underbrace{x_1, x_2, \dots, x_s, x_1, x_2, \dots, x_s, x_1, \dots}_{r \mbox{ elementów}}\]
    Z kolei lista trójek reprezentuje listę powstała w wyniku konkatenacji list odpowiadających poszczególnym trójkom.

    Napisz procedurę dekompresja : (α list * int * int) list → int → α, która
    dla danej listy trójek i indeksu \(i\) wyznacza \(i\)-ty element listy wynikowej.
  23. Rozważmy następującą metodę kompresji ciągów liczb całkowitych:
    Jeżeli w oryginalnym ciągu ta sama liczba powtarza się kilka razy z rzędu, to jej kolejne wystąpienia reprezentujemy za pomocą jednej tylko liczby.
    Konkretnie, \(i\) powtórzeń liczby \(k\) reprezentujemy w ciągu skompresowanym jako \(2^{i-1} \cdot (2 \cdot k - 1)\).

    Napisz procedurę kompresuj : int list → int list kompresującą zadaną listę.
    Lista wynikowa powinna być oczywiście jak najkrótsza.

     
          kompresuj [1; 2; 2; 5; 11; 11; 2];;
          - : int list = [1; 6; 9; 42; 3]
     
  24. Napisz procedurę buduj_permutacje : α list list → α → α,
    która przyjmuje permutację w postaci rozkładu na cykle i zwraca ją w postaci procedury.

    Lista składowa postaci \([a_1; \dots; a_n]\), gdzie \(a_i \neq a_j\) dla \(1 \leq i < j \leq n\),
    reprezentuje cykl, czyli permutację przeprowadzającą \(a_i\) na \(a_{(i \bmod n) + 1}\) dla \(1 \leq i \leq n\).
    Możesz założyć, że listy składowe są niepuste.

    Lista list \([c_1; \dots; c_k]\), gdzie listy \(c_i\) dla \(1 \leq i \leq k\) reprezentują cykle, reprezentuje permutację złożoną z tych cykli.
    Możesz założyć, że wszystkie cykle są rozłączne.

    Przyjmujemy, że dla wartości \(x\) nie występujących na żadnej z list \(c_i\) mamy: buduj_permutacje \([c_0; \dots; c_k]\ x = x\).
    W szczególności, przyjmujemy, że pusta lista reprezentuje permutację identycznościową.

     
          let p = buduj_permutacje [[2; 1]; [8; 3; 4]; [5; 7; 6; 10]; [11]];;
          map p [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12];;
          -: int list = [2; 1; 4; 8; 7; 10; 6; 3; 9; 5; 11; 12]
     
  25. Napisz procedurę podzial : int list → int list list, która dla danej listy liczb całkowitych
    \(l=[x_1; x_2; \dots; x_n]\) podzieli ją na listę list \([l_1; \dots; l_k]\), przy czym:

    • \(l = l_1 @ \dots @ l_k\),
    • dla każdej listy \(l_i\) wszystkie elementy na takiej liście są tego samego znaku,
    • \(k\) jest najmniejsze możliwe.

    Przykład:

     
          podzial [1;3;0;-2;-2;-4;9] = [[1; 3]; [0]; [-2;-2;-4]; [9]]
     
  26. Lista jest monotoniczna jeśli jest niemalejąca lub nierosnąca.
    Napisz procedurę \(\mathtt{monotons}: \mathtt{int~list} \to \mathtt{int}\), która dla danej listy wyznaczy minimalną liczbę spójnych fragmentów, na które trzeba ją podzielić, tak żeby każdy fragment był monotoniczny. (Dla pustej listy poprawnym wynikiem jest zero.)
    Na przykład, monotons [2; 3; 3; 5; 0; -1; -7; 1; 3; 5; 5; 2; 4; 6] = 4.
    Daną listę można podzielić tak: [2; 3; 3], [5; 0; -1; -7], [1; 3; 5; 5], [2; 4; 6].
  27. Napisz procedurę \(\mathtt{prefiksy}: \mathtt{int~list} \to \mathtt{int~list~list}\), która dla danej listy liczb całkowitych
    zwróci listę wszystkich jej prefiksów zakończonych zerem, w kolejności rosnącej ich długości.
    Na przykład:

     
          prefiksy [0;1;2;3;0;5;6;0;1] = [[0]; [0;1;2;3;0]; [0;1;2;3;0;5;6;0]]