From the Lukasz Stafiniak pages
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.
Schemat tabelki z punktami:
Imię i nazwisko | Lista 1 | Lista 2 | Lista 3 | Lista 4 | Lista 5 | Lista 6 | Lista 7 | Lista 8 | Lista 9 | Projekt | Razem | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
pdst | dod | pdst | dod | pdst | dod | pdst | dod | pdst | dod | ob | pdst | dod | pdst | dod | pdst | dod | dod | pdst, dod | suma | wynik | ocena | |
maksymalna ilość punktów | 12 | 6 | 12 | 9 | 12 | 8 | 12 | 8 | 9 | 4 | 14 | 8 | 13 | 11 | 18 | 19 | 24 | 68, 12 | 279 | 8.2 |
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
Napisz funkcję sortującą listy “mergesort” lub “quicksort”.
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ę:
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.
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.
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
.)
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?
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).
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.
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.
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”:
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
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.
Napisz funkcję dokonującą transpozycji macierzy reprezentowanych jako listy list.
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:
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.
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.
Porównaj następujące dwie implementacje list leniwych:
Wytłumacz różnicę w złożoności pomiędzy obliczeniem
a
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”?
Wygeneruj n pierwszych liczb w postaci 2a13a25a3…pkak, 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ę x1 taką, że 2x1 jest większa od ostatniego elementu już wygenerowanej listy, tak samo dla x2 i 3x2, etc. Do listy dodajemy minimum z 2x1, 3x2, …, pkxk.
Rozwiąż zadanie budując listę leniwą (na bazie modułu Lazy
),
zawierającą kolejne liczby zadanej postaci: uzupełnij brakującą
linijkę kodu:
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)
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 ez = 1 + (z / (1 - z / (2 + z / (3 - …)))) dla z=1 (i 'a = float
).
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.
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.
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).
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.
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).
Porównaj eksperymentalnie wydajność (faktyczną złożoność czasową) wyznaczania histogramu (np. zliczania wystąpień słów):
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
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”.
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
.
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.
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.
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.
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.
Zaimplementuj przykład wykorzystania “mixin modules” z Dominic Duggan, Constantinos Sourelis Mixin Modules [1] 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 [2]. 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.
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.
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”?
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:
Zaimplementuj przykład z zadania 7 listy 8 na trzy kolejne sposoby.
private
(wymaga OCamla 3.09). Przykładowe rozwiązanie: Private rows: abstracting the unnamed [4].
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.
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.
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.
Ćwiczenie 32 z http://caml.inria.fr/pub/docs/u3-ocaml/ocaml-mixins.html#toc19.
Zaprezentuj (zaimplementuj) model “subject - observer” na podstawie któregoś podręcznika do OCamla.
Copyright © 2005–2006 the Main wiki and its authors
Retrieved from http://ii.uni.wroc.pl/~lukstafi/pmwiki/index.php?n=ProgFun.Zadania
Page last modified on June 07, 2011, at 03:48 PM