Punktacja

Schemat tabelki z punktami:

(:scoretable grades="ndst 2.75 dst 3.25 dst+ 3.75 db 4.25 db+ 4.75 bdb" comput="s/170.0*5.0":)

(:endscoretable:)

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

module Weird (Top : sig end) = (struct

module Gen (X : functor (Top : sig end) → S) = X (struct end);;

module Weird (B : sig end) = (struct

module Gen (X : functor (B : sig end) → S) = X (struct end);;

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

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

(:source lang=ocaml:)

(:sourcend:)

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ę

óó

• 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)

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

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.

rozwiązanie ze stanu obliczeń, który może przechowywać dodatkowe

O funkcji f której pierwiastki będziesz obliczać możesz poczynić

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

“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)

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

zwróci string:

(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,

- dodawanie szeregów potęgowych

- mnożenie szeregów - dzielenie szeregów (wzór wyprowadź rozwijając równanie F = Q * G, by

- złożenie szeregów (F . G) (x) = F (G (x))

- trudniejsze: odwrotność funkcyjną szeregu, tzn. R w równaniu F(R(x)) = x

trudniejszy, wyznaczone z odpowiednich równań różniczkowych:

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

Wprowadź nazwę na typ szeregów:

przez toplevel odnosiły się do typów szeregów tylko przez nazwę

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

go z równości F*G = (f + xF1)*(g+xG1)), bez wyznaczania “za każdym

współdzieleniu wspólnych części, w przypadku modyfikacji węzła drzewa

ruchy kursora do przemieszczania do sąsiadujących węzłów. Wtedy udaje

stałym czasie, dzięki strukturze, którą Gerard Huet nazwał “Zipper”:

Typy algebraiczne (czyli warianty, sumy rozłączne produktów typów algebraicznych) dają bardzo wygodny sposób reprezentacji danych

funkcję, która dla zadanych danych wejściowych wygeneruje zadane dane

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

z pliku źródłowego).

tym samym argumentom przypisane są różne wyniki — obecnie program

wygenerowane funkcje. Przykładowe możliwości to wykorzystanie modułów

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.

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”:

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!

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

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

naturalnych, tzn. funkcji które dla obliczenia argumentu n potrzebują (co najwyżej) wartości dla argumentów mniejszych od n.

istotna). Napisz funkcję map_lBT która leniwie mapuje drzewo lBT

itr taką, jak w zadaniu 4 (a) z wykładu 5: która dla zadanej liczby

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.

począwszy od wierzchołka 1, traktując 0 jako szczególny przypadek:

Jaka jest zaleta tej metody memoizacji w porównaniu z metodą

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

• 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)

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

rozwiązywania równania y' = f (y, t), y(t0)=y0, zazwyczaj

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

Stop gdy Cj*Dj prawie równe 1.

Porównaj wydajność wersji imperatywnej i funkcyjnej.

Zastanów się nad podobieństwami i różnicami “dynamicznie

Zaimplementuj wznawialne wyjątki: mechanizm, w którym fragment

Napisz rozwiązywaczkę do “gry w 8″: gry, w której na prostokątnej

jest sprowadzenie planszy do sytuacji, w której kwadraty umieszczone

kwadratów, przy czym jeden z zamienianych kwadratów musi mieć numer 0

Testuj program dla duuużych plansz, stopniując trudność ilością ruchów

przypadkowych ruchów do konfiguracji będącej rozwiązaniem.

(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.)

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ł

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.

(lista elementów). Nie wymagaj od użytkownika podawania jakichś

Wytłumacz, jakie udogodnienie systemu modułów w OCamlu pozwala na

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

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.

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”?

“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:

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.

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.

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

ó

(:source lang=ocaml:)

(:sourcend:)

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.

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”?

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.

Warianty i rekordy to koncepcje w pewnym sensie dualne, dlatego zagadnienia dotyczące jednych przenoszą się na drugie. Nowy 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 8 moduły i funktory (zad.1, zad.2, zad.3, zad.4, zad.5, zad.6, zad.7, zad.8)

Zadanie 8.

Warianty i rekordy to koncepcje w pewnym sensie dualne, dlatego zagadnienia dotyczące jednych przenoszą się na drugie. Nowy 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 czy też “two-level types” zbuduj przykładową hierarchię typów rekordowych i napisz funkcje demonstrujące praktyczne zachodzenie podtypowania.

THE END.

• 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)

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.

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.

