Haskell — алгебраические типы данных, использующие рекурсию?

Я следовал руководству по созданию двоичного дерева поиска, которое использует следующий тип данных:

data BinarySearchTree a = EmptyTree | TreeNode a (BinarySearchTree a) (BinarySearchTree a) deriving (Show, Read, Eq)

Правильно ли я говорю, что «TreeNode» использует рекурсию, т.е. создает 2 элемента своего собственного типа данных «(BinarySearchTree a) (BinarySearchTree a)»?

Я никогда не видел такого типа данных, любое краткое объяснение было бы здорово!


person Babra Cunningham    schedule 22.09.2016    source источник
comment
Он очень похож на тип списка (который также является рекурсивным), за исключением того, что он рекурсирует дважды (две ветви узла в дереве), а не один раз (в списке ячейка имеет только один конец).   -  person chi    schedule 22.09.2016
comment
Технически TreeNode принимает два значения BinarySearchTree (и одно значение a) и возвращает новое значение BinarySearchTree. Тип определяется рекурсивно.   -  person chepner    schedule 22.09.2016
comment
TreeNode ничего не создает.   -  person user253751    schedule 26.09.2016


Ответы (1)


Да, это рекурсивный тип данных.

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

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

person ljedrz    schedule 22.09.2016