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

Ćwiczenie [Ciągi różnicowe]

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

Rozwiązanie

{{{3}}}

Ćwiczenie [Nawiasy]

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) = ... ;;

Ćwiczenie [Suma funkcji]

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

Rozwiązanie

{{{3}}}

Ćwiczenie [Łączenie funkcji]

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

Rozwiązanie

{{{3}}}

Ćwiczenie [Exists]

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.

Ćwiczenie [Forall]

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?

Ćwiczenie [Sumy]

Napisz procedurę sumy: int list -> int list, której wynikiem dla danej listy $[x_1,\dots ,x_n]$ jest lista: $[x_1,x_1+x_2,x_1+x_2+x_3,\dots ,x_1+x_2+\cdots +x_n]$.

Przykład: sumy [1; 5; 2; 7; 12; 10; 5] = [1; 6; 8; 15; 27; 37; 42].

Ćwiczenie [Podział na listy rosnące]

Napisz procedurę podzial: int list -> int list list, która dla danej listy liczb całkowitych $l=[x_1;x_2;\dots ;x_n]$ podzieli ją na listę list $[l_1;\dots ;l_k]$, przy czym:

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle l = l_1 @ \dots @ l_k} ,
• każda z list $l_i$ jest ściśle rosnąca,
• $k$ jest najmniejsze możliwe.

Przykład: podzial [1;3;0;-2;-2;4;9] = [[1; 3]; [0]; [-2]; [-2;4;9]].

Ćwiczenie [Podział na listy liczb tego samego znaku]

Napisz procedurę podzial: int list -> int list list, która dla danej listy liczb całkowitych $l=[x_1;x_2;\dots ;x_n]$ podzieli ją na listę list $[l_1;\dots ;l_k]$, przy czym:

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle l = l_1 @ \dots @ l_k} ,
• dla każdej listy $l_i$ wszystkie elementy na takiej liście są tego samego znaku,
• $k$ jest najmniejsze możliwe.

Przykład: podzial [1;3;0;-2;-2;-4;9] = [[1; 3]; [0]; [-2;-2;-4]; [9]].

Ćwiczenie [Zamiana iloczynu sum na sumę iloczynów]

Wyobraźmy sobie, że jest dana lista list elementów:

$[[x_{1,1};x_{1,2};\dots ;x_{1,n_1}];[x_{2,1};x_{2,2};\dots ;x_{2,n_2}];\dots ;[x_{k,1};x_{k,2};\dots ;x_{k,n_k}]$

Reprezentuje ona iloczyn sum elementów postaci:

$(x_{1,1}+x_{1,2}+\cdots +x_{1,n_1})\cdot (x_{2,1}+x_{2,2}+\cdots +x_{2,n_2})\cdots (x_{k,1}+x_{k,2}+\cdots +x_{k,n_k})$

Taki iloczyn sum jest równy sumie iloczynów postaci:

$(x_{1,1}\cdot x_{2,1}\cdots x_{k,1})+(x_{1,1}\cdot x_{2,1}\cdots x_{k,2})+\cdots +(x_{1,n_1}\cdot x_{2,n_2}\cdots x_{k,n_k})$

którą z kolei można przedstawić jako listę list postaci:

$[[x_{1,1};x_{2,1};\dots ;x_{k,1}];[x_{1,1};x_{2,1};\dots ;x_{k,2}];[x_{1,n_1};x_{2,n_2};\dots ;x_{k,n_k}]]$

Napisz procedurę rozwin: 'a list list -> 'a list list, która przekształca listę list reprezentującą iloczyn sum w listę list reprezentującą sumę iloczynów. Kolejność składników w sumie i czynników w iloczynach może być dowolna.

Przykład: rozwin [[1;2;3]; [4]; [5;6]] = [[1; 4; 5]; [1; 4; 6]; [2; 4; 5]; [2; 4; 6]; [3; 4; 5]; [3; 4; 6]].

Rozwiązanie

{{{3}}}

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.

Rozwiązanie

{{{3}}}

Ć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, $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.

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

Ćwiczenie [Tails]

Załóżmy, że dana jest lista $[x_1;x_2;\dots ;x_n]$. Sufiksem tej listy nazwiemy każdą listę, którą można uzyskać przez usunięcie pewnej liczby (od 0 do $n$) jej początkowych elementów. Tak więc sufiksami danej listy będzie np. ona sama, pusta lista, a także $[x_3;x_4;\dots ;x_n]$. 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.

Rozwiązanie

{{{3}}}

Ćwiczenie [Uśrednienie listy]

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

Rozwiązanie

{{{3}}}

Ćwiczenie [Od końca do końca]

Napisz funkcję od_końca_do_końca: int list -> int, która dla danej niepustej listy $[a_1;...;a_n]\mathrm{\$}$ obliczy $\underset{i=1,2,\dots ,n}{\min }|a_i-a_{n+1-i}|$.

Ćwiczenie [Fold_tree]

Dane są: definicja typu tree i procedura fold_tree:

type tree = Node of tree * int * tree | Leaf;;
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);;
val fold_tree : (int -> 'a -> 'a -> 'a) -> 'a -> tree -> 'a = <fun>

Użyj procedury fold_tree do:

• Policzenia liczby węzłów w drzewie.
• Policzenia wysokości drzewa.
• Policzenia średnicy drzewa (tj. najdłuższej prostej ścieżki w drzewie łączącej dwa liście).
• Sprawdzenia czy drzewo jest drzewem BST (dla drzewa liczb float).
• 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 należy skorzystać z procedury fold_tree. Możesz założyć, że w drzewie nie ma liczb ujemnych.

Rozwiązanie prostsze, ale mniej efektywne

{{{3}}}

Rozwiązanie efektywne

{{{3}}}

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