• View
• Edit
• History
• Print

Zadania

Zadania na ćwiczenia będą się składać z: zadań z wykładów, zadań, które będę podawał bezpośrednio na ćwiczeniach, i zadań, które będę wysyłał i/lub zamieszczał na stronie.

Listy:

• lista 1 funkcje wyższego rzędu i manipulowanie listami (zad.1, zad.2)
• lista 2 jak wyżej (zad.1, zad.2, zad.3)
• lista 3 funkcje jako wartości, budowanie funkcji z funkcji (zad.1, zad.2)
• lista 4 typy algebraiczne (warianty) (zad.1, zad.2)
• lista 5 przerywnikowa (zad.1, zad.2, zad.3, zad.4)
• lista 6 leniwe (korekurencyjne) struktury danych (zad.1, zad.2, zad.3, zad.4)
• lista 7 programowanie imperatywne (zad.1, zad.2, zad.3, zad.4, zad.5)
• lista 8 moduły i funktory (zad.1, zad.2, zad.3, zad.4, zad.5, zad.6, zad.7, zad.8)
• lista 9 argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty (zad.1, zad.2, zad.3, zad.4, zad.5, zad.6, zad.7)

Punktacja

Schemat tabelki z punktami:

0..2.75: ndst
2.75..3.25: dst
3.25..3.75: dst+
3.75..4.25: db
4.25..4.75: db+
>4.75: bdb

Punktacja wybranych zadań: “Lista 8″ zadania podstawowe: wykład 8 zad. 1: 3pkt, zad. 2: 2pkt (+1 pkt za interfejs z osobną kompilacją); wykład 9 zad. 1: 3pkt, zad. 2: 2pkt; lista zad. 2: 2pkt, zad. 3: 3pkt, zad. 4: 3pkt.

Maksymalna ilość punktów za zadania podstawowe: 102

Ilość punktów za dobrze obroniony projekt: 68

Prognoza oceny (punkty + 68) / (102 + 68) * 5.0

Lista 1

Zadanie 1.

Napisz funkcję sortującą listy “mergesort” lub “quicksort”.

Zadanie 2.

Napisz funkcję wyższego rzędu “map_reduce” wzorowaną na

http://labs.google.com/papers/mapreduce.html

wraz z przykładowym (testowym) zastosowaniem. (Zauważ, że “reduce = fold”.)

Zachowaj pełną polimorficzność, tzn. sygnaturę:

Lista 2

Zadanie 1.

Wykorzystaj rozszerzenie składniowe “list comprehension”:

http://cl-informatik.uibk.ac.at/teaching/ss06/ocaml/content/listcompr.ml

Trójkąt o bokach a, b, c ma pole A dane wzorem:

s = (a+b+c)/2
A = sqrt(s*(s-a)*(s-b)*(s-c))

Znajdź wszystkie trójkąty o bokach długości będącej liczbą całkowitą nie większą od n, których pole też jest całkowitoliczbowe.

Zadanie 2.

Napisz funkcję until realizującą iterację: until termCheck iter init oblicza iter^n(init) t. że termCheck (iter^n(init)) = true oraz termCheck (iter^i(init)) = false dla 1 <= i < n.

Wykorzystaj tę funkcję do znajdywania miejsc zerowych. Napisz odpowiednie funkcje: termCheck, iterMethod, initApprox, report, takie, że funkcja:

findRoot f = report (until termCheck (iterMethod f) (initApprox f))

zwraca miejsce zerowe funkcji f (funkcja report ma wydobywać rozwiązanie ze stanu obliczeń, który może przechowywać dodatkowe informacje). Zaimplementuj dwa rozwiązania, np. wykorzystujące metodę bisekcji i metodę Newtona. Przetestuj je na kilku przykładach.

O funkcji f której pierwiastki będziesz obliczać możesz poczynić upraszczające założenia, np. że jest rosnąca.

Zadanie 3. Napisz funkcję liczącą domknięcie zwrotne i przechodnie grafu. Graf

dany jest jako lista przyległości: lista par wierzchołek, lista jego dzieci. (Możesz wykorzystać “list comprehension i funkcję fixpoint = (until equals) dla odpowiednio zdefiniowanej equals.)

Instalacja rozszerzenia składniowego:

