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

Ćwiczenia

• Zapisz procedurę length za pomocą foldr.
• Zapisz procedurę append za pomocą foldr/foldl.
• Za pomocą foldl zapisz procedurę rev.
• suma listy funkcji,
• złożenie listy funkcji,
• Za pomocą map zapisz procedurę heads, której wynikiem dla danej listy list, jest lista pierwszych elementów list składowych.
• Za pomocą filter zaimplementuj procedurę not_divisivble, która pozostawia na liście wszystkie elementy niepodzielne przez zadaną liczbę.
• Wykorzystaj rozwiązanie poprzedniego zadania do zaimplementowania sita Eratostenesa.
• Za pomocą foldr zapisz flatten. (let flatten l = foldr (@) l [];;)
• Za pomocą foldl zapisz procedurę foldr.
• 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.

Laboratorium

• Korzystając z filter zaimplementuj Quick-sort.
• Niech $f:{ℛ}\to {ℛ}$ będzie funkcją 1-1 i "na" oraz taką, że $f(0)=0$, $f$ jest rosnąca i $|f(x)|\ge |x|$. Zaimplementuj procedurę odwrotność, której wynikiem dla parametru $f$ będzie przybliżenie $f^{-1}$ z dokładnością zadaną przez stałą epsilon (czyli jeśli $g=(\text{<mrow data-mjx-texclass="ORD">odwrotnosc</mrow>}f)$, to $\mathrm{\forall }x|g(x)-f^{-1}(x)|\le epsilon$). Wygładzenie funkcji z odstępem $dx$ polega na uśrednieniu $f(x-dx)$, $f(x)$ i $f(x+dx)$.
• Napisz procedurę wygładzającą daną funkcję z zadanym odstępem. Punktem stałym funkcji $y\to \frac{x}{y^{n-1}}$ jest $\sqrt[n]{x}$.
• Zaimplementuj obliczanie $n$-tego pierwiastka z $x$ za pomocą obliczania punktu stałego i tłumienia przez uśrednianie. Uwaga: ile razy należy stosować tłumienie w zależności od $n$?
• 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]*;\end{flushleft}

• Napisz odpowiedniki map i filter dla drzew. Rozważ drzewa binarne i drzewa o wierzchołkach dowolnego skończonego stopnia (por. ćw. do poprzedniego wykładu).