• lista 9 argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty (zad.1, zad.2, zad.3, zad.4)

Zadanie 7. The Expression Problem (Part I)

Zadanie 2. The Expression Problem (Part II)

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

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.

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.

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). Porównaj Private rows: abstracting the unnamed.
3. Przy pomocy klas, jak w http://pauillac.inria.fr/~remy/work/expr/.

 (‘a → ‘b * ‘c) → (‘d → ‘c → ‘d) → ‘d → ‘a list → (‘b * ‘d) list =

• lista 9 argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty (zad.1, zad.2, zad.3)

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

let map_reduce mapf redf red0 xs = … val map_reduce :

 ‘a list → (‘a → ‘b * ‘c) → (‘d → ‘c → ‘d) → ‘d → (‘b * ‘d) list =
 <fun>

Zapoznaj się z wariantami polimorficznymi http://caml.inria.fr/pub/docs/manual-ocaml/manual006.html, par. 4.2.

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 argumentó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.

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

Zaimplementuj przykład z zadania 7 listy 8 na dwa kolejne sposoby: przy pomocy wariantów polimorficznych i typów otwartych, oraz 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.

• lista 9 argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty (zad.1, zad.2)

Zaimplementuj przykład z zadania 7 listy 8 na dwa kolejne sposoby: przy pomocy wariantów polimorficznych i typów otwartych, oraz przy pomocy typów zamkniętych, jak w poprzednim zadaniu (czyli tak 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).