zgodnie z komentarzem w pliku źródłowym:

 The syntax extension for list comprehension.

  HOW TO COMPILE
  $ ocamlc -c -I +camlp4 -pp "camlp4o q_MLast.cmo pa_extend.cmo -loc loc" listcompr.ml

  HOW TO USE
  # #load "camlp4o.cma";;
  # #load "listcompr.cmo";;
  # [ x + y | x <- [1;2;3] when x > 1; y <- [4;5;6] ];;

  The original code was posted by Anton Moscal to caml-list:

    Date: 2000-01-21 (08:43)
    Subject: Re: Q: camlp4 use?

Lista 3.

Zadanie 1.

Napisz bezpieczny typowo odpowiednik funckji sprintf z C (albo “nieoszukany” wariant funkcji Printf.sprintf) w następujący sposób. Napisz funkcje będące “dyrektywami wzorców”:

• lit dla literałów (stałych stringów)
• eol dla wstawiania końca linii
• int dla wstawiania liczb całk. (odpow. “%i”)
• str dla wstawiania stringów (odpow. “%s”)
• lis dla wstawiania list elementów.

Napisz funkcję “format”, która jako argument pobiera wzorzec zbudowany z dyrektyw wzorców. Niech $$ będzie infiks-owym operatorem złożenia funkcji zdefiniowanym na wykładzie. Wtedy przykładowo wywołanie:

ma zdefiniować funkcję o typie:

i zastosowanie

zwróci string:

"Napis graf oraz lista list liczb [[1, 2], [1], []]\n"

(lub ze średnikami zamiast przecinków).

Zadanie 2.

Na którymś z kolejnych wykładów zostanie wprowadzone pojęcie listy leniwej. My teraz zdefiniujemy szczególny przypadek listy leniwej, strumień (nieskończoną listę leniwą). Strumień to procedura, zwracająca kolejny element ze strumienia i resztę (ogon) strumienia. Aby to “naiwne” podejście zadziałało, musimy przekazać OCamlowi parametr -rectypes, uruchamiając go komendą ocaml -rectypes.

Strumień liczb naturalnych:

Podglądanie strumienia:

Napisz funkcje do manipulacji szeregami potęgowymi zaimplementowanymi jako strumienie. Zadeklaruj dla nich odpowiednie operatory infiksowe, np. ~-$, +$, -$, *.$, *$, /$, ... Żeby podkreślić dokładny charakter obliczeń, wykorzystaj liczby wymierne num z biblioteki Num. (Potrzebujemy ją “zlinkować”, np. w trybie interaktywnym komendą #load "nums.cma";;.)

Napisz funkcje: - szereg potęgowy stałej - negację szeregu potęgowego - dodawanie szeregów potęgowych - mnożenie szeregu przez stałą - mnożenie szeregów - dzielenie szeregów (wzór wyprowadź rozwijając równanie F = Q * G, by wyznaczyć q i Q1 dla Q = q + x*Q1) - złożenie szeregów (F . G) (x) = F (G (x)) - pochodną szeregu - trudniejsze: odwrotność funkcyjną szeregu, tzn. R w równaniu F(R(x)) = x - całkę szeregu i szeregi dla funkcji exp, sin, cos, sqrt - trudniejszy, wyznaczone z odpowiednich równań różniczkowych:

Np. z równania na exp: “dy/dx = y, y(0) = 1″ dostajemy

co w naszej implementacji zapisuje się jako:

Wytłumacz, dlaczego przy alternatywnej definicji:

wywołanie exp' () się zapętla.

Dalsze uwagi.

Wprowadź nazwę na typ szeregów:

oraz wprowadź annotacje typami w programie tak, aby typy zwracane przez toplevel odnosiły się do typów szeregów tylko przez nazwę “series”. Kiedy wyrażenia z szeregami są na tyle “wysokiego poziomu”, że system rozpoznaje, że chodzi nam o “series”, bez dodatkowych annotacji z naszej strony?

Annotacja typem to wyrażenie lub wzorzec (expr : typ), którego typem jest typ, o ile typ jest szczególnym przypadkiem najogólniejszego typu jaki ma expr.

Zapisz funkcję mnożącą szeregi prostym wzorem rekurencyjnym (wyprowadź go z równości F*G = (f + xF1)*(g+xG1)), bez wyznaczania “za każdym razem” odcinka początkowego.

Lista 4

Zadanie 1.

Programując czysto funkcyjnie nie mamy możliwości bezpośredniego modyfikowania struktur danych. Oznacza to, że przekształcając struktury, musimy dokonywać ich kopiowania. Okazuje się, że dzięki współdzieleniu wspólnych części, w przypadku modyfikacji węzła drzewa wystarczy skopiować ścieżkę od korzenia do modyfikowanego wierzchołka (jak w funkcji pomocniczej “insert2bst” z wykładu). Jednak jeśli dokonujemy na strukturze bardzo częstych zmian, jak np. w edytorze, wolelibyśmy uniknąć kopiowania zupełnie. Wyobraźmy sobie edytor strukturalny, np. edytor drzewa XML. W takim edytorze modyfikujemy drzewo tylko lokalnie, w pozycji kursora. Ograniczmy ruchy kursora do przemieszczania do sąsiadujących węzłów. Wtedy udaje się wykonać każdą operację (modyfikację i przemieszczanie kursora) w stałym czasie, dzięki strukturze, którą Gerard Huet nazwał “Zipper”:

zipper.pdf Δ

Dokończ artykuł Gerarda Hueta: napisz brakujące funkcje manipulacji “zipperami” z memoizacją (punkt 3.1).

Rozwinięcie: http://www.lri.fr/Rapports-internes/2006/RR1428.pdf

zippers.ml Δ

Zadanie 2. (Propozycja projektu.)

Typy algebraiczne (czyli warianty, sumy rozłączne produktów typów algebraicznych) dają bardzo wygodny sposób reprezentacji danych strukturalnych. Podejmiemy ambitne zadanie z maszynowego uczenia się: indukcję funkcji, czyli będziemy konstruować jak najoszczędniejszą funkcję, która dla zadanych danych wejściowych wygeneruje zadane dane wyjściowe. Zapoznaj się z artykułem Markusa Mottla “Using Algebraic Datatypes as Uniform Representation for Structured Data”:

http://ocaml.info/oefai/papers/algebraic_dts/index.html,

w szczególności z rozdziałem “Generalizing Decision Tree Learning to Algebraic Datatypes”:

http://ocaml.info/oefai/papers/algebraic_dts/algebraic_dts003.html

i dokończ moją prototypową implementację funind.ml Δ (bezpośrednio opartą na wspomnianym rozdziale z pracy Markusa Mottla) (konstruktywna krytyka mile widziana :-)).

