Создание полиморфных рекурсивных типов в Haskell

Question

Я пытаюсь создать тип дерева в Haskell. Я использовал этот простой конструктор данных для хранения дерева, в котором каждый узел может быть пустым, быть листом, содержащим целое число, или узлом, содержащим целое число с ветвями для двух других листьев / узлов. Вот что у меня есть:

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

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

Это прекрасно работает, но мне нужно сделать тип дерева полиморфным. Я пытался просто заменить «Int» на «a», но это не сработало. Есть ли другая система для того, чтобы сделать эти типы полиморфными?

Answer 1

В самом деле, вы можете задать для Tree параметр типа, как в Александр Полуэктов .Достаточно просто!Но зачем останавливаться на достигнутом?Мы можем получить немного больше удовольствия, чем просто это.Вместо просто рекурсивной структуры с полиморфными данными , вы можете сделать структуру полиморфной в самой рекурсии !

Во-первых, абстрагируйте ссылки дерева на себя, втак же, как абстрагирование ссылок на Int, замена рекурсивных ссылок новым параметром t.Это оставляет нам довольно расплывчатую структуру данных:

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

Это было переименовано здесь как TNode, потому что это больше не дерево;просто простой тип данных.Теперь, чтобы восстановить исходную рекурсию и создать дерево, мы вращаем TNode и подаем его себе:

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

Теперь мы можем использовать это Tree рекурсивно, хотя, к сожалению, за счет некоторыхлишнее словоблудие, вот так:

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

Так что же это дает нам, кроме дополнительного набора текста, спросите вы?Просто то, что мы отделили структуру фундаментального дерева как от содержащихся в ней данных, так и от метода, с помощью которого эти данные конструируются и обрабатываются, что позволяет нам писать более общие функции для работы с тем или иным аспектом.

Например, мы можем украсить деревья дополнительными данными или скомбинировать дополнительные элементы в дерево, не влияя на какие-либо общие функции дерева.Скажем, мы хотели дать имя каждому фрагменту дерева:

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

С другой стороны, мы можем написать общую логику обхода дерева:

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

Учитывая функцию для извлечениятекущий TNode из рекурсивного дерева, мы можем использовать его для любой такой структуры:

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

Конечно, это, вероятно, выходит далеко за рамки того, что вы хотите сделать, но это хороший вкуснасколько полиморфизм и универсальный код Haskell позволяет (нет, поощряет) программист создавать.

Answer 2

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

Answer 3

Замена Int на a является правильным началом, но вам также необходимо заменить каждое вхождение Tree на Tree a (заключив его в скобки, если это необходимо).Часть data Tree нуждается в a, чтобы объявить, что у Дерева есть один аргумент типа, названный a.Node Tree Int Tree должен означать, что поддеревья сами по себе имеют тип Tree a, а не какой-либо другой тип Treetype.

Answer 4

Попробуйте немного прочитать о конструкторе типов kind .

Если у вас полиморфный тип, зависящий от некоторых переменных типа, тогда ваш конструктор типов должен иметь тип, который отражает это.

Например, конструктор типа MyBool, определенный в:

data MyBool = False | True

, имеет вид *.То есть мой конструктор типов MyBool не принимает параметров для определения типа.Если я напишу что-то вроде:

data MyMaybe a = Just a | Nothing

, тогда конструктор типа MyMaybe будет иметь вид *->*, то есть ему нужен «аргумент типа» для определения типа.

Вы можете сравнить, как работает конструктор типов, с тем, как работает тип конструктора данных.

Конструктор данных True может быть значением данных типа MyBool самостоятельно, без каких-либо параметров.Но конструктор данных Just является значением типа a -> MyMaybe a, он будет оперировать над значением типа a, чтобы создать другое значение типа MyMaybe a - как, например, в этом сеансе ghci:

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

Это более или менее сопоставимо с разницей между конструкторами типов MyMaybe и MyBool.Учитывая, что MyBool имеет вид *, вы можете иметь значения с типом MyBool без каких-либо дополнительных параметров типа.Но MyMaybe не является типом сам по себе - это конструктор типов, который «оперирует» с типом для создания другого типа, то есть его тип - * -> *.И так, вы не можете иметь вещи типа MyMaybe, но вещи типа MyMaybe Int, MyMaybe Bool, MyMaybe [Int] и т. Д. *

Если тип полиморфный, он долженбыть хотя бы вида * -> *, но это может быть *->*->*, как в:

 data MyPair a b = Pair a b

MyPair требуется два параметра типа для определения типа, как в MyPair Int Bool, MyPair Int Intи т. д.

Сообщение возврата домой выглядит примерно так: поскольку конструкторы значений имеют сигнатуры типов, конструкторы типов имеют сигнатуры типов, и это необходимо учитывать при планировании нового типа данных.

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