• lista 9 argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty (zad.1, [[#z92 | zad.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.

Zaimplementuj przykład z zadania 7 listy 8 na dwa kolejne sposoby: przy pomocy wariantów polimorficznych i typów otwartych, oraz przy pomocy typów zamkniętych “two-level types”, jak w poprzednim zadaniu (czyli tak 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).

• lista 9 argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty (zad.1)

Lista 9.

Zadanie 1.

“Zawiąż węzeł” następującej spłaszczonej wieży typów, tzn. podaj równoważną definicję, która się kompiluje:

type number =
    [ `NCst of num			(** numeric constant *)
    | `Ninf				(** positive infinity *)
    | `Neginf				(** negative infinity *)
    ]

type variable =
    [ `EVar of string			(** (existential) variable *)
    | `UVar of string			(** constant (universal
					    variable) *)
    ]

type num_coef =
    [ `Mult of num * variable		(** constant coefficient *)
    ]

type numeric =
    [ number | num_coef
    | `Add of num_coef list * number	(** linear combination *)
    ]
;;

type construct =
    [ `TCons of string * typ list
    | `Fun of proper_typ * proper_typ
    ]

and proper_typ = [variable | construct]

and typ = [proper_typ | numeric]
;;

P.S. Na następnej liście rozwiążemy ten problem bez wytaczania “ciężkiej machinerii” wieży typów czy “two-level types” (ale zdecydowanie poza SMLem), przy użyciu wariantów polimorficznych.

P.S. Na następnej liście rozwiążemy to zadanie bez wytaczania “ciężkiej machinerii” wieży typów czy “two-level types”, przy użyciu wariantów polimorficznych.

Zadanie 7.

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.

module Num =
mixin body
  type term = Const of int | Add of term * term
  type value = Num of int
  type env
  let rec eval tm (e:env) = match tm with
    | Const i -> Num i
    | Add (t1, t2) -> begin match eval t1, eval t2 with
      | Num i, Num j -> Num (i + j)
      | _ -> failwith "Num.eval: type mismatch"
      end
    | tm -> inner tm e
end (* Num *)

module Func =
mixin
  let bind (x, v, e) = fun y ->
    if x=y then v else e y
body
  type term = Var of string
    | Abs of string * term | App of term * term
  type value = Clos of term * env
  and env = string -> value
  let eval tm (e:env) = match tm with
    | Var x -> e x
    | Abs _ as f -> Clos (f, e)
    | App (rator, rand) e -> begin
      match eval rator e with
      | Clos (Abs (x, b), e') ->
        eval b (bind (x, eval rand e, e'))
      | _ -> failwith "Func.eval: type mismatch"
      end
    | _ -> inner tm e
end (* Func *)

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 poskładanie kawałków przez funktory.

• lista 8 moduły i funktory (zad.1, zad.2, zad.3, zad.4, zad.5, zad.6, zad.7)
• lista 9 argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty

• lista 8 moduły i funktory (zad.1, zad.2, zad.3, zad.4, zad.5, zad.6)

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

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/.)

1. Table2.compare s4 s3;;

• lista 9 argumenty etykietowane, argumenty domyślne, tzw. warianty polimorficzne, obiekty

• lista 8 moduły i funktory (zad.1, zad.2, zad.3, zad.4, zad.5, zad.6)

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

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*) Zaimplementuj w OCamlu bibliotekę dla grafów funkcyjnych (trwałych, “persistent”), np. w oparciu o http://web.engr.oregonstate.edu/~erwig/papers/abstracts.html#IFL97

Zadanie 2.

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

module type SYMBOL_TABLE = sig
 type symbol
 val string_to_symbol : string -> symbol
 val symbol_to_string : symbol -> string
 val eq : symbol -> symbol -> bool
 val compare : symbol -> symbol -> int
end;;

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
# Table1.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)

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

module type DICT = functor (Key : Set.OrderedType) -> sig
 type 'a dict
 val domain : 'a dict -> Set.Make(Key).t
end;;

module type PRIO_QUEUE = functor (Elt : Set.OrderedType) -> sig
 type queue
 val contents : queue -> Set.Make(Elt).t
end;;

module QueuedDict (Data : Set.OrderedType)
 (MyDict : DICT) (MyPrioQueue : PRIO_QUEUE) =
struct
 module Dict = MyDict (Data)
 module PQ = MyPrioQueue (Data)
 module DataSet = Set.Make (Data)
 let queued_domain dict pq =
   DataSet.equal (Dict.domain dict) (PQ.contents pq)
end;;

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

let moonFull = let v = ref false in fun () -> v := not !v; !v
;;

module type S = sig
 type t
 val x : t
 val f : t -> t
 val g : t -> t -> bool
end;;

module Weird (Top : sig end) = (struct
 type t = int
 let x = if moonFull () then 1 else 2
 let f x = x + 2
 let g x y = (3*x + 2*y) / (x - y + 1) = 7
end : S);;

module Gen (X : functor (Top : sig end) -> S) = X (struct end);;

module W1 = Gen (Weird);; (* moon full now *)
module W2 = Gen (Weird);; (* moon no longer full now *)
W1.g W1.x W2.x;;

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

module W3 = Weird (struct end);;
module W4 = Weird (struct end);;
W3.g W3.x W4.x;;
4 = W1.x;;

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):

module type ORDERED =
sig
 type t
 val eq: t -> t -> bool
 val lt: t -> t -> bool
 val leq: t -> t -> bool
end

module type HEAP =
sig
 module Elem: ORDERED
 type heap
 val empty: heap
 val isEmpty: heap -> bool
 val insert: Elem.t -> heap -> heap
 val merge: heap -> heap -> heap
 val findMin: heap -> Elem.t
 val deleteMin: heap -> heap
end

module Bootstrap (MakeH: functor (Element:ORDERED) ->
 HEAP with module Elem = Element)
 (Element: ORDERED) : HEAP with module Elem = Element =
struct
 module Elem = Element
 module rec BE
   : sig type t = E | H of Elem.t * PrimH.heap
         val eq: t -> t -> bool
         val lt: t -> t -> bool
         val leq: t -> t -> bool
   end = struct
     type t = E | H of Elem.t * PrimH.heap
     let leq (H(x, _)) (H(y, _)) = Elem.leq x y
     let eq (H(x, _)) (H(y, _)) = Elem.eq x y
     let lt (H(x, _)) (H(y, _)) = Elem.lt x y
   end
 and PrimH
   : HEAP with type Elem.t = BE.t
   = MakeH(BE)
 type heap = BE.t
 let empty = BE.E
 let isEmpty = function BE.E -> true | _ -> false
 let rec merge x y =
   match (x,y) with
       (BE.E, _) -> y
     | (_, BE.E) -> x
     | (BE.H(e1,p1) as h1), (BE.H(e2,p2) as h2) ->
         if Elem.leq e1 e2
         then BE.H(e1, PrimH.insert h2 p1)
         else BE.H(e2, PrimH.insert h1 p2)
 let insert x h =
   merge (BE.H(x, PrimH.empty)) h
 let findMin = function
     BE.E -> raise Not_found
   | BE.H(x, _) -> x
 let deleteMin = function
     BE.E -> raise Not_found
   | BE.H(x, p) ->
       if PrimH.isEmpty p then BE.E else begin
         let (BE.H(y, p1)) = PrimH.findMin p in
         let p2 = PrimH.deleteMin p in
         BE.H(y, PrimH.merge p1 p2)
       end
end

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

• imperatywnie przez iterację, przy pomocy tablicy haszującej (moduł Hashtbl) klucz:słowo - wartość:liczba wystąpień

• 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)

skompilowany i zzipowany plik z rozszerzeniem składniowym Δ

• lista 7 programowanie imperatywne (zad.1, zad.2, zad.3, zad.4, zad.5)

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.

skompilowany plik z rozszerzeniem składniowym Δ

• lista 7 programowanie imperatywne (zad.1, zad.2, zad.3, zad.4)

Zadanie 4.

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

• 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)

Zadanie 1.

Zadanie 2.

Zadanie 1.

Zadanie 2.

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

Zadanie 1.

Zadanie 2.

Zadanie 1.

Zadanie 2. (Propozycja projektu.)

Zadanie 1.

Zadanie 2.

Zadanie 3.

Zadanie 4.

Zadanie 1.

Zadanie 2.

Zadanie 3. (Problem Hamminga)

Zadanie 4. Ciągi liczbowe.

Zadanie 1.

Zadanie 2.

Zadanie 3.

• lista 1 funkcje wyższego rzędu i manipulowanie listami
• lista 2 jak wyżej
• lista 3 funkcje jako wartości, budowanie funkcji z funkcji
• lista 4 typy algebraiczne (warianty)
• lista 5 przerywnikowa
• lista 6 leniwe (korekurencyjne) struktury danych
• lista 7 programowanie imperatywne

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. Ciągi liczbowe.

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

type 'a sequence =
     (* constant sequence: Cs h ~= [h; h; h; ...] *)
 | Cs of 'a
     (* generic sequence: S (x, xs) ~= x::xs *)
 | S of 'a * 'a sequence lazy_t
     (* differential sequence: for ds ~= [d0; d1; d2; ...], A(x0, ds) ~= [x0;
        x0+d0; x0+d0+d1; x0+d0+d1+d2; ...] *)
 | A of 'a * 'a sequence lazy_t
     (* generalized geometric progression: for ds ~= [d0; d1; d2; ...],
        G(x0,ds) ~= [x0; x0*d0; x0*d0*d1; x0*d0*d1*d2; ...] *)
 | G of 'a * 'a sequence lazy_t
;;

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

@]

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. (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:

type 'a llist = LNil | LCons of 'a * 'a llist lazy_t;;
let rec ltake n = function
 | LCons (a, ll) when n > 0 -> a::(ltake (n-1) (Lazy.force ll))
 | _ -> []
;;
let rec lfrom n = LCons (n, lazy (lfrom (n+1)));;
let rec lfilter f = function
 | LNil -> LNil
 | LCons (n, ll) ->
     if f n then LCons (n, lazy (lfilter f (Lazy.force ll)))
     else lfilter f (Lazy.force ll)
;;
let primes =
 let rec sieve = function
     LCons(p,nf) -> LCons(p, lazy (sieve (sift p (Lazy.force nf))))
   | LNil -> failwith "Impossible! Internal error."
 and sift p = lfilter (function n -> n mod p <> 0)
in sieve (lfrom 2)
;;

let times ll n = lmap (fun i -> i * n) ll;;

let rec merge xs ys = match xs, ys with
 | LCons (x, xr), LCons (y, yr) ->
     if x < y then LCons (x, lazy (merge (Lazy.force xr) ys))
     else if x > y then LCons (y, lazy (merge xs (Lazy.force yr)))
     else LCons (x, lazy (merge (Lazy.force xr) (Lazy.force yr)))
 | r, LNil | LNil, r -> r
;;

let hamming k =
 let pr = ltake k primes in
 let rec h = LCons (1, lazy (
   <TODO> )) in
 h
;;

Listy:

• lista 1
• lista 2
• lista 3
• lista 4
• lista 5
• lista 6

Lista 1

Zadanie 1.

Zadanie 2.

Dodatkowe wskazówki do zadania map_reduce z “listy 1″:

Lista 2

Zadanie 1.

Zadanie 2.

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

Instalacja rozszerzenia składniowego:

Lista 3.

Zadanie 1.

Zadanie 2.

Dalsze uwagi.

Lista 4

Zadanie 1.

Zadanie 2. (Propozycja projektu.)

Lista 5

Zadanie 1.

Zadanie 2.

Zadanie 3.

Zadanie 4.

Lista 6.

Zadanie 1.

Zadanie 2.

Zadanie 2.

Lista 6.

Zadanie 1.

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

(* implementation by function closures *)

type 'a lflist = LFNil | LFCons of 'a * (unit -> 'a lflist);;

let rec lfzip = function
 | LFNil, LFNil -> LFNil
 | LFCons (a1, lf1), LFCons (a2, lf2) ->
     LFCons ((a1, a2), fun () -> lfzip (lf1 (), lf2 ()))
 | _ -> raise (Invalid_argument "lfzip")
;;
let rec lfmap f = function
 | LFNil -> LFNil
 | LFCons (a, lf) -> LFCons (f a, fun () -> lfmap f (lf ()))
;;
let rec lffib = LFCons (1, fun () -> lfmap (fun (a,b)-> a+b) (lfzip
 (lffib, LFCons (1, fun () -> lffib))))
;;
let rec lftake n = function
 | LFCons (a, lf) when n > 0 -> a::(lftake (n-1) (lf ()))
 | _ -> []
;;

(* implementation by native lazy values *)

type 'a llist = LNil | LCons of 'a * 'a llist lazy_t;;

let rec lzip = function
 | LNil, LNil -> LNil
 | LCons (a1, ll1), LCons (a2, ll2) ->
     LCons ((a1, a2), lazy (lzip (Lazy.force ll1, Lazy.force ll2)))
 | _ -> raise (Invalid_argument "lzip")
;;
let rec lmap f = function
 | LNil -> LNil
 | LCons (a, ll) -> LCons (f a, lazy (lmap f (Lazy.force ll)))
;;
let rec lfib = LCons (1, lazy (lmap (fun (a,b)-> a+b) (lzip
 (lfib, LCons (1, lazy lfib)))))
;;
let rec ltake n = function
 | LCons (a, ll) when n > 0 -> a::(ltake (n-1) (Lazy.force ll))
 | _ -> []
;;

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

lftake 17 lffib;;

a

ltake 17 lfib;;

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:

(int -> int) -> int -> int

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

let fib f n = if n < 2 then 1 else f (n-1) + f (n-2);;

Napisz funkcję memoize taką, że np.

let fib_memo = memoize fib;;
- : int -> int = <fun>

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:

type 'a lBT = LEmpty
 | LNode of 'a * 'a lBT lazy_t * 'a lBT lazy_t;;

(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:

f (fun _ -> raise Not_found) 0

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

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:

type 'a span_tree = Node of 'a * 'a span_tree list * 'a list

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:

let try X = GUARDED
in BODY
with EXC1 -> HANDLER1 | ... | EXCn -> HANDLERn

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.

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

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.

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”.)

Dodatkowe wskazówki do zadania map_reduce z “listy 1″:

Napisz funkcję

let map_reduce fmap freduce v0 xs = ...

obliczającą listę par klucz-wartość przez “List.map fmap xs”, grupującą wartości o tym samym kluczu w listy “intermediate”, oraz zwracające listę par klucz-nowa wartość, gdzie nowa wartość = List.fold_left freduce v0 intermediate.

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:

let fs = format (lit "Napis " $$ str $$ lit " oraz lista list liczb "
  $$ lis (lis int) $$ eol)

ma zdefiniować funkcję o typie:

string -> int list list -> string

i zastosowanie

fs "graf" [[1; 2]; [1]; []]

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.

type 'a stream = unit -> 'a * 'a stream

Strumień liczb naturalnych:

let nats = let rec aux i () = i, aux (i+1) in aux 0

Podglądanie strumienia:

let rec take n s =
 if n <= 0 then [] else let hd, tl = s () in hd :: (take (n-1) tl)

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

let display n s = String.concat " + "
 (List.map2 (fun i v -> (Num.string_of_num v)^"x^"^(string_of_int i))
   (take n nats) (take n s))

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

exp = 1 + (integral exp)

co w naszej implementacji zapisuje się jako:

let ni = Num.num_of_int
let rec exp () =
 let h,t = integral exp () in h +/ ni 1, t

Wytłumacz, dlaczego przy alternatywnej definicji:

let rec exp' () = (cst 1 +$ integral exp') ()

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

Dalsze uwagi.

Wprowadź nazwę na typ szeregów:

type 'a stream = unit -> 'a * 'a stream;;
type series = Num.num stream;;

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

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 Δ

funind.ml Δ