Ćwiczenia na listy z elementami procedur wyższych rzędów:
-
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.
-
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?
-
Zapisz procedurę
append za pomocą fold_right/fold_left.
-
Napisz procedurę obliczającą funkcję będącą złożeniem listy funkcji.
-
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.
Rozwiązania
-
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.
-
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].
Rozwiązania
-
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].
-
Jaś pracuje wykonując zlecenia, które dostaje od swojego szefa. Wykonuje je w kolejności ich otrzymania. Wykonanie każdego zlecenia zajmuje mu określony czas. Masz daną tablicę par: moment otrzymania zlecenia, czas potrzebny na jego wykonanie, posortowaną ściśle rosnąco po momentach otrzymania zleceń.
Napisz procedurę \(\mathtt{zlecenia}: (\mathtt{int} * \mathtt{int})\ \mathtt{list} \to \mathtt{int~list}\), która dla każdego zlecenia wyznaczy ile czasu upłynie od momentu otrzymania zlecenia do momentu jego wykonania.
Na przykład: zlecenia [(-1, 1); (2, 2); (3, 3); (4, 2); (10, 2)] = [1; 2; 4; 5; 2]}.
Rozwiązania
-
Dany jest ciąg liczb całkowitych (niekoniecznie dodatnich). Element takiego ciągu nazwiemy widocznym, jeśli suma poprzedzających go elementów jest taka sama, jak suma elementów występujących po nim.
Napisz procedurę \(\mathtt{widoczne}:\mathtt{int~list} \to \mathtt{int~list}\), która z danej listy liczb całkowitych wybierze te, które są widoczne.
Rozwiązania
-
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]].
Rozwiązania
-
Napisz procedurę \(\mathtt{wybory}: \mathtt{int~list} \to \mathtt{int}\), która mając daną posortowaną niemalejąco listę liczb całkowitych, znajdzie liczbę która pojawia się na niej najwięcej razy (w przypadku takiej samej liczby wystąpień, wybierz największą taką liczbę).
Rozwiązania
-
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]
Rozwiązania
-
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 [] = []
Rozwiązania
-
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.
-
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]\).
-
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.
Rozwiązania
-
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.
-
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.
-
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.
Rozwiązania
-
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.
-
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.
-
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.
-
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}|\).
-
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.
-
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.
-
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.
-
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]
-
Listę nazwiemy dobrą, jeśli zawiera elementy o naprzemiennych znakach (dodatnie i ujemne).
Listę nazwiemy prawie dobrą, jeśli jest dobra lub zawiera co najwyżej jedno zero, a po obu jego stronach jest dobra.
Szukamy najdłuższego spójnego fragmentu danej listy liczb całkowitych, który jest prawie dobry.
Napisz procedurę \(\mathtt{prawie}: \mathtt{int~list} \to \mathtt{int}\), która zwraca długość takiego fragmentu.
Na przykład: prawie [3; 2; -2; 0; 42; 22; -12; 15; -4] = 4.
Są dwa takie fragmenty: [2; -2; 0; 42] i [22; -12; 15; -4].
-
Przy windzie (na parterze) ustawiła się kolejka ludzi, którzy chcą wjechać windą (wszyscy do góry). Jednorazowo windą mogą jechać osoby o łącznym ciężarze nie większym niż \(w\).
Do windy zawsze wsiada maksymalnie dużo osób z początku kolejki, których łączny ciężar nie przekracza \(w\).
Napisz procedurę winda: int → int list → int, która mając dane \(w\) oraz listę ciężarów kolejnych osób czekających na windę policzy minimalną liczbę kursów windy potrzebnych do obsłużenia czekających.
Możesz założyć, że ciężary osób czekających na windę są liczbami dodatnimi, nie większymi od \(w\).
Rozwiązując to zadanie, nie możesz tworzyć żadnych własnych procedur rekurencyjnych.
Zamiast tego należy wykorzystać standardowe procedury wyższych rzędów przetwarzające listy.
Rozwiązania
-
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]
-
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]]
Rozwiązania
-
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].
-
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]]
Rozwiązania
-
Prostokątną macierz reprezentujemy jako listę wierszy, a każdy wiersz jest listą elementów. Należy zaimplementować operację transpozycji macierzy:
\[
\mathtt{transpose}: \alpha\ \mathtt{list~list} \to \alpha\ \mathtt{list~list}
\]
Dla przypomnienia, \(k\)-ty wiersz macierzy jest \(k\)-tą kolumną macierzy transponowanej i odwrotnie.
Możesz założyć, że:
- dana lista jest niepusta,
- listy składowe są niepuste i są wszystkie tej samej długości.
Na przykład: transpose [[1; 2]; [5; 3]; [0; 1]] = [[1; 5; 0]; [2; 3; 1]]
Rozwiązania
-
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