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

Ćwiczenia

Ćwiczenia na listy i procedury wyższych rzędów:

• Zapisz procedurę append za pomocą foldr/foldl.
• Napisz procedurę, która dla danej listy funkcji oblicza funkcję będącą sumą funkcji z danej listy.
• Napisz procedurę, która dla danej listy funkcji oblicza ich złożenie.
• 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. Rozwiązując to zadanie, zamiast rekurencji, należy użyć standardowych procedur wyższych rzędów przetwarzających listy.

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

• 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 nie wolno Ci tworzyć żadnych definicji rekurencyjnych. Powinieneś natomiast skorzystać z procedury fold_tree.