Zadania:

a) Napisz test-zastosowanie (odpowiednik akapitu (* *** example *** *) z pliku źródłowego).

b) Przyjrzyj się, czy formuły matematyczne (wzory na entropię) zgadzają się z odpowiednimi funkcjami OCamla.

Bardziej czasochłonne zadania:

c) Wprowadź obsługę sytuacji, gdy dane nie opisują funkcji (tzn. gdy tym samym argumentom przypisane są różne wyniki — obecnie program wysypuje się wtedy). Dopisz obsługę gałęzi domyślnych “ _ → “. Patrz: paragraf 3.3 artykułu.

d) Dopisz normalizację “lewej strony” (patrz paragraf 3.1.2 artykułu).

Dalsze propozycje:

e) Rozszerz algorytm o obsługę zmiennych liczbowych (zapoznaj się z odpowiednimi mechanizmami budowy drzew decyzyjnych).

f) Możesz zmierzyć się z problemem indukcji funkcji rekurencyjnych.

g) Zbuduj system automatycznie kompilujący i wykorzystujący wygenerowane funkcje. Przykładowe możliwości to wykorzystanie modułów trybu interaktywnego budowanych w czasie kompilacji OCamla, albo wykorzystanie MetaOCamla.

h) Zaimplementuj zastosowanie programu, np. w systemie eksperckim.

funind.ml Δ

Lista 5

Zadanie 1.

Napisz funkcję dokonującą transpozycji macierzy reprezentowanych jako listy list.

Zadanie 2.

Zbuduj dowolne drzewo rozpinające dla grafu danego jako lista par wierzchołek, lista wierzchołków przyległych. Zapamiętaj również pozostałe wierzchołki wychodzące z danego węzła. Użyj typu:

Zadanie 3.

Dzielimy wierzchołki drzewa na lekkie i ciężkie jak następuje: korzeń jest lekki, wszyscy synowie, którzy rozpinają poddrzewa o największym rozmiarze spośród poddrzew rodzeństwa, są ciężcy, pozostałe wierzchołki są lekkie. (Innymi słowy, dla każdego wierzchołka wewnętrznego oznaczamy tego syna, w którym podczepione jest największe poddrzewo, jako ciężkiego.) Oznaczamy krawędzie prowadzące do lekkich synów jako lekkie, a prowadzące do ciężkich synów jako ciężkie. Lekką głębokością wierzchołka v nazywamy ilość lekkich krawędzi na ścieżce od v do korzenia. Lekką głębokością drzewa nazywamy maksimum z lekkich głębokości jego wierzchołków. Napisz funkcję obliczającą lekką głębokość drzewa.

