5109637321

data Tree a = Node (Tree (a,a)) | Leaf a

(zauważ, że zmiana polega na zamianie miejscami typów Tree i (,) w argumencie konstruktora Node). Zaprogramuj funkcje

height :: Tree a -> Int

size :: Tree a -> Int

peek :: Int -> Int -> Tree a -> a

poke :: Int -> Int -> a -> Tree a -> Tree a

link :: (Tree (a,a)) -> (Tree (a,a)) -> Tree a

Funkcja peek hit ujawnia ż-ty element drzewa wysokości h (elementy numerujemy od lewej do prawej poczynając od zera), funkcja poke zmienia odpowiedni element, zaś link łączy dwa drzewa w większe. Wyjaśnij w których miejscach pojawia się rekursja polimorficzna.

Komentarz: możemy w Haskellu zaprogramować typ BinomialRAL tak, że każda dana tego typu jest nie tylko ciągiem pełnych drzew, ale także wysokości tych drzew są ciągiem ściśle rosnącym. Zamiast standardowego typu [] należy zdefiniować wersję list sprawdzających rozmiar drzew.

Zadanie 11. Tzw. zagnieżdżone lub nieregularne typy danych są atrakcyjne o tyle, że nie wymagają rozszerzania systemu typów. Są jednak mało intuicyjne. Lepiej byłoby majstrować przy wyniku, a nie argumencie konstruktora. To prowadzi nas do tzw. uogólnionych algebraicznych typów danych. Niestety zawierają one w sobie typy egzystencjalne, więc — jak widzieliśmy w zadaniu 9 — musimy uważać, żeby nie załamać systemu typów. Pozwalamy, by typ wyniku konstruktora nie był dokładnie równy definiowanemu typowi, lecz mógł być jego instancją. Ten pomysł w połączeniu z typami fantomowymi (typami, które nie posiadają wartości) prowadzi do znacznie czytelniejszej implementacji pełnych drzew binarnych:

data Zero

data Suce n

data Tree h a where

Node :: Tree h a -> Tree h a -> Tree (Suce h) a Leaf :: a -> Tree Zero a

Dodatkowy parametr typowy „zlicza” wysokość drzewa i zapewnia, że łączymy tylko drzewa tej samej wysokości. Zaprogramuj funkcje z poprzedniego zadania dla tej reprezentacji (zauważ, że np. link jest nie tylko prostsza, ale ma znacznie lepszą złożoność). Zauważ, że rekursja polimorficzna tu również jest niezbędna do rozwiązania zadania.

5