Programowanie funkcyjne/Procedury wyższych rzędów i listy/Ćwiczenia

Praca domowa

W rozwiązaniach poniższych zadań zamiast rekurencji, należy użyć standardowych procedur wyższych rzędów przetwarzających listy.

• Zapisz procedurę append za pomocą fold_right lub fold_left.
• Napisz procedurę, która dla danej listy funkcji oblicza ich złożenie.
• Napisz procedurę obliczającą sumę elementów listy występujących po ostatniej liczbie ujemnej (lub wszystkich, jeżeli na liście nie ma liczb ujemnych).

Ćwiczenia

W rozwiązaniach poniższych zadań zamiast rekurencji, należy użyć standardowych procedur wyższych rzędów przetwarzających listy.

• Napisz procedurę, która dla danej listy funkcji oblicza funkcję będącą sumą funkcji z danej listy.
• 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.
• Za pomocą map zapisz procedurę heads, której wynikiem dla danej listy list, jest lista pierwszych elementów list składowych.
• Korzystając z filter zaimplementuj alorytm quick-sort.
• 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 procedury: kompresującą i dekompresującą zadaną listę. Lista skompresowana powinna być oczywiście jak najkrótsza. Przy dekompresji możesz założyć, że lista skompresowana nie zawiera zer.

kompresuj [1; 2; 2; 5; 11; 11; 2];;
- : int list = [1; 6; 9; 42; 3]

• 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ę uśrednienie, 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]\mathrm{\$}$ obliczy $\underset{i=1,2,\dots ,n}{\min }|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 procedurę tails: 'a list -> 'a list list, która dla danej listy tworzy listę wszystkich jej sufiksów, uporządkowaną wg. malejących ich długości.
• Dane są: definicja typu tree i procedura fold_tree:

type tree = Node of tree * int * tree | Leaf;;
let rec fold_tree f a t = 
  match t with
  Leaf -> a |
  Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);;

Powiemy, że liczba w węźle drzewa jest widoczna, jeżeli na ścieżce od tego węzła do korzenia drzewa nie ma większej liczby. W szczególności liczba w korzeniu drzewa jest zawsze widoczna, a liczby mniejsze od niej nie są nigdy widoczne.

Napisz procedurę widoczne:drzewo $\to$ int, która dla zadanego drzewa (zawierającego wyłącznie liczby nieujemne) obliczy liczbę widocznych liczb. Rozwiązując to zadanie należy skorzystać z procedury fold_tree.