Создание полиморфных рекурсивных типов в Haskell
Я пытаюсь создать Древовидный тип в Haskell. Я использовал этого простого конструктора данных для хранения дерева, в котором каждый узел может или быть пустым, быть листом, содержащим целое число, или быть узлом, содержащим целое число с ответвлениями к двум другим листам/узлам. Вот то, что я имею:
module Tree ( Tree(Empty, Leaf, Node) ) where
data Tree = Empty
| Leaf Int
| Node Tree Int Tree
deriving(Eq, Ord, Show, Read)
Это хорошо работает, но я должен сделать Древовидный тип полиморфным. Я попытался просто заменить 'Интервал', но это, кажется, не работает. Есть ли другая система для того, чтобы сделать эти типы полиморфными?
4 ответа
В самом деле, вы можете указать дереву параметр типа, как в примере Александра Полуэктова . Достаточно просто! Но зачем останавливаться на достигнутом? Мы можем получить немного больше удовольствия, чем просто это. Вместо простой рекурсивной структуры с полиморфными данными вы можете сделать структуру полиморфной в самой рекурсии !
Во-первых, абстрагируйте ссылки дерева на себя, таким же образом, как абстрагирование ссылок на 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 из рекурсивного tree, мы можем использовать это в любой такой структуре:
treeToList = toList (\(Tree t) -> t)
nameTreeToList = toList (\(NameTree (_, t)) -> t)
Конечно, это, вероятно, выходит далеко за рамки того, что вы хотите сделать, но это хороший вкус того, насколько полиморфизм и общий код позволяет Haskell (нет, поощряет) программист для создания.
data Tree a = Empty
| Leaf a
| Node (Tree a) a (Tree a)
Замена Int на a является правильным началом, но также необходимо заменить каждое вхождение Tree на Tree a (при необходимости заключив его в скобки). В части Дерево данных необходимо указать, что дерево имеет один аргумент типа. Int-дерево дерева узлов должно означать, что сами поддеревы имеют тип Дерево , а не какой-либо другой тип дерева.
Попробуйте прочитать немного о конструкторе типов 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 и т. д.
Сообщение о выходе выглядит примерно так: поскольку конструкторы значений имеют сигнатуры типа, конструкторы типов имеют сигнатуры типа, и это необходимо учитывать при планировании нового типа данных.
data Tree a = Empty
| Leaf a
| Node (Tree a) a (Tree a)