Programowanie funkcyjne/Procedury wyższych rzędów i listy/Ćwiczenia: Różnice pomiędzy wersjami
Linia 30: | Linia 30: | ||
W rozwiązaniach poniższych zadań zamiast rekurencji, należy użyć standardowych procedur wyższych rzędów przetwarzających listy. | 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];; | kompresuj [1; 2; 2; 5; 11; 11; 2];; | ||
''- : int list = [1; 6; 9; 42; 3]'' | ''- : 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;; | '''type''' tree = Node '''of''' tree * int * tree | Leaf;; | ||
'''let''' '''rec''' fold_tree f a t = | '''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. | ||
+ | }} |
Wersja z 13:03, 25 paź 2006
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.
- 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ę nawiasy, 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 NieDaSie.
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ę 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.
- Napisz procedurę negującą predykat non: ('a -> bool) -> ('a -> bool). Za pomocą tej procedury oraz procedury exists zdefiniuj procedurę forall, która sprawdza, czy dany predykat jest spełniony przez wszystkie elementy danej listy. Czy zastosowanie wyjątków w implementacji procedury exists 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.
Ćwiczenie [Heads]
Za pomocą map zapisz procedurę heads, której wynikiem dla danej listy jest lista pierwszych elementów list składowych.
Ćwiczenie [Quick-sort]
Korzystając z filter zaimplementuj alorytm quick-sort.
Ćwiczenie [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,
powtórzeń liczby reprezentujemy w ciągu skompresowanym jako .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]
Ćwiczenie [Uśrednienie listy]
Dana jest lista liczb zmiennopozycyjnych
. Jej uśrednienie, to lista postaci: . Uśrednieniem listy jednoelementowej oraz pustej jest lista pusta. Napisz procedurę uśrednienie, która dla danej listy obliczy jej uśrednienie.Ćwiczenie [Od końca do końca]
Napisz funkcję od_końca_do_końca: int list -> int, która dla danej niepustej listy
obliczy .Ćwiczenie [Tails]
Załóżmy, że dana jest lista
. Sufiksem tej listy nazwiemy każdą listę, którą można uzyskać przez usunięcie pewnej liczby (od 0 do ) jej początkowych elementów. Tak więc sufiksami danej listy będzie np. ona sama, pusta lista, a także . 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.Ćwiczenie [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
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.Ćwiczenie [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 map, filter i fold.
W procedurze filter, jeżeli odrzucamy jakiś wierzchołek, to odrzucamy również wszystkich jego potomków. Odpowiednik procedury fold 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.