Zadanie 4.

W Pythonie mechanizm wyjątków pozwala zdefiniować klauzulę “else”:

try:
  GUARDED
except EXC1:
  HANDLER1
...
except EXCn:
  HANDLERn
else:
  CLOSING

Fragment CLOSING jest obliczany tylko, jeśli nie nastąpił żaden wyjątek. W OCamlu bardzo przydałby się następujący wariant tej konstrukcji:

w którym nazwa X jest związana z wartością GUARDED w wyrażeniu BODY. O ile obliczanie GUARDED nie spowodowało wyjątku, wynikiem całego wyrażenia jest wartość BODY. Jeśli obliczenie GUARDED podniosło wyjątek EXCi, wynikiem całego wyrażenia jest wartość HANDLERi. Wyjątki podnoszone przez BODY nie są przechwytywane!

a) Przetłumacz konstrukcję let try na standardowe konstrukcje OCamla, co pozwoli dodać ją jako rozszerzenie składniowe (rzeczywiście takie rozszerzenie jest dostępne).

b) Czy w twoim tłumaczeniu pozycja BODY jest ogonowo-rekurencyjna (tail-recursive)? Jeśli nie jesteś pewien, sprawdź to eksperymentalnie.

Lista 6.

Zadanie 1.

Porównaj następujące dwie implementacje list leniwych:

Wytłumacz różnicę w złożoności pomiędzy obliczeniem

a

Zadanie 2.

Zaimplementuj “czysto funkcyjny” mechanizm memoizacji funkcji pierwotnie rekurencyjnych (primitive recursive) na liczbach naturalnych, tzn. funkcji które dla obliczenia argumentu n potrzebują (co najwyżej) wartości dla argumentów mniejszych od n. Funkcje pierwotnie rekurencyjne reprezentuj przy pomocy nierekurencyjnych funkcji wyższego rzędu o typie:

gdzie pierwszy argument ma oznaczać tę samą funkcję, np.

Napisz funkcję memoize taką, że np.

będzie wydajną wersją funkcji Fibonacciego. W implementacji wykorzystaj leniwe drzewa binarne jak w zadaniu 4 do wykładu 5, ale oparte o natywne wartości leniwe:

(na podstawie zadania 1. wytłumacz, dlaczego ta modyfikacja jest istotna). Napisz funkcję map_lBT która leniwie mapuje drzewo lBT (podobnie do powyższej funkcji lmap dla list leniwych). Napisz funkcję itr taką, jak w zadaniu 4 (a) z wykładu 5: która dla zadanej liczby całkowitej n konstruuje nieskończone leniwe drzewo binarne z korzeniem o etykiecie n i z dwoma poddrzewami itr(2*n) i itr(2*n+1). Napisz funkcję nth_node, która dla danego drzewa i liczby n zwraca etykietę wierzchołka, który w drzewie zwróconym przez itr miałby numer n. Wykorzystaj te trzy funkcje do napisania memoize. Drzewo buduj począwszy od wierzchołka 1, traktując 0 jako szczególny przypadek:

Jaka jest zaleta tej metody memoizacji w porównaniu z metodą “wypełniania tablicy”?

Zadanie 3. (Problem Hamminga)

Wygeneruj n pierwszych liczb w postaci 2^a₁3^a₂5^a₃…p_k^a_k, tzn. nie dzielących się przez liczby pierwsze większe od k-tej liczby pierwszej, dla danego k.

Idea rozwiązania polega na generowaniu listy liczb tej postaci. Aby wygenerować kolejną liczbę, znajdujemy najmniejszą już wygenerowaną liczbę x₁ taką, że 2x₁ jest większa od ostatniego elementu już wygenerowanej listy, tak samo dla x₂ i 3x₂, etc. Do listy dodajemy minimum z 2x₁, 3x₂, …, p_kx_k.

Rozwiąż zadanie budując listę leniwą (na bazie modułu Lazy), zawierającą kolejne liczby zadanej postaci: uzupełnij brakującą linijkę kodu:

Zadanie 4. Ciągi liczbowe.

