Рекурсивный тип данных

В компьютерных языках программирования , A тип рекурсивного данных (также известный как рекурсивно определенный , индуктивно определяются или индуктивным тип данных ) представляет собой тип данных для значений , которые могут содержать другие значения одного и тот же типа. Данные рекурсивных типов обычно рассматриваются как ориентированные графы .

Важное применение рекурсии в информатике - определение динамических структур данных, таких как списки и деревья. Рекурсивные структуры данных могут динамически увеличиваться до произвольно большого размера в соответствии с требованиями времени выполнения; напротив, требования к размеру статического массива должны быть установлены во время компиляции.

Иногда термин «индуктивный тип данных» используется для алгебраических типов данных, которые не обязательно рекурсивны.

Пример [ править ]

Примером является тип списка в Haskell :

 список  данных a  =  Nil  |  Минусы  a  ( список  a )

Это указывает на то, что список a является либо пустым списком, либо cons-ячейкой, содержащей «a» («начало» списка) и другой список («хвост»).

Другой пример - аналогичный односвязный тип в Java:

class  List < E >  {  значение E  ; Список < E > следующий ; }  

Это указывает на то, что непустой список типа E содержит элемент данных типа E и ссылку на другой объект List для остальной части списка (или пустую ссылку, чтобы указать, что это конец списка).

Взаимно рекурсивные типы данных [ править ]

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

f: [t [1], ..., t [k]]т: vf

Лес f состоит из списка деревьев, а дерево t состоит из пары значения v и леса f (его потомков). Это определение элегантно, и с ним легко работать абстрактно (например, при доказательстве теорем о свойствах деревьев), поскольку оно выражает дерево в простых терминах: список одного типа и пара двух типов.

Это взаимно рекурсивное определение можно преобразовать в однократно рекурсивное определение, вставив определение леса:

t: v [t [1], ..., t [k]]

Дерево t состоит из пары значения v и списка деревьев (его дочерних элементов). Это определение более компактно, но несколько запутано: дерево состоит из пары одного типа и списка другого, которые требуют распутывания для подтверждения результатов.

В стандартном ML типы данных дерева и леса могут быть взаимно рекурсивно определены следующим образом, что позволяет использовать пустые деревья: ^[1]

тип данных  '  дерево  =  Пусто  |  Узел  из  «в  *  » в  лесу и  «а  леса  =  Nil  |  Cons  из  «в  дерево  *  » а  лес

В Haskell типы данных tree и forest можно определить аналогично:

 дерево  данных a  =  Пусто  |  Узел  ( а ,  лес  а )data  Forest  a  =  Nil  |  Минусы  ( Дерево  а )  ( Лес  а )

Теория [ править ]

В теории типов рекурсивный тип имеет общий вид μα.T, где переменная типа α может появляться в типе T и обозначает сам тип в целом.

Например, натуральные числа (см. Арифметику Пеано ) могут быть определены типом данных Haskell:

данные  Nat  =  Zero  |  Succ  Nat

В теории типов мы бы сказали: где две ветви типа суммы представляют конструкторы данных Zero и Succ. Zero не принимает аргументов (таким образом, представленных типом единицы ), а Succ принимает другой Nat (таким образом, другой элемент ).${\ displaystyle nat = \ mu \ alpha .1+ \ alpha}$${\ displaystyle \ mu \ alpha .1+ \ alpha}$

Есть две формы рекурсивных типов: так называемые изорекурсивные типы и эквирекурсивные типы. Эти две формы различаются тем, как вводятся и удаляются термины рекурсивного типа.

Изорекурсивные типы [ править ]

С изорекурсивными типами рекурсивный тип и его раскрытие (или разворачивание ) (где обозначение указывает, что все экземпляры Z заменены на Y в X) являются отдельными (и непересекающимися) типами со специальными конструкциями терминов, обычно называемыми roll и unroll , которые образуют между ними изоморфизм . Чтобы быть точным: и , и эти два являются обратными функциями .${\ displaystyle \ mu \ alpha .T}$${\ Displaystyle Т [\ му \ альфа .T / \ альфа]}$${\ Displaystyle X [Y / Z]}$${\ displaystyle roll: T [\ mu \ alpha .T / \ alpha] \ to \ mu \ alpha .T}$${\displaystyle unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]}$

Эквирекурсивные типы [ править ]

В соответствии с правилами equirecursive, рекурсивный тип и его разворачивания являются равными - то есть, эти два выражения типа понимается для обозначения того же типа. Фактически, большинство теорий эквирекурсивных типов идут дальше и по существу указывают, что любые два выражения типа с одним и тем же «бесконечным расширением» эквивалентны. В результате применения этих правил эквирекурсивные типы значительно усложняют систему типов, чем изорекурсивные типы. Алгоритмические проблемы, такие как проверка типов и вывод типов, также более сложны для эквирекурсивных типов. Поскольку прямое сравнение не имеет смысла для эквирекурсивного типа, они могут быть преобразованы в каноническую форму за время O (n log n), что легко сопоставить. ^[2]${\displaystyle \mu \alpha .T}$${\displaystyle T[\mu \alpha .T/\alpha ]}$

Эквирекурсивные типы охватывают форму определений типов, ссылающихся на себя (или взаимно ссылочных), которые можно увидеть в процедурных и объектно-ориентированных языках программирования, а также возникают в теоретико-типовой семантике объектов и классов . В языках функционального программирования изорекурсивные типы (в виде типов данных) встречаются гораздо чаще.

В синонимах типа [ править ]

Рекурсия не разрешена в синонимах типов в Miranda , OCaml (если -rectypesне используется флаг, запись или вариант) и Haskell; так, например, недопустимы следующие типы Haskell:

type  Bad  =  ( Int ,  Bad ) тип  Evil  =  Bool  ->  Evil

Вместо этого он должен быть заключен в алгебраический тип данных (даже если у него только один конструктор):

data  Good  =  Pair  Int  Good data  Fine  =  Fun  ( Bool  ->  Fine )

Это связано с тем, что синонимы типов, такие как typedef в C, заменяются их определением во время компиляции. (Синонимы типов не являются «настоящими» типами; они являются просто «псевдонимами» для удобства программиста.) Но если это делается с рекурсивным типом, цикл будет бесконечным, потому что независимо от того, сколько раз псевдоним был заменен, он все равно относится к самому себе, например, «Плохо» будет расти бесконечно: Bad→ (Int, Bad)→ (Int, (Int, Bad))→ ....

Другой способ увидеть это состоит в том, что необходим уровень косвенности (алгебраический тип данных), чтобы позволить системе изорекурсивных типов определить, когда свернуть и развернуть .

См. Также [ править ]

• Рекурсивное определение
• Алгебраический тип данных
• Индуктивный тип
• Узел (информатика)

Заметки [ править ]

Эта статья основана на материалах, взятых из Free On-line Dictionary of Computing до 1 ноября 2008 г. и включенных в соответствии с условиями «перелицензирования» GFDL версии 1.3 или новее.