Tekst źródłowy strony 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ę <tt>append</tt> za pomocą <tt>fold_right</tt> lub <tt>fold_left</tt>.

* 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.

* Przypomnij sobie zadanie o ciągu różnicowym danej listy liczb całkowitych.  Rozwiąż je za pomocą procedur wyższych rzędów. 

* Dany jest ciąg nawiasów, otwierających i zamykających.  Napisz procedurę <tt>nawiasy</tt>, która obliczy minimalną liczbę nawiasów które należy obrócić, tak aby uzyskać poprawne wyrażenie nawiasowe.  Jeżeli nie jest to możliwe, to należy podnieść wyjątek <tt>NieDaSie</tt>.
  exception NieDaSię;;
  type nawias = Otwierający | Zamykający;;
  let nawiasy  (l: nawias list) = ... ;;

* Napisz procedurę, która dla danej listy funkcji, oblicza funkcję będącą sumą funkcji z danej listy.

* Rozszerz rozwiązanie poprzedniego zadania tak, żeby zamiast dodawania można było zastosować dowolną dwuargumentową operację na wynikach funkcji. 

* Napisz procedurę <tt>exists</tt>, 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 <tt>non: ('a -> bool) -> ('a -> bool)</tt>.  Za pomocą tej procedury oraz procedury <tt>exists</tt> zdefiniuj procedurę <tt>forall</tt>, która sprawdza, czy dany predykat jest spełniony przez wszystkie elementy danej listy.  Czy zastosowanie wyjątków w implementacji procedury <tt>exists</tt> nadal powoduje, że przeglądane są tylko niezbędne elementy listy?

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

{{cwiczenie|[Heads]||
Za pomocą <tt>map</tt> zapisz procedurę <tt>heads</tt>, której wynikiem dla danej listy jest lista pierwszych elementów list składowych. 
}}

{{cwiczenie|[Quick-sort]||
Korzystając z <tt>filter</tt> zaimplementuj alorytm quick-sort. 
}}

{{cwiczenie|[Kompresja ciągu liczb]||
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, <math>i</math> powtórzeń liczby <math>k</math> reprezentujemy w ciągu skompresowanym jako 
<math>2^{i-1} \cdot (2 \cdot k - 1)</math>. 

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]''

{{cwiczenie|[Uśrednienie listy]||
Dana jest lista liczb zmiennopozycyjnych <math>[x_1; x_2; \dots; x_n]</math>. 
Jej uśrednienie, to lista postaci: <math>[\frac{x_1 +. x_2}{2.0}; \dots; \frac{x_{n-1} +. x_n}{2.0}]</math>. 
Uśrednieniem listy jednoelementowej oraz pustej jest lista pusta. 
Napisz procedurę <tt>uśrednienie</tt>, która dla danej listy obliczy jej uśrednienie. 
}}

{{cwiczenie|[Od końca do końca]||
Napisz funkcję <tt>od_końca_do_końca: int list -> int</tt>, która dla danej niepustej listy <math>[a_1;...;a_n]$</math> obliczy <math>\min_{i=1,2,\dots,n} |a_i - a_{n+1-i}|</math>.
}}

{{cwiczenie|[Tails]||
Załóżmy, że dana jest lista <math>[x_1; x_2; \dots; x_n]</math>. 
''Sufiksem'' tej listy nazwiemy każdą listę, którą można uzyskać przez usunięcie pewnej liczby (od 0 do <math>n</math>) jej początkowych elementów. 
Tak więc sufiksami danej listy będzie np. ona sama, pusta lista, a także <math>[x_3; x_4; \dots; x_n]</math>. 
Napisz procedurę <tt>tails: 'a list -> 'a list list</tt>, która dla danej listy tworzy listę wszystkich jej sufiksów, 
uporządkowaną wg. malejących ich długości. 
}}

{{cwiczenie|[Fold_tree]||Dane są: definicja typu <tt>tree</tt> i procedura <tt>fold_tree</tt>:}}

 '''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ę <tt>widoczne:drzewo <math>\to</math> int</tt>, 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 <tt>fold_tree</tt>.

{{cwiczenie|[Procedury wyższych rzędów dla drzew]||
Przypomnij sobie rozwiązanie jednego z poprzednich zadań, gdzie trzeba było zdefiniować typ danych reprezentujący drzewa dowolnego (skończonego) stopnia. Zdefiniuj dla takich drzew odpowiedniki procedur <tt>map</tt>, <tt>filter</tt> i <tt>fold</tt>.  

W procedurze <tt>filter</tt>, jeżeli odrzucamy jakiś wierzchołek, to odrzucamy również wszystkich jego potomków. 
Odpowiednik procedury <tt>fold</tt> powinien być sparametryzowany dwiema funkcjami: 
Jedna powinna działać "w poziomie", kumulując wyniki policzone dla poddrzew zakorzenionych w synach danego węzła. 
Druga powinna działać "w pionie", okreslając wynik dla poddrzewa zakorzenionego w danym węźle, na podstawie wartości przechowywanej w tym węźle oraz wyniku skumulowanego dla poddrzew zakorzenionych w jego synach.
}}