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

Ćwiczenia

• 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

• 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$?

• 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).