Programowanie funkcyjne/Procedury wyższych rzędów i listy/Ćwiczenia: Różnice pomiędzy wersjami

Wersja z 13:28, 22 sie 2006

Ćwiczenia na listy i procedury wyższych rzędów:

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.
Korzystając z filter zaimplementuj Quick-sort.
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]

@@ Linia 12: / Linia 12: @@
 * Za pomocą <tt>foldr</tt> zapisz <tt>flatten</tt>. (<tt>let flatten l = foldr (@) l [];;</tt>)
 * Za pomocą <tt>foldl</tt> zapisz procedurę <tt>foldr</tt>.
+* Korzystając z <tt>filter</tt> zaimplementuj Quick-sort.
+* 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. 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]''