Użyjemy poręcznego typu do reprezentacji ciągów.

Napisz funkcje:

• neg zmieniającą znak każdego wyrazu ciągu na przeciwny: neg [x0; x1; x2; ...] = [-x0; -x1; -x2; ...]
• head, tail zwracające pierwszy element oraz ciąg począwszy od drugiego elementu
• x_to_S konwertującą ciąg do postaci ogólnej: x_to_S xs = S (x0, S(x1, S (x2, ...))) (używaj tej funkcji w kolejnych definicjach tylko w razie konieczności! np. w definicji map i map2)
• dodawanie po osiach, mnożenie przez stałą, mnożenie po osiach
• sumy częściowe: n-tym wyrazem sumy częściowej sums [x0; x1; x2; ...] jest x0+x1+x2+...+xn

Czemu są równe: exp (A x r), sqrt (G x q), log (G x q), n!?

Zakoduj algorytm Rungego-Kutty drugiego rzędu iteracyjnego rozwiązywania równania y' = f (y, t), y(t0)=y0, zazwyczaj prezentowany tak:

k1 = h * f(yn; tn)
k2 = h * f(yn + k1/2; tn + h/2)
yn+1 = yn + k2

zastosuj “podniesienie” funkcji f z liczb na ciągi, (map2 f s1 s2).

Zakoduj algorytm Lentza obliczania ułamków łańcuchowych:

f = b0 + a1 / (b1 + a2 / (b2 + a3 / (b3 + …)))

o następującej specyfikacji imperatywnej:

Set f0 = b0; C0 = f0; D0 = 0;
for j = 1; 2; …
Set Dj = 1/(bj + aj*Dj-1)
Set Cj = bj + aj/Cj-1
Set fj = fj-1(Cj*Dj)
Stop gdy Cj*Dj prawie równe 1.

Oblicz przy jego pomocy e^z = 1 + (z / (1 - z / (2 + z / (3 - …)))) dla z=1 (i 'a = float ).

Lista 7.

Zadanie 1.

Napisz wersje imperatywną i czysto funkcyjną procedury generującej losową permutację ciągu. Procedurę zaimplementuj jako funkcję pobierającą strumień liczb całkowitych (domyślnie liczb losowych z przedziału 0..M dla dużego M) oraz, w przypadku imperatywnym tablicę, a w przypadku funkcyjnym listę. Postaraj się uzyskać poprawne (żadna permutacja nie powinna być faworyzowana) i wydajne implementacje. Porównaj wydajność wersji imperatywnej i funkcyjnej.

Zadanie 2.

a)

Zapoznaj się z pojęciem leksykalnego vs. dynamicznego zakresu wiązań (zmiennych), na przykład z 1. i 2. rozdziału artykułu “A Syntactic Theory of Dynamic Binding” Luc Moreau http://www.ecs.soton.ac.uk/~lavm/papers/tapsoft97.ps.gz Zastanów się nad podobieństwami i różnicami “dynamicznie zakresowanych” zmiennych i referencji.

b*)

Zaimplementuj wznawialne wyjątki: mechanizm, w którym fragment programu obsługujący wyjątek może przekazać fragmentowi zgłaszającemu wyjątek informację potrzebną do kontynuowania obliczeń (da się to zrobić w OCamlu, bez tzw. kontynuacji). (Zadanie to rozwiązał Oleg Kiselyov).

Zadanie 3.

Napisz rozwiązywaczkę do “gry w 8″: gry, w której na prostokątnej planszy rozłożone są kwadraty ponumerowane kolejnymi liczbami naturalnymi, ale bez związku liczby z położeniem kwadratu, a celem jest sprowadzenie planszy do sytuacji, w której kwadraty umieszczone są kolejno, tzn. na prawo od kwadratu z numerem i jest i+1, chyba że i jest na prawym brzegu, wtedy i+1 jest pierwszym kwadratem w kolejnym wierszu. Dopuszczalnymi ruchami są zamiany przyległych krawędzią kwadratów, przy czym jeden z zamienianych kwadratów musi mieć numer 0 (tzw. puste pole).

Testuj program dla duuużych plansz, stopniując trudność ilością ruchów zaburzających: generuj testową konfigurację wyjściową stosując n przypadkowych ruchów do konfiguracji będącej rozwiązaniem.

Wymagania co do programu:

