Programowanie funkcyjne, II UWr, 2014/15
Lista zadań nr 5
Część I (na 18.11.2014)

Zadanie 1 (4p.)

Zdefiniuj typ do reprezentacji leniwych nieskończonych ciągów elementów dowolnego typu (strumieni) tak, jak na wykładzie. Następnie:
  • zdefiniuj strumień przybliżający wartość liczby π z rosnącą dokładnością, korzystając ze wzoru Leibniza: π/4 = 1 - 1/3 + 1/5 - 1/7 + ...
  • napisz funkcję przekształcającą dowolny strumień x1,x2,x3,... w strumień postaci f x1 x2 x3, f x2 x3 x4, f x3 x4 x5,..., dla dowolnej funkcji f.
  • korzystając z powyższych definicji i transformacji Eulera:
    F x y z = z - (y-z)2/(x-2y+z)
    utwórz nowy strumień, szybciej zdążający do liczby π.
Napisz te same definicje używając konstrukcji lazy i force z modułu Lazy. Dlaczego lazy jest specjalną konstrukcją języka, a nie funkcją?

Zadanie 2 (2p.)

Napisz funkcję przeszukiwania zbioru stanów wszerz, typu ('a -> 'a list) -> 'a -> 'a llist (przy wybranej przez siebie reprezentacji list leniwych 'a llist), a następnie wykorzystaj ją do rozwiązania problemu n hetmanów.
Część II (na 25.11.2014)

Zadanie 3 (2p.)

Zmodyfikuj zaproponowane na wykładzie rozwiązanie problemu n hetmanów, tak by pozbyć się leniwej listy zawierającej wszystkie możliwe ustawienia hetmanów, z której dopiero wybiera się rozwiązania dobre. Algorytm, o który chodzi wygląda mniej więcej tak:
  • jeżeli bieżące ustawienie jest rozwiązaniem, to zwróć kolekcję zawierającą to rozwiązanie;
  • w przeciwnym razie, zsumuj kolekcje rozwiązań otrzymane przez dostawienie hetmana na wszystkie legalne pozycje w kolejnej kolumnie i powtórzenie algorytmu dla każdego tak otrzymanego ustawienia.

Zadanie 4 (6p.)

Kodowanie Huffmana jest prostą metodą bezstratnej kompresji. Załóżmy, że dana jest lista asocjacyjna złożona z par (symbol, częstość występowania). Zaimplementuj statyczny algorytm kodowania i dekodowania napisów (czyli ciągów symboli z listy) według następujących zasad:
  • Drzewo kodowe jest drzewem binarnym, w którego liściach znajdują się symbole wraz z ich częstościami, a w każdym węźle znajduje się suma częstości poddrzew lewego i prawego. Zdefiniuj typ takich drzew.
  • Korzystając z listy częstości zbuduj drzewo Huffmana: Mając daną listę drzew, wybieramy z niej dwa drzewa o najmniejszych częstościach (ten wybór nie musi być jednoznaczny). Usuwamy te drzewa z listy, łączymy je w jedno drzewo i wstawiamy do listy. Kontynuujemy aż do otrzymania listy jednoelementowej (czyli drzewa kodowego). Początkowa lista składa się z liści otrzymanych z listy częstości. Łączenie dwóch poddrzew polega na utworzeniu nowego drzewa o częstości będącej sumą częstości obu poddrzew.
  • Kodem symbolu jest zapis ścieżki od korzenia drzewa kodowego do liścia zawierającego ten symbol, gdzie ścieżka jest reprezentowana jako ciąg zer i jedynek, w którym 0 oznacza zejście do lewego poddrzewa, a 1 zejście do prawego poddrzewa (lub na odwrót, ale jednakowo dla wszystkich symboli). Kod napisu to ciąg kodów wszystkich symboli tego napisu.
  • Dekodowanie jest procesem odwrotnym: dla danego ciągu zer i jedynek kodującego pewien napis, wędrujemy po drzewie według kierunków zapisanych w kodzie, zaczynając od korzenia. Gdy dotrzemy do liścia, odczytujemy umieszczony w nim symbol i odrzucamy wykorzystany dotąd fragment kodu. Następnie dla pozostałego fragmentu kodu wracamy do korzenia i odszukujemy kolejne symbole, aż do wyczerpania kodu.