Ć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. Dana jest lista list elementów. Napisz procedurę \(\mathtt{ostatki}: \alpha\ \mathtt{list~list} \to \alpha\ \mathtt{list}\), która zwraca listę ostatnich elementów list składowych.
    Kolejność elementów w wyniku powinna być taka jak kolejność list składowych, z których pochodzą.
    Puste listy składowe nie wpływają na wynik.
  7. 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].
  8. 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].
  9. 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]].
  10. 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]
  11. 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 [] = []
     
  12. Dany jest ciąg \(n\) kulek ułożonych w rządku. Każda kulka jest czerwona lub zielona. Maciek chciałby ułożyć kulki naprzemiennie: zielona, czerwona, zielona itd. Niestety liczby kulek zielonych i czerwonych nie muszą być równe. Maćkowi wystarczy jeśli ciąg kulek będzie (od lewej) zaczynał się naprzemiennie od zielonej kulki. Natomiast pewien fragment ciągu kulek od prawej strony może być jednokolorowy. (W szczególności, jeśli w danym ciągu są kulki tylko jednego koloru, to wynikowy ciąg też musi być jednokolorowy.)
    Maciek w jednym ruchu może zamienić miejscami dowolnie dwie wybrane kulki w ciągu.
    Dana jest deklaracja typu: type kolor = Czerwona | Zielona.
    Napisz procedurę \(\mathtt{kulki}: \mathtt{kolor~list} \to \mathtt{int}\), która mając daną liste opisującą ciąg kulek (od lewej do prawej) wyznaczy minimalną liczbę ruchów, w jakich Maciek może ułożyć ciąg kulek tak jak to opisano.
    Na przykład: kulki [Czerwona, Zielona, Zielona, Zielona, Zielona, Czerwona, Czerwona, Zielona] = 2.
  13. 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]\).
  14. 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.

  15. 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.

  16. 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.
  17. 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.
  18. 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.
  19. 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.
  20. 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.

  21. 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}|\).
  22. 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.
  23. 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.
  24. 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.
  25. 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]
     
  26. 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]
     
  27. 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]]
     
  28. 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].
  29. 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]]
     
  30. Dany jest typ reprezentujący symbole tworzące wyrażenia arytmetyczne:

            type symbol = 
              | Liczba of int
              | Plus | Minus | Razy | Podziel
              | Nawias_Otw | Nawias_Zam
     

    Masz daną listę symboli tworzących poprawne wyrażenie arytmetyczne. Napisz procedurę \(\mathtt{kalkulator}: \mathtt{symbol~list} \to \mathtt{int}\), która obliczy wartość wyrażenia.
    Przyjmij, że, o ile nawiasy nie wymuszają innej kolejności, operacje arytmetyczne wykonujemy od lewej do prawej.
    Przykład:

            kalkulator [Nawias_Otw; Liczba 5; Plus; Liczba 4; Razy; 
                        Liczba 2; Plus; Liczba 3; Nawias_Zam; Razy; Liczba 2] = 42