Program ma przechowywać dokładnie dwie tablice zawierające konfiguracje planszy: jedną z konfiguracją wyjściową (początkową) i drugą z konfiguracją aktualnie rozpatrywaną. Program ma wykorzystywać funkcję heurystyczną, mierzącą odległość aktualnej konfiguracji od docelowej. Pozostałe konfiguracje mają być pamiętane jako ciągi (listy) ruchów sprowadzających konfigurację początkową do danej. Zmiana konfiguracji aktualnej na którąś z zapamiętanych pozostałych ma być wykonywana przez wycofanie części ruchów aktualnej konfiguracji (zrobienie ruchów odwrotnych, w odwrotnej kolejności), aż do uzyskania wspólnego odcinka początkowego (traktując głowę jako koniec listy) z konfiguracją zapamiętaną, i następnie wykonanie brakujących ruchów konfiguracji zapamiętanej. Do znalezienia wspólnego odcinka początkowego wykorzystaj test równości fizycznej (==) (zapewnij współdzielenie).

Zadanie 4.

Porównaj eksperymentalnie wydajność (faktyczną złożoność czasową) wyznaczania histogramu (np. zliczania wystąpień słów):

• imperatywnie przez iterację, przy pomocy tablicy haszującej (moduł Hashtbl) klucz:słowo - wartość:liczba wystąpień
• funkcyjnie “jednorazowo” np. przez posortowanie i zwinięcie posortowanej listy
• funkcyjnie iteracyjnie (symulując przypadki, gdy wyniki pośrednie też są potrzebne): podobnie jak w stylu imperatywnym ale z modułem Map zamiast Hashtbl (zwinięcie listy będącej argumentem funkcji wyznaczającej histogram)

Zadanie 5.

Wykorzystując rozszerzenie składniowe let try (patrz zadanie 4 z listy 5), napisz funkcję, która pobiera listę nazw plików, i dla plików (w bieżącym katalogu), których zawartość da się przeczytać (czyli m. in. istnieją), tworzy ich kopię (dodając rozszerzenie “.copy”) — kopię stwórz otwierając nowy plik i zapisując w nim zawartość starego. Funkcja ma zwrócić konkatenację zawartości wszystkich plików (które dało się otworzyć) — zakładamy, że są to pliki tekstowe z jedną linią tekstu. (Jeśli któryś z plików mających zawierać kopię już istnieje, funkcja ma przepuścić wyjątek.)

skompilowany i zzipowany plik z rozszerzeniem składniowym Δ

Lista 8.

Zadanie 1.

a) Zapoznaj się z ideą “grafów indukcyjnych”: http://web.engr.oregonstate.edu/~erwig/fgl/ Zapisz wybrany algorytm grafowy nie zaimplementowany w artykule “Inductive Graphs and Functional Graph Algorithms”: http://web.engr.oregonstate.edu/~erwig/papers/abstracts.html#JFP01 w “języku grafów indukcyjnych”.

b) Zapoznaj się z biblioteką “ocamlgraph”: http://www.lri.fr/~filliatr/ocamlgraph/. (*) Napisz funktor dodający operację dekompozycji z “grafów indukcyjnych” do grafów z “ocamlgraph”.

Zadanie 2.

Wygeneruj współdzielące kod moduły o sygnaturze:

tak, że compare jest funkcją porównującą zgodną ze specyfikacją Pervasives.compare, przy czym symbol mniejszy to ten, który był wcześniej widziany przez dany moduł. Np.:

# let s1 = Table1.string_to_symbol "Ala";;
val s1 : Table1.symbol = <abstr>
# let s2 = Table1.string_to_symbol "Becia";;
val s2 : Table1.symbol = <abstr>
# let s3 = Table2.string_to_symbol "Becia";;
val s3 : Table2.symbol = <abstr>
# let s4 = Table2.string_to_symbol "Ala";;
val s4 : Table1.symbol = <abstr>
# Table1.compare s1 s2;;
- : int = -1
# Table2.compare s4 s3;;
- : int = 1

Do efektywnego odwzorowania ze stringów w symbole wykorzystaj moduł Hashtbl.

Zadanie 3.

Zobacz, w jaki sposób Will Farr wykorzystuje funktory do sparametryzowania swoich algorytmów względem implementacji obiektów, na których one działają: http://wmfarr.blogspot.com/2006/08/adventures-in-ocaml-land-barnes-hut.html, http://wmfarr.blogspot.com/2006/10/automatic-differentiation-in-ocaml.html (wersja poprawiona http://wmfarr.blogspot.com/2006/10/correction-to-automatic.html). (Możesz też zobaczyć, w jaki sposób Jean-Christophe Filliatre implementuje algorytmy grafowe w oderwaniu od konkretnej “realizacji” grafów http://www.lri.fr/~filliatr/ocamlgraph/.)

