Programowanie funkcyjne/Funktory/Ćwiczenia

Praca domowa

• Napisz funktor implementujący liczby całkowite "podwójnej precyzji". Jego parametrem powinien być pakiet liczb całkowitych z ograniczonego zakresu, a wynikiem pakiet liczb całkowitych zwiększonego zakresu. Sygnatury parametru i wyniku powinny być takie same, tak aby funktor można było składać z samym sobą otrzymując liczby całkowite "poczwórnej precyzji".
• Napisz funktor implementujący ogólny mechanizm przeszukiwania z nawrotami (ang. back-tracking). Sprecyzuj najpierw rodzaj przeszukiwania (np. czy znajdowane jest jedno rozwiązanie, wszystkie rozwiązania czy też najlepsze rozwiązanie).

Ćwiczenia

• Podaj sygnaturę implementacji struktury danych liczb zespolonych (wyłącznie konstruktory i selektory, biegunowe i prostokątne). Sygnatura powinna pasować do dowolnej implementacji: biegunowej, prostokątnej lub mieszanej. Naszkicuj implementację reszty pakietu liczb zespolonych jako funktor, którego parametrem jest implementacja struktury danych, a wynikiem w pełni funkcjonalny pakiet.
• Przypomnijmy sobie pakiet liczb wymiernych z poprzedniego wykładu. Można go zapisać w postaci funktora, sparametryzowanego (wybranym typem) liczb całkowitych. Podaj sygnaturę liczb całkowitych zawierającą wszystkie operacje potrzebne do zaimplementowania pakietu liczb wymiernych ze skracaniem ułamków. Napisz funktor implementujący taki pakiet liczb wymiernych.
• Wyobraźmy sobie pakiet implementujący wielomiany, wraz z rozmaitymi operacjami na wielomianach: suma, różnica, iloczyn, iloraz, reszta z dzielenia, porównanie, pochodna, itp. Pakiet taki może być sparametryzowany typem liczb (ciałem) współczynników wielomianu. Podaj odpowiednie sygnatury i naszkicuj sposób implementacji pakietu wielomianów jako funktora. Czy implementacja jest na tyle ogólna, aby pakiet działał nie tylko dla liczb zmiennopozycyjnych, ale również dla zespolonych i wymiernych?
• Porównaj sygnatury wielomianów i liczb zastosowanych do budowy liczb wymiernych. Czy można ich użyć do stworzenia pakietu liczb wymiernych, jako ułamków, których współczynnikami są wielomiany? Jeżeli nie, to co trzeba zmienić? Zwróć uwagę na skracanie ułamków.
• Korzystając z wyników poprzednich zadań podaj, jak można skonstruować pakiet wielomianów dwóch zmiennych? Czy współczynnikami wielomianów jednej zmiennej mogą być wielomiany drugiej zmiennej?
• Podaj sygnaturę struktury implementującej przestrzeń metryczną oraz zaimplementuj przestrzeń liczb rzeczywistych z metryką |...|. Napisz funktory implementujące metrykę euklidesową i typu Manhattan na produkcie kartezjańskim dwóch przestrzeni metrycznych. Jak za ich pomocą można zapisać przestrzeń $R^3$ z metryką euklidesową i Manhattan?
• Napisz funktor implementujący wybraną strategię grania w dowolną grę dwuosobową, z pełną informacją, bez losowości i z binarnym wynikiem (takiej jak szachy, Go, warcaby, Nim, czy kółko i krzyżyk), np. mini-max, alfa-beta obcięcie, drzewa and-or.
• Rozważamy funktor służący do generowania losowych drzew binarnych. Typ takich drzew jest postaci: type tree = Leaf | Node of tree * t * tree. Losowe drzewo z prawdopodobieństwem $p$ jest puste (\texttt{Leaf}), a z prawdopodobieństwem $1-p$ składa się z dwóch losowych poddrzew i losowej wartości w korzeniu. Parametr funktora definiuje:
  • typ t,
  • procedurę random_leaf : unit -> bool, która z prawdopodobieństwem p zwraca true,
  • procedurę random_t : unit -> t, która zwraca losową wartość typu t.

Zdefiniuj opisany funktor.