Tworzenie polimorficznych typów rekursywnych w Haskell

Question

Próbuję utworzyć typ drzewa w Haskell. Użyłem tego prostego konstruktora danych do przechowywania drzewa, w którym każdy węzeł może być pusty, być liściem zawierającym liczbę całkowitą lub być węzłem zawierającym liczbę całkowitą z gałęziami do dwóch innych liści/węzłów. Oto, co mam:

module Tree (Tree(Empty, Leaf, Node)) where 

data Tree = Empty 
| Leaf Int 
| Node Tree Int Tree 
deriving(Eq, Ord, Show, Read) 

To działa dobrze, ale muszę sprawić, aby drzewo było polimorficzne. Próbowałem po prostu zastąpić "Int" z "a", ale nie wydaje się działać. Czy istnieje inny system, który umożliwi polimorfizm tego typu?

Answer 1

Rzeczywiście, można nadać drzewu parametr typu, jak w przykładzie Alexander Poluektov. Wystarczająco proste! Ale dlaczego tam się zatrzymać? Możemy mieć nieco więcej zabawy niż tylko to. Zamiast struktury rekursywnej z polimorficznymi danymi można uzyskać polimorficzną strukturę w samej rekursji!

Po pierwsze, odinstaluj odniesienia do drzewa w taki sam sposób, jak usunięcie odniesień do Int, zastępując odniesienia rekurencyjne nowym parametrem t. To pozostawia nas z tej dość niejasnej struktury danych:

data TNode t a = Empty 
       | Leaf a 
       | Node (t a) a (t a) 
       deriving (Eq, Ord, Show, Read) 

ta została przemianowana na TNode tutaj, bo to naprawdę nie jest już drzewo; tylko prosty typ danych. Teraz, aby odzyskać oryginalny rekurencji i utworzyć drzewo, możemy skręcać TNode się i karmić go do siebie:

newtype Tree a = Tree (TNode Tree a) deriving (Eq, Ord, Show, Read) 

teraz możemy korzystać z tej Tree rekurencyjnie, ale niestety kosztem jakiegoś dodatkowego słownictwa, tak jak poniżej:

Tree (Node (Tree Empty) 5 (Tree (Leaf 2))) 

Co nam to daje, oprócz dodatkowego pisania, pytasz? Po prostu rozdzieliliśmy podstawowe drzewo o strukturze i sposobie, w jaki dane są konstruowane i przetwarzane, co pozwala nam pisać bardziej ogólne funkcje, aby poradzić sobie z jednym aspektem.

Na przykład możemy ozdobić drzewa dodatkowymi danymi lub ułożyć dodatkowe elementy w drzewie, bez wpływu na ogólne funkcje drzewa.Powiedzieć, chcieliśmy nadać nazwę każdego kawałka drzewa:

newtype NameTree a = NameTree (String, TNode NameTree a) deriving (Eq, Ord, Show, Read) 

Z drugiej strony, możemy napisać rodzajowe logikę przechodzenie drzewa:

toList f t = toList' f (f t) [] 
    where toList' f (Node t1 x t2) xs = toList' f (f t1) (x : toList' f (f t2) xs) 
      toList' f (Leaf x) xs = x:xs 
      toList' _ Empty xs = xs 

Biorąc funkcja wyodrębnić bieżący TNode z rekurencyjny drzewo, możemy to wykorzystać na każdej takiej strukturze:

treeToList = toList (\(Tree t) -> t) 
nameTreeToList = toList (\(NameTree (_, t)) -> t) 

oczywiście, to prawdopodobnie wykracza daleko poza to, czego szukasz do zrobienia, ale jest to miły smak, jak wiele polimorfizm i kod generyczny Haskell pozwala (nie zachęca,) programistom do tworzenia.

Answer 2

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

Answer 3

Wymiana Int z prawej jest początek, ale trzeba także wymienić każde wystąpienie Drzewo z Tree a (parenthesizing ją tam, gdzie jest to konieczne). Część data Tree wymaga, aby zadeklarować, że drzewo ma jeden typ argumentu nazywany a. Node Tree Int Tree musi oznaczać, że poddrzewa są same w sobie typu Tree a, a nie jakimiś innymi rodzajami wierzchołków.

Answer 4

Spróbuj trochę przeczytać o typie konstruktora rodzaj.

Jeśli masz typ polimorficzny w zależności od niektórych zmiennych typu, to twój konstruktor typu musi mieć rodzaj, który to odzwierciedla.

Na przykład, konstruktor typu MyBool określone w:

data MyBool = False | True 

jest rodzaju *. Oznacza to, że mój konstruktor typu MyBool nie przyjmuje parametrów definiujących typ. Jeśli piszę coś takiego:

data MyMaybe a = Just a | Nothing 

następnie konstruktor typu MyMaybe mieć miłą *->*, to znaczy, że potrzebuje „typ argumentu”, aby określić typ.

Można porównać sposób działania typów konstruktorów z typem konstruktora danych.

Konstruktor danych True może być wartością danych typu MyBool na własną rękę, bez żadnego parametru. Ale konstruktor dane Just jest wartością typu a -> MyMaybe a będzie działać na wartości typu A, aby utworzyć kolejną wartość typu MyMaybe a - jak na przykład w tym ghci sesji:

> let x = Just 5 
> :t x 
Maybe Int 
> let y = Just 
> :t y 
a -> Maybe a 

Jest to bardziej lub mniej porównywalne z różnicą między konstruktorami typu MyMaybe i MyBool. Biorąc pod uwagę, że MyBool ma rodzaj *, możesz mieć wartości o typie MyBool, bez żadnego dodatkowego parametru typu. Ale MyMaybe nie jest typem sam w sobie - jest konstruktorem typu, który "działa" na typ, aby utworzyć inny typ, czyli jego rodzaj to * -> *. I tak, że nie można mieć rzeczy typu MyMaybe, ale rzeczy typu MyMaybe Int, MyMaybe Bool, MyMaybe [Int], itp ...

Jeżeli typ jest polimorficzny, musi wynosić co najmniej od rodzaju * -> *, ale może być *->*->*, jak w:

data MyPair a b = Pair a b 

MyPair potrzebuje dwa parametry typu, aby określić typ, podobnie jak w MyPair Int Bool, MyPair Int Int, itp ...

Komunikat take home jest podobny do: konstruktory wartości mają sygnatury typów, konstruktory typów mają własne sygnatury i należy to wziąć pod uwagę przy planowaniu nowego typu danych.

http://en.wikipedia.org/wiki/Kind_%28type_theory%29