Podaj przykład praktycznej instancjacji funktora realizującego algorytm z dziedziny twojego projektu (tzn. nie implementującego kontener ani odwzorowanie) różnymi strukturami.

Zadanie 4.

Napisz funktor konstruujący odwzorowania MyMap, pobierający funktor budujący zbiory oraz odpowiednie struktury dla kluczy i wartości, implementujący odwzorowania jako zbiory par (klucz, wartość). Przetestuj wykorzystując Set.Make z biblioteki standardowej. Do zaimplementowania MyMap.find użyj inter (intersection) i elements (lista elementów). Nie wymagaj od użytkownika podawania jakichś wartości domyślnych / początkowych w obrazie odwzorowania.

Zadanie 5.

Wytłumacz, jakie udogodnienie systemu modułów w OCamlu pozwala na następującą zwięzłą specyfikację:

jednak w następującym przykładzie prowadzi do “katastrofy”:

Dlaczego to zachowanie jest niespodziewane? (Co myślał sobie autor modułu Weird?) Pouczające są komunikaty o błędach:

Zaimplementuj funktor QueuedDict w SMLu.

Zadanie 6.

Przeczytaj podrozdział 10.2 z książki Chrisa Okasaki “Purely Functional Data Structures” z pominięciem analizy złożoności na końcu paragrafu 10.2.1 (str. 156–157). Przeanalizuj fragment kodu (z http://caml.inria.fr/pub/papers/xleroy-recursive_modules-03.pdf):

Zrób ćwiczenie 10.8 z książki.

Zadanie 7. The Expression Problem (Part I)

Zaimplementuj przykład wykorzystania “mixin modules” z Dominic Duggan, Constantinos Sourelis Mixin Modules poszerzony o operację dodawania w module Num. Idea jest taka: typy i funkcje składamy z klocków zdefiniowanych w osobnych modułach, które można osobno kompilować. Poniżej dla wygody zaadoptowany do składni OCamla.

Moduły “mixinowe” przerób na funktory wykorzystując pomysły z ML Module Mania: A Type-Safe, Separately Compiled, Extensible Interpreter. Być może konstrukcję da ci się uprościć wykorzystując dostępne w OCamlu moduły rekurencyjne (rekurencyjne będą oczywiście instancje funktorów Num i Func, nie same te funktory, które muszą dać się osobno kompilować). UWAGA: nie ma potrzeby czytać całego artykułu Normana Ramseya, kluczem jest pojęcie “wieży typów” i “two-level types” oraz poskładanie kawałków przez funktory.

Dodatkowe uwagi.

Wieżą typów nazywam technikę budowania hierarchi typów przez wstawienie opcji “w innym przypadku…” Wieża typów to też jednonitkowa hierarchia typów.

“Two-level types” to generalnie rozcięcie definicji typu przez wprowadzenie parametrów, tak że definicję równoważną oryginalnej otrzymuje się przez podstawienie definiowanego typu pod parametr (fixpunkt). W zastosowaniach podstawia się coś co rekurencyjnie zależy od całości.

Zadanie 8.

Warianty i rekordy to koncepcje w pewnym sensie dualne, dlatego zagadnienia dotyczące jednych przenoszą się na drugie. OCaml ma warianty polimorficzne, ale ciągle nie ma rekordów polimorficznych, dlatego “recykling” etykiet rekordów pozostaje bolączką (etykiety użytej w jednym typie rekordowym nie można użyć w innym w tym samym module). Naturalną ideą jest podtypowanie typów rekordowych, traktujące typ rekordowy z dodatkowymi etykietami jako podtyp wyjściowego typu rekordowego, w sensie type p3d = {x : float; y : float; z : float} “jest podtypem” type p2d = {x : float; y : float}. Wykorzystując koncepcje wieży typów i “two-level types” zbuduj przykładową hierarchię typów rekordowych i napisz funkcje demonstrujące praktyczne zachodzenie podtypowania. W jakiej mierze możliwe jest “wielodziedziczenie”?

Lista 9.

Zadanie 1.

Zapoznaj się z wariantami polimorficznymi http://caml.inria.fr/pub/docs/manual-ocaml/manual006.html, par. 4.2. “Zawiąż węzeł” (najpierw rozetnij ten za ciasno związany) następującej spłaszczonej wieży typów, tzn. podaj równoważną definicję, która się kompiluje:

Zadanie 2. The Expression Problem (Part II)

Zaimplementuj przykład z zadania 7 listy 8 na trzy kolejne sposoby.

1. Przy pomocy typów zamkniętych, jak w poprzednim zadaniu (czyli np. jak w wyjściowym rozwiązaniu zadania 7, tylko z “płaskim otagowaniem” wariantami polimorficznymi — bez zagnieżdżonych tagów i nietrywialnych projekcji / injekcji). Przykładowe rozwiązanie: Code reuse through polymorphic variants.
2. Przy pomocy wariantów polimorficznych i typów otwartych. Typ otwarty w sygnaturze poprzedzamy słowem kluczowym private (wymaga OCamla 3.09). Przykładowe rozwiązanie: Private rows: abstracting the unnamed.
3. Przy pomocy klas, jak w http://pauillac.inria.fr/~remy/work/expr/.

Zadanie 3.

Zamień funkcję map_reduce z zad.2 listy 1 na funkcję, która może (ale nie musi) pobrać gotową już listę par zamiast (a czasami dodatkowo do) listy dowolnych elementów i funkcji mapującej je na pary. Wykorzystaj argumenty opcjonalne http://caml.inria.fr/pub/docs/manual-ocaml/manual006.html par. 4.1.1.

Zadanie 4.

Zdefiniuj hierarchię klas (albo typów klas) dla zwierząt, animal, camel, omnivore, bactrian_camel oraz dla pożywienia food, grass, meat, green_grass. camel i omnivore są animal, grass i meat są food. green_grass jest grass, bactrian_camel jest camel. Zwierzęta mają metodę eat, każde zwierzę ma swoją dietę. omnivore może jeść dowolne food. bactrian_camel je green_grass. Zapewnij, że wszystkie zwierzęta dziedziczące z camel mają dietę będącą podtypem grass (nie mogą jeść meat) (ale może być ona zawężona, jak dla bactrian_camel). (Ogólnie zapewnij, że podtypowanie jest kowariantne względem diety.) Możesz wykorzystać klasy pomocnicze, klasyfikatory virtual, private, ograniczenia constraint, itd. ale postaraj się uzyskać możliwie proste rozwiązanie.

Zadanie 5.

Zdefiniuj “dwuargumentową” klasę [‘a, ‘b] cons i “bezargumentową” klasę [‘a, ‘b] nil, definiujące obiekty typu < null : bool; car : 'a; cdr : 'b > . (Oczywiście wywołanie car czy cdr na obiekcie klasy nil ma rzucić wyjątek.) Na bazie tych klas zdefiniuj typ homogenicznych (zwykłych) list polimorficznych 'a homo_list — przykładowa wartość: new cons 2 (new cons 5 (new nil)), oraz typ list alternujących, zawierających elementy z dwóch typów, na zmianę ('a, 'b) alt_list — przykładowa wartość: new cons 2 (new cons 'b' (new cons 5 (new nil))) . Sprawdź, że przykładowe wartości rzeczywiście mają zdefiniowane przez ciebie typy, a niechciane wartości nie, np. że new cons 2 (new cons 'b' (new cons 'a' (new nil))) nie jest listą alternującą. Zdefiniuj dziedziczącą z ['a, 'b] cons klasę ['a, 'b] alt_cons pozwalającą budować tylko listy alternujące. Sprawdź, że listy zbudowane z alt_cons mają również wcześniej zdefiniowany typ alt_list i że wyrażenie new alt_cons 2 (new alt_cons 'b' (new alt_cons 'a' (new nil))) oraz inne nie będące listami alternującymi się nie typują. Dodaj przez dziedziczenie metodę length do klas cons i nil. Zdefiniuj klasę list alternujących z długością alt_lcons przez podwójne dziedziczenie. Uzasadnij, że zgłoszone przez kompilator ostrzeżenia nie są w tym konkretnym przypadku błędami.

Zadanie 6.

Ćwiczenie 32 z http://caml.inria.fr/pub/docs/u3-ocaml/ocaml-mixins.html#toc19.

Zadanie 7.

Zaprezentuj (zaimplementuj) model “subject - observer” na podstawie któregoś podręcznika do OCamla.

THE END.