Emacs Artificial General Intelligence Algorithmic Game Theory: Prediction Markets (po polsku) Systemy Inteligentnych Agentów
|
ProgFun.Zadania HistoryHide minor edits - Show changes to output Added lines 17-37:
!! Punktacja Schemat tabelki z punktami: ||border=1 ||!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 (:scoretable grades="ndst 2.75 dst 3.25 dst+ 3.75 db 4.25 db+ 4.75 bdb" comput="s/170.0*5.0":) ||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|| (: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 October 01, 2007, at 02:07 PM
by - Undo: it is top.
Changed line 762 from:
module Weird ( to:
module Weird (Top : sig end) = (struct Changed lines 769-770 from:
module Gen (X : functor ( to:
module Gen (X : functor (Top : sig end) -> S) = X (struct end);; October 01, 2007, at 01:59 PM
by - it was rather Bottom than Top, right?
Changed line 762 from:
module Weird ( to:
module Weird (B : sig end) = (struct Changed lines 769-770 from:
module Gen (X : functor ( to:
module Gen (X : functor (B : sig end) -> S) = X (struct end);; May 13, 2007, at 11:23 PM
by - zipper iterators
Added lines 270-271:
Rozwinięcie: [[http://www.lri.fr/Rapports-internes/2006/RR1428.pdf]] Deleted lines 4-5:
Changed line 123 from:
to:
(:source lang=ocaml:) Changed lines 126-127 from:
to:
(:sourcend:) Changed line 130 from:
to:
(:source lang=ocaml:) Changed lines 132-133 from:
to:
(:sourcend:) Changed line 136 from:
to:
(:source lang=ocaml:) Changed lines 138-139 from:
to:
(:sourcend:) Changed line 157 from:
to:
(:source lang=ocaml:) Changed lines 159-160 from:
to:
(:sourcend:) Changed line 163 from:
to:
(:source lang=ocaml:) Changed lines 165-166 from:
to:
(:sourcend:) Changed line 169 from:
to:
(:source lang=ocaml:) Changed lines 172-173 from:
to:
(:sourcend:) Changed line 181 from:
to:
(:source lang=ocaml:) Changed lines 185-186 from:
to:
(:sourcend:) Changed line 203 from:
to:
(:source lang=ocaml:) Changed lines 205-206 from:
to:
(:sourcend:) Changed line 209 from:
to:
(:source lang=ocaml:) Changed lines 213-214 from:
to:
(:sourcend:) Changed line 217 from:
to:
(:source lang=ocaml:) Changed lines 219-220 from:
to:
(:sourcend:) Changed line 227 from:
to:
(:source lang=ocaml:) Changed lines 230-231 from:
to:
(:sourcend:) Changed line 335 from:
to:
(:source lang=ocaml:) Changed lines 337-338 from:
to:
(:sourcend:) Changed line 359 from:
to:
(:source lang=ocaml:) Changed lines 363-364 from:
to:
(:sourcend:) Changed line 377 from:
to:
(:source lang=ocaml:) Changed lines 421-422 from:
to:
(:sourcend:) Changed line 425 from:
to:
(:source lang=ocaml:) Changed lines 427-428 from:
to:
(:sourcend:) Changed line 431 from:
to:
(:source lang=ocaml:) Changed lines 433-434 from:
to:
(:sourcend:) Changed line 444 from:
to:
(:source lang=ocaml:) Changed lines 446-447 from:
to:
(:sourcend:) Changed line 450 from:
to:
(:source lang=ocaml:) Changed lines 452-453 from:
to:
(:sourcend:) Changed line 456 from:
to:
(:source lang=ocaml:) Changed lines 459-460 from:
to:
(:sourcend:) Changed line 465 from:
to:
(:source lang=ocaml:) Changed lines 468-469 from:
to:
(:sourcend:) Changed line 481 from:
to:
(:source lang=ocaml:) Changed lines 483-484 from:
to:
(:sourcend:) Changed line 503 from:
to:
(:source lang=ocaml:) Changed lines 540-541 from:
to:
(:sourcend:) Changed line 545 from:
to:
(:source lang=ocaml:) Changed lines 558-559 from:
to:
(:sourcend:) Changed line 676 from:
to:
(:source lang=ocaml:) Changed lines 684-685 from:
to:
(:sourcend:) Changed line 725 from:
to:
(:source lang=ocaml:) Changed lines 745-746 from:
to:
(:sourcend:) Changed line 749 from:
to:
(:source lang=ocaml:) Changed lines 772-773 from:
to:
(:sourcend:) Changed line 777 from:
to:
(:source lang=ocaml:) Changed lines 782-783 from:
to:
(:sourcend:) Changed line 792 from:
to:
(:source lang=ocaml:) Changed lines 857-858 from:
to:
(:sourcend:) Changed line 864 from:
to:
(:source lang=ocaml:) Changed lines 899-900 from:
to:
(:sourcend:) Changed line 917 from:
to:
(:source lang=ocaml:) Changed lines 949-950 from:
to:
(:sourcend:) Changed lines 1-2 from:
Zadania na ćwiczenia będą się składać z: zadań z wykł to:
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ę Changed lines 5-6 from:
ó to:
óó Changed lines 17-18 from:
* [[#l9 | lista 9]] argumenty etykietowane, domyślne wartości to:
* [[#l9 | lista 9]] argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty ([[#z91 | zad.1]], [[#z92 | zad.2]], [[#z93 | zad.3]], [[#z94 | zad.4]], [[#z95 | zad.5]], [[#z96 | zad.6]], [[#z97 | zad.7]]) Changed lines 50-51 from:
to:
Trójkąt o bokach a, b, c ma pole A dane wzorem: Changed lines 57-59 from:
Znajdź wszystkie nie większą od n, to:
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. Changed line 75 from:
rozwiązanie ze stanu obliczeń, to:
rozwiązanie ze stanu obliczeń, który może przechowywać dodatkowe Changed line 79 from:
O funkcji @@f@@ to:
O funkcji @@f@@ której pierwiastki będziesz obliczać możesz poczynić Changed lines 89-90 from:
zgodnie z komentarzem w pliku ź to:
zgodnie z komentarzem w pliku źródłowym: Changed lines 113-115 from:
"nieoszukany" wariant funkcji [@Printf.sprintf@]) w następujący Napisz funkcje będące "dyrektywami * @@lit@@ dla literał to:
"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) Changed lines 118-121 from:
* @@str@@ dla wstawiania * @@lis@@ dla wstawiania list Napisz funkcj z dyrektyw to:
* @@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. Changed lines 142-143 from:
to:
zwróci string: Changed lines 148-149 from:
(lub ze średnikami zamiast to:
(lub ze średnikami zamiast przecinków). Changed lines 152-153 from:
Na leniwej. My teraz zdefiniujemy szczególny to:
Na którymś z kolejnych wykładów zostanie wprowadzone pojęcie listy leniwej. My teraz zdefiniujemy szczególny przypadek listy leniwej, Changed line 192 from:
- dodawanie to:
- dodawanie szeregów potęgowych Changed lines 194-195 from:
- mnożenie to:
- mnożenie szeregów - dzielenie szeregów (wzór wyprowadź rozwijając równanie F = Q * G, by Changed line 197 from:
- złożenie to:
- złożenie szeregów (F . G) (x) = F (G (x)) Changed line 199 from:
- trudniejsze: odwrotność funkcyjną szeregu, tzn. R w to:
- trudniejsze: odwrotność funkcyjną szeregu, tzn. R w równaniu F(R(x)) = x Changed lines 201-204 from:
trudniejszy, wyznaczone z odpowiednich Np. to:
trudniejszy, wyznaczone z odpowiednich równań różniczkowych: Np. z równania na exp: "dy/dx = y, y(0) = 1" dostajemy Changed lines 227-228 from:
Wprowadź nazwę na typ to:
Wprowadź nazwę na typ szeregów: Changed line 235 from:
przez toplevel odnosiły się do to:
przez toplevel odnosiły się do typów szeregów tylko przez nazwę Changed lines 240-241 from:
Annotacja typem to wyrażenie lub wzorzec [@(expr : typ)@], @@typ@@, o ile @@typ@@ jest to:
Annotacja typem to wyrażenie lub wzorzec [@(expr : typ)@], którego typem jest @@typ@@, o ile @@typ@@ jest szczególnym przypadkiem najogólniejszego typu Changed line 245 from:
go z to:
go z równości F*G = (f + xF1)*(g+xG1)), bez wyznaczania "za każdym Changed line 256 from:
to:
współdzieleniu wspólnych części, w przypadku modyfikacji węzła drzewa Changed line 263 from:
ruchy kursora do przemieszczania do sąsiadujących węzł to:
ruchy kursora do przemieszczania do sąsiadujących węzłów. Wtedy udaje Changed lines 265-266 from:
stałym czasie, dzięki strukturze, to:
stałym czasie, dzięki strukturze, którą Gerard Huet nazwał "Zipper": Changed lines 276-277 from:
Typy algebraiczne (czyli warianty, sumy rozłączne algebraicznych) daj to:
Typy algebraiczne (czyli warianty, sumy rozłączne produktów typów algebraicznych) dają bardzo wygodny sposób reprezentacji danych Changed line 280 from:
funkcję, to:
funkcję, która dla zadanych danych wejściowych wygeneruje zadane dane Changed line 286 from:
w to:
w szczególności z rozdziałem "Generalizing Decision Tree Learning to Changed lines 298-299 from:
z pliku ź to:
z pliku źródłowego). Changed line 306 from:
tym samym argumentom przypisane są to:
tym samym argumentom przypisane są różne wyniki -- obecnie program Changed line 320 from:
wygenerowane funkcje. Przykładowe możliwości to wykorzystanie moduł to:
wygenerowane funkcje. Przykładowe możliwości to wykorzystanie modułów Changed line 334 from:
Zbuduj dowolne drzewo rozpinające dla grafu danego jako lista par wierzchołek, lista wierzchoł to:
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. Changed lines 342-343 from:
Dzielimy wierzchołki drzewa na lekkie i ciężkie jak następuje: korzeń jest lekki, wszyscy synowie, to:
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. Changed lines 345-346 from:
W Pythonie mechanizm wyją to:
W Pythonie mechanizm wyjątków pozwala zdefiniować klauzulę "else": Changed lines 367-368 from:
w to:
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! Changed lines 377-378 from:
to:
Porównaj następujące dwie implementacje list leniwych: Changed lines 425-426 from:
Wytłumacz to:
Wytłumacz różnicę w złożoności pomiędzy obliczeniem Changed lines 441-442 from:
naturalnych, tzn. funkcji (co najwyżej) wartości dla to:
naturalnych, tzn. funkcji które dla obliczenia argumentu @@n@@ potrzebują (co najwyżej) wartości dla argumentów mniejszych od @@n@@. Changed line 473 from:
istotna). Napisz funkcję @@map_lBT@@ to:
istotna). Napisz funkcję @@map_lBT@@ która leniwie mapuje drzewo @@lBT@@ Changed line 475 from:
@@itr@@ taką, jak w zadaniu 4 (a) z wykładu 5: to:
@@itr@@ taką, jak w zadaniu 4 (a) z wykładu 5: która dla zadanej liczby Changed lines 478-479 from:
funkcję @@nth_node@@, wierzchołka, to:
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@@. Changed lines 481-482 from:
począwszy od wierzchołka 1, traktując 0 jako to:
począwszy od wierzchołka 1, traktując 0 jako szczególny przypadek: Changed line 487 from:
Jaka jest zaleta tej metody memoizacji w to:
Jaka jest zaleta tej metody memoizacji w porównaniu z metodą Changed lines 545-546 from:
Użyjemy poręcznego typu do reprezentacji cią to:
Użyjemy poręcznego typu do reprezentacji ciągów. Changed line 566 from:
* @@x_to_S@@ konwertującą ciąg do postaci to:
* @@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) Changed lines 570-571 from:
Czemu są to:
Czemu są równe: [@exp (A x r)@], [@sqrt (G x q)@], [@log (G x q)@], [@n!@]? Changed line 573 from:
rozwiązywania to:
rozwiązywania równania [@y' = f (y, t), y(t0)=y0@], zazwyczaj Changed lines 582-583 from:
Zakoduj algorytm Lentza obliczania uł to:
Zakoduj algorytm Lentza obliczania ułamków łańcuchowych: Changed lines 593-594 from:
Stop gdy C'_j_'*D'_j_' prawie to:
Stop gdy C'_j_'*D'_j_' prawie równe 1. Changed lines 607-608 from:
to:
Porównaj wydajność wersji imperatywnej i funkcyjnej. Changed line 614 from:
to:
Zastanów się nad podobieństwami i różnicami "dynamicznie Changed line 617 from:
Zaimplementuj wznawialne wyjątki: mechanizm, w to:
Zaimplementuj wznawialne wyjątki: mechanizm, w którym fragment Changed line 624 from:
Napisz rozwiązywaczkę do "gry w 8": gry, w to:
Napisz rozwiązywaczkę do "gry w 8": gry, w której na prostokątnej Changed line 627 from:
jest sprowadzenie planszy do sytuacji, w to:
jest sprowadzenie planszy do sytuacji, w której kwadraty umieszczone Changed line 631 from:
to:
kwadratów, przy czym jeden z zamienianych kwadratów musi mieć numer 0 Changed line 634 from:
Testuj program dla duuużych plansz, stopniując trudność ilością to:
Testuj program dla duuużych plansz, stopniując trudność ilością ruchów Changed lines 636-637 from:
przypadkowych to:
przypadkowych ruchów do konfiguracji będącej rozwiązaniem. Changed lines 645-654 from:
(listy) Zmiana konfiguracji aktualnej na by (zrobienie konfiguracją zapamiętaną, i następnie wykonanie brakujących konfiguracji zapami pocz wspó to:
(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). Changed lines 656-657 from:
wyznaczania to:
Porównaj eksperymentalnie wydajność (faktyczną złożoność czasową) wyznaczania histogramu (np. zliczania wystąpień słów): Changed lines 663-664 from:
Wykorzystując rozszerzenie składniowe [@let try@] (patrz zadanie 4 z listy 5), napisz funkcję, to:
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.) Changed lines 671-674 from:
a) Zapoznaj się z ideą " b) Zapoznaj się z biblioteką "ocamlgraph": [[http://www.lri.fr/~filliatr/ocamlgraph/]]. (*) Napisz funktor dodający operację dekompozycji z " to:
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". Changed lines 676-677 from:
Wygeneruj to:
Wygeneruj współdzielące kod moduły o sygnaturze: Changed lines 688-689 from:
tak, że @@compare@@ jest funkcją to:
tak, że @@compare@@ jest funkcją porównującą zgodną ze specyfikacją [@Pervasives.compare@], przy czym symbol mniejszy to ten, który był Changed lines 707-708 from:
Do efektywnego odwzorowania ze to:
Do efektywnego odwzorowania ze stringów w symbole wykorzystaj moduł @@Hashtbl@@. Changed lines 710-713 from:
Zobacz, w jaki Podaj przykład praktycznej instancjacji funktora realizującego algorytm z dziedziny twojego projektu (tzn. nie implementującego kontener ani odwzorowanie) to:
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. Changed line 720 from:
(lista to:
(lista elementów). Nie wymagaj od użytkownika podawania jakichś Changed line 724 from:
Wytłumacz, jakie udogodnienie systemu moduł to:
Wytłumacz, jakie udogodnienie systemu modułów w OCamlu pozwala na Changed lines 861-862 from:
to:
Zrób ćwiczenie 10.8 z książki. Changed lines 864-865 from:
Zaimplementuj przykład wykorzystania "mixin modules" z [[http://citeseer.ist.psu.edu/duggan96mixin.html | Dominic Duggan, Constantinos Sourelis ''Mixin Modules'']] poszerzony o operację dodawania w module @@Num@@. Idea jest taka: typy i funkcje składamy z to:
Zaimplementuj przykład wykorzystania "mixin modules" z [[http://citeseer.ist.psu.edu/duggan96mixin.html | 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. Changed lines 903-904 from:
Moduły "mixinowe" to:
Moduły "mixinowe" przerób na funktory wykorzystując pomysły z [[http://www.eecs.harvard.edu/~nr/pubs/maniaws-abstract.html | 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. Changed lines 906-909 from:
Wieżą "Two-level types" to generalnie rozci to:
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. Changed lines 911-912 from:
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 to:
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"? Changed lines 917-918 from:
"Zawiąż węzeł" (najpierw rozetnij ten za ciasno związany) następującej spłaszczonej wieży to:
"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: Changed lines 956-959 from:
# Przy pomocy # Przy pomocy to:
# 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: [[http://www.math.nagoya-u.ac.jp/~garrigue/papers/variant-reuse.ps.gz | Code reuse through polymorphic variants.]] # 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: [[http://www.math.nagoya-u.ac.jp/~garrigue/papers/privaterows-aplas2006.pdf | Private rows: abstracting the unnamed]]. Changed lines 964-965 from:
Zamień funkcję [@map_reduce@] z [[#z12 | zad.2 listy 1]] na funkcję, to:
Zamień funkcję [@map_reduce@] z [[#z12 | 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. Changed lines 967-968 from:
Zdefiniuj hierarchię klas (albo to:
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. Changed lines 970-971 from:
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 to:
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. Changed lines 976-977 from:
Zaprezentuj (zaimplementuj) model "subject - observer" na podstawie to:
Zaprezentuj (zaimplementuj) model "subject - observer" na podstawie któregoś podręcznika do OCamla. Changed line 33 from:
to:
(:source lang=ocaml:) Changed lines 38-39 from:
to:
(:sourcend:) Added lines 903-907:
!!!! 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. Changed lines 904-905 from:
Warianty i rekordy to koncepcje w pewnym sensie dualne, dlatego zagadnienia dotyczące jednych przenoszą się na drugie. to:
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"? Changed lines 901-902 from:
Moduły "mixinowe" przerób na funktory wykorzystując pomysły z [[http://www.eecs.harvard.edu/~nr/pubs/maniaws-abstract.html | 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. to:
Moduły "mixinowe" przerób na funktory wykorzystując pomysły z [[http://www.eecs.harvard.edu/~nr/pubs/maniaws-abstract.html | 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. Changed lines 904-905 from:
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 to:
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"? Changed line 14 from:
* [[#l8 | lista 8]] moduły i funktory ([[#z81 | zad.1]], [[#z82 | zad.2]], [[#z83 | zad.3]], [[#z84 | zad.4]], [[#z85 | zad.5]], [[#z86 | zad.6]], [[#z87 | zad.7]]) to:
* [[#l8 | lista 8]] moduły i funktory ([[#z81 | zad.1]], [[#z82 | zad.2]], [[#z83 | zad.3]], [[#z84 | zad.4]], [[#z85 | zad.5]], [[#z86 | zad.6]], [[#z87 | zad.7]], [[#z88 | zad.8]]) Added lines 903-905:
!!! [[#z88]] 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. Changed lines 15-16 from:
* [[#l9 | lista 9]] argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty ([[#z91 | zad.1]], [[#z92 | zad.2]], [[#z93 | zad.3]], [[#z94 | zad.4]]) to:
* [[#l9 | lista 9]] argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty ([[#z91 | zad.1]], [[#z92 | zad.2]], [[#z93 | zad.3]], [[#z94 | zad.4]], [[#z95 | zad.5]], [[#z96 | zad.6]], [[#z97 | zad.7]]) Changed lines 960-966 from:
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. to:
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. !!! [[#z96]] Zadanie 6. Ćwiczenie 32 z [[http://caml.inria.fr/pub/docs/u3-ocaml/ocaml-mixins.html#toc19]]. !!! [[#z97]] Zadanie 7. Zaprezentuj (zaimplementuj) model "subject - observer" na podstawie któregoś podręcznika do OCamla. Added lines 959-960:
!!! [[#z95]] 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. Changed lines 15-16 from:
* [[#l9 | lista 9]] argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty ([[#z91 | zad.1]], [[#z92 | zad.2]], [[#z93 | zad.3]]) to:
* [[#l9 | lista 9]] argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty ([[#z91 | zad.1]], [[#z92 | zad.2]], [[#z93 | zad.3]], [[#z94 | zad.4]]) Changed line 861 from:
!!! [[#z87]] Zadanie 7. to:
!!! [[#z87]] Zadanie 7. The Expression Problem (Part I) Deleted lines 902-903:
Changed line 943 from:
!!! [[#z92]] Zadanie 2. to:
!!! [[#z92]] Zadanie 2. The Expression Problem (Part II) Changed lines 948-949 from:
# Przy pomocy wariantów polimorficznych i typów otwartych. Typ otwarty w sygnaturze poprzedzamy słowem kluczowym @@private@@ (wymaga OCamla 3.09). to:
# 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: [[http://www.math.nagoya-u.ac.jp/~garrigue/papers/privaterows-aplas2006.pdf | Private rows: abstracting the unnamed]]. Added line 952:
Added lines 957-958:
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. Changed lines 955-956 from:
Zamień funkcję [@map_reduce@] z [[#z12 | 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 to:
Zamień funkcję [@map_reduce@] z [[#z12 | 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. Changed lines 946-947 from:
Zaimplementuj przykład z zadania 7 listy 8 na to:
Zaimplementuj przykład z zadania 7 listy 8 na trzy kolejne sposoby. # 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: [[http://www.math.nagoya-u.ac.jp/~garrigue/papers/variant-reuse.ps.gz | Code reuse through polymorphic variants.]] # Przy pomocy wariantów polimorficznych i typów otwartych. Typ otwarty w sygnaturze poprzedzamy słowem kluczowym @@private@@ (wymaga OCamla 3.09). Porównaj [[http://www.math.nagoya-u.ac.jp/~garrigue/papers/privaterows-aplas2006.pdf | Private rows: abstracting the unnamed]]. # Przy pomocy klas, jak w [[http://pauillac.inria.fr/~remy/work/expr/]]. Changed line 36 from:
'a to:
('a -> 'b * 'c) -> ('d -> 'c -> 'd) -> 'd -> 'a list -> ('b * 'd) list = Changed lines 15-16 from:
* [[#l9 | lista 9]] argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty ([[#z91 | zad.1]], [[#z92 | zad.2]]) to:
* [[#l9 | lista 9]] argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty ([[#z91 | zad.1]], [[#z92 | zad.2]], [[#z93 | zad.3]]) Changed lines 31-34 from:
Napisz funkcj to:
Zachowaj pełną polimorficzność, tzn. sygnaturę: Changed lines 34-37 from:
let map_reduce to:
let map_reduce mapf redf red0 xs = ... val map_reduce : 'a list -> ('a -> 'b * 'c) -> ('d -> 'c -> 'd) -> 'd -> ('b * 'd) list = <fun> Deleted lines 39-44:
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@]. Added line 908:
Zapoznaj się z wariantami polimorficznymi [[http://caml.inria.fr/pub/docs/manual-ocaml/manual006.html]], par. 4.2. Added lines 947-951:
!!! [[#z93]] Zadanie 3. Zamień funkcję [@map_reduce@] z [[#z12 | 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. !!! [[#z94]] Zadanie 4. Changed lines 676-677 from:
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". to:
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". Changed line 950 from:
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 to:
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: [[http://www.math.nagoya-u.ac.jp/~garrigue/papers/variant-reuse.ps.gz | Code reuse through polymorphic variants.]] Changed lines 15-16 from:
* [[#l9 | lista 9]] argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty ([[#z91 | zad.1]], [[#z92 | zad.2) to:
* [[#l9 | lista 9]] argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty ([[#z91 | zad.1]], [[#z92 | zad.2]]) Changed line 950 from:
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 to:
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). Changed lines 15-16 from:
* [[#l9 | lista 9]] argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty ([[#z91 | zad.1]]) to:
* [[#l9 | lista 9]] argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty ([[#z91 | zad.1]], [[#z92 | zad.2) Changed lines 913-914 from:
"Zawiąż węzeł" następującej spłaszczonej wieży typów, tzn. podaj równoważną definicję, która się kompiluje: to:
"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: Added lines 948-950:
!!! [[#z92]] 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). Changed lines 15-16 from:
* to:
* [[#l9 | lista 9]] argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty ([[#z91 | zad.1]]) Added lines 909-947:
!! [[#l9]] Lista 9. !!! [[#z91]] 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] ;; @] Changed line 908 from:
P.S. Na następnej liście rozwiążemy to:
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. Added lines 907-908:
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. Added lines 865-906:
!!! [[#z87]] Zadanie 7. Zaimplementuj przykład wykorzystania "mixin modules" z [[http://citeseer.ist.psu.edu/duggan96mixin.html | 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 [[http://www.eecs.harvard.edu/~nr/pubs/maniaws-abstract.html | 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. Changed lines 14-16 from:
* [[#l8 | lista 8]] moduły i funktory ([[#z81 | zad.1]], [[#z82 | zad.2]], [[#z83 | zad.3]], [[#z84 | zad.4]], [[#z85 | zad.5]], [[#z86 | zad.6]] * lista 9 argumenty etykietowane, to:
* [[#l8 | lista 8]] moduły i funktory ([[#z81 | zad.1]], [[#z82 | zad.2]], [[#z83 | zad.3]], [[#z84 | zad.4]], [[#z85 | zad.5]], [[#z86 | zad.6]], [[#z87 | zad.7]]) * lista 9 argumenty etykietowane, domyślne wartości argumentów, tzw. warianty polimorficzne, obiekty Changed line 14 from:
* [[# to:
* [[#l8 | lista 8]] moduły i funktory ([[#z81 | zad.1]], [[#z82 | zad.2]], [[#z83 | zad.3]], [[#z84 | zad.4]], [[#z85 | zad.5]], [[#z86 | zad.6]]) Changed lines 676-677 from:
b to:
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". Changed lines 713-714 from:
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]]) to:
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/]].) November 27, 2006, at 07:24 PM
by - Powazny blad w przykladzie do zadania 2 lista 8
Changed line 706 from:
# to:
# Table2.compare s4 s3;; Changed lines 15-16 from:
to:
* lista 9 argumenty etykietowane, argumenty domyślne, tzw. warianty polimorficzne, obiekty Changed lines 14-15 from:
to:
* [[#l7 | lista 8]] moduły i funktory ([[#z81 | zad.1]], [[#z82 | zad.2]], [[#z83 | zad.3]], [[#z84 | zad.4]], [[#z85 | zad.5]], [[#z86 | zad.6]]) Changed lines 673-674 from:
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 to:
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". Changed lines 666-862 from:
to:
[[Attach:pa_lettry.cmo.zip | skompilowany i zzipowany plik z rozszerzeniem składniowym]] !! [[#l8]] Lista 8. !!! [[#z81]] 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]] !!! [[#z82]] 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@@. !!! [[#z83]] 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. !!! [[#z84]] 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. !!! [[#z85]] 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. !!! [[#z86]] 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. Changed lines 659-660 from:
* imperatywnie przez iterację, przy pomocy tablicy haszującej (moduł Hashtbl) klucz:słowo - wartość:liczba wystąpień to:
* imperatywnie przez iterację, przy pomocy tablicy haszującej (moduł Hashtbl) klucz:słowo - wartość:liczba wystąpień Changed lines 661-665 from:
* funkcyjnie iteracyjnie (symulując przypadki, gdy wyniki pośrednie też są potrzebne): podobnie jak w stylu imperatywnym ale z modułem Map wyznaczającej histogram) to:
* 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) Changed line 670 from:
[[Attach:pa_lettry.cmo | skompilowany plik z rozszerzeniem składniowym]] to:
[[Attach:pa_lettry.cmo.zip | skompilowany i zzipowany plik z rozszerzeniem składniowym]] Changed lines 13-14 from:
* [[#l7 | lista 7]] programowanie imperatywne ([[#z71 | zad.1]], [[#z72 | zad.2]], [[#z73 | zad.3]], [[#z74 | zad.4]]) to:
* [[#l7 | lista 7]] programowanie imperatywne ([[#z71 | zad.1]], [[#z72 | zad.2]], [[#z73 | zad.3]], [[#z74 | zad.4]], [[#z75 | zad.5]]) Added lines 657-667:
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) !!! [[#z75]] Zadanie 5. Added lines 669-670:
[[Attach:pa_lettry.cmo | skompilowany plik z rozszerzeniem składniowym]] Changed lines 13-14 from:
* [[#l7 | lista 7]] programowanie imperatywne ([[#z71 | zad.1]], [[#z72 | zad.2]], [[#z73 | zad.3]]) to:
* [[#l7 | lista 7]] programowanie imperatywne ([[#z71 | zad.1]], [[#z72 | zad.2]], [[#z73 | zad.3]], [[#z74 | zad.4]]) Added lines 655-657:
!!! [[#z74]] 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.) Changed lines 7-14 from:
* [[#l1 | lista 1]] funkcje wyższego rzędu i manipulowanie listami * * * [[# * [[#l6 | lista 6]] leniwe * to:
* [[#l1 | lista 1]] funkcje wyższego rzędu i manipulowanie listami ([[#z11 | zad.1]], [[#z12 | zad.2]]) * [[#l2 | lista 2]] jak wyżej ([[#z21 | zad.1]], [[#z22 | zad.2]], [[#z23 | zad.3]]) * [[#l3 | lista 3]] funkcje jako wartości, budowanie funkcji z funkcji ([[#z31 | zad.1]], [[#z32 | zad.2]]) * [[#l4 | lista 4]] typy algebraiczne (warianty) ([[#z41 | zad.1]], [[#z42 | zad.2]]) * [[#l5 | lista 5]] przerywnikowa ([[#z51 | zad.1]], [[#z52 | zad.2]], [[#z53 | zad.3]], [[#z54 | zad.4]]) * [[#l6 | lista 6]] leniwe (korekurencyjne) struktury danych ([[#z61 | zad.1]], [[#z62 | zad.2]], [[#z63 | zad.3]], [[#z64 | zad.4]]) * [[#l7 | lista 7]] programowanie imperatywne ([[#z71 | zad.1]], [[#z72 | zad.2]], [[#z73 | zad.3]]) Changed lines 17-18 from:
!!! Zadanie 1. to:
!!! [[#z11]] Zadanie 1. Changed lines 21-22 from:
!!! Zadanie 2. to:
!!! [[#z12]] Zadanie 2. Changed lines 45-46 from:
!!! Zadanie 1. to:
!!! [[#z21]] Zadanie 1. Changed lines 61-62 from:
!!! Zadanie 2. to:
!!! [[#z22]] Zadanie 2. Changed line 83 from:
!!! Zadanie 3. Napisz funkcję liczącą domknięcie zwrotne i przechodnie grafu. Graf to:
!!! [[#z23]] Zadanie 3. Napisz funkcję liczącą domknięcie zwrotne i przechodnie grafu. Graf Changed lines 111-112 from:
!!! Zadanie 1. to:
!!! [[#z31]] Zadanie 1. Changed lines 151-152 from:
!!! Zadanie 2. to:
!!! [[#z32]] Zadanie 2. Changed lines 252-253 from:
!!! Zadanie 1. to:
!!! [[#z41]] Zadanie 1. Changed lines 275-276 from:
!!! Zadanie 2. (Propozycja projektu.) to:
!!! [[#z42]] Zadanie 2. (Propozycja projektu.) Changed line 331 from:
!!! Zadanie 1. to:
!!! [[#z51]] Zadanie 1. Changed line 334 from:
!!! Zadanie 2. to:
!!! [[#z52]] Zadanie 2. Changed line 342 from:
!!! Zadanie 3. to:
!!! [[#z53]] Zadanie 3. Changed line 345 from:
!!! Zadanie 4. to:
!!! [[#z54]] Zadanie 4. Changed lines 376-377 from:
!!! Zadanie 1. to:
!!! [[#z61]] Zadanie 1. Changed lines 438-439 from:
!!! Zadanie 2. to:
!!! [[#z62]] Zadanie 2. Changed line 491 from:
!!! Zadanie 3. (Problem Hamminga) to:
!!! [[#z63]] Zadanie 3. (Problem Hamminga) Changed line 545 from:
!!! Zadanie 4. Ciągi liczbowe. to:
!!! [[#z64]] Zadanie 4. Ciągi liczbowe. Changed line 601 from:
!!! Zadanie 1. to:
!!! [[#z71]] Zadanie 1. Changed line 610 from:
!!! Zadanie 2. to:
!!! [[#z72]] Zadanie 2. Changed line 624 from:
!!! Zadanie 3. to:
!!! [[#z73]] Zadanie 3. Changed lines 7-14 from:
* [[#l1 | lista 1]] * [[#l3 | lista 3 * [[#l6 | lista 6]] * to:
* [[#l1 | lista 1]] funkcje wyższego rzędu i manipulowanie listami * [[#l2 | lista 2]] jak wyżej * [[#l3 | lista 3]] funkcje jako wartości, budowanie funkcji z funkcji * [[#l4 | lista 4]] typy algebraiczne (warianty) * [[#l5 | lista 5]] przerywnikowa * [[#l6 | lista 6]] leniwe (korekurencyjne) struktury danych * [[#l7 | lista 7]] programowanie imperatywne Added lines 623-654:
!!! 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). Added lines 545-598:
!!! 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: k'_1_' = h * f(y'_n_'; t'_n_') k'_2_' = h * f(y'_n_' + k'_1_'/2; t'_n_' + h/2) y'_n+1_' = y'_n_' + k'_2_' zastosuj "podniesienie" funkcji @@f@@ z liczb na ciągi, [@(map2 f s1 s2)@]. Zakoduj algorytm Lentza obliczania ułamków łańcuchowych: f = b'_0_' + a'_1_' / (b'_1_' + a'_2_' / (b'_2_' + a'_3_' / (b'_3_' + ...))) o następującej specyfikacji imperatywnej: Set f'_0_' = b'_0_'; C'_0_' = f'_0_'; D'_0_' = 0; for j = 1; 2; ... Set D'_j_' = 1/(b'_j_' + a'_j_'*D'_j-1_') Set C'_j_' = b'_j_' + a'_j_'/C'_j-1_' Set f'_j_' = f'_j-1_'(C'_j_'*D'_j_') Stop gdy C'_j_'*D'_j_' prawie równe 1. Oblicz przy jego pomocy e'^z^' = 1 + (z / (1 - z / (2 + z / (3 - ...)))) dla z=1 (i [@ 'a = float @]). Changed lines 13-14 from:
to:
* [[#l7 | lista 7]] Changed lines 543-568 from:
to:
@] !! [[#l7]] 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). Added lines 489-542:
!!! Zadanie 3. (Problem Hamminga) Wygeneruj n pierwszych liczb w postaci 2'^a'_1_'^'3'^a'_2_'^'5'^a'_3_'^'...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'_1_' taką, że 2x'_1_' jest większa od ostatniego elementu już wygenerowanej listy, tak samo dla x'_2_' i 3x'_2_', etc. Do listy dodajemy minimum z 2x'_1_', 3x'_2_', ..., p'_k_'x'_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 ;; @] Changed lines 5-8 from:
! !! to:
!! [[#contents]] Listy: * [[#l1 | lista 1]] * [[#l2 | lista 2]] * [[#l3 | lista 3]] * [[#l4 | lista 4]] * [[#l5 | lista 5]] * [[#l6 | lista 6]] !! [[#l1]] Lista 1 !!! Zadanie 1. Changed lines 20-21 from:
!! Zadanie 2. to:
!!! Zadanie 2. Changed lines 28-29 from:
!!! Dodatkowe wskazówki do zadania [@map_reduce@] z "listy 1": to:
!!!! Dodatkowe wskazówki do zadania [@map_reduce@] z "listy 1": Changed lines 42-45 from:
! !! Zadanie 1. to:
!! [[#l2]] Lista 2 !!! Zadanie 1. Changed lines 60-61 from:
!! Zadanie 2. to:
!!! Zadanie 2. Changed line 82 from:
!! Zadanie 3. Napisz funkcję liczącą domknięcie zwrotne i przechodnie grafu. Graf to:
!!! Zadanie 3. Napisz funkcję liczącą domknięcie zwrotne i przechodnie grafu. Graf Changed lines 87-88 from:
!!! Instalacja rozszerzenia składniowego: to:
!!!! Instalacja rozszerzenia składniowego: Changed lines 108-111 from:
! Lista 3. !! Zadanie 1. to:
!! [[#l3]] Lista 3. !!! Zadanie 1. Changed lines 150-151 from:
!! Zadanie 2. to:
!!! Zadanie 2. Changed lines 225-226 from:
!!! Dalsze uwagi. to:
!!!! Dalsze uwagi. Changed lines 249-252 from:
! Lista 4 !!Zadanie 1. to:
!! [[#l4]] Lista 4 !!! Zadanie 1. Changed lines 274-275 from:
!! Zadanie 2. (Propozycja projektu.) to:
!!! Zadanie 2. (Propozycja projektu.) Changed lines 328-330 from:
! Lista 5 !! Zadanie 1. to:
!! [[#l5]] Lista 5 !!! Zadanie 1. Changed line 333 from:
!! Zadanie 2. to:
!!! Zadanie 2. Changed line 341 from:
!! Zadanie 3. to:
!!! Zadanie 3. Changed line 344 from:
!! Zadanie 4. to:
!!! Zadanie 4. Changed lines 373-376 from:
! Lista 6. !! Zadanie 1. to:
!! [[#l6]] Lista 6. !!! Zadanie 1. Changed lines 437-438 from:
!! Zadanie 2. to:
!!! Zadanie 2. Added lines 363-478:
! 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"? Added lines 319-362:
! 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. Changed lines 106-110 from:
to:
* @@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. Changed lines 1-318 from:
to:
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": [[Attach:zipper.pdf]] Dokończ artykuł Gerarda Hueta: napisz brakujące funkcje manipulacji "zipperami" z memoizacją (punkt 3.1). [[Attach: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ę [[(Attach:)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. [[Attach:funind.ml]] |