[Перевод] Пальчиковые деревья (часть 1. Представление)

Вышла недавно статья на Хабре о том, как можно самому создать на функциональном языке такие структуры как Очередь (первый зашёл, первый вышел) и Последовательность (напоминает двусторонний стек — первый зашёл, первый вышел с обоих концов). Посмотрел я на этот код и понял, что он жутко неэффективен — сложность порядка O(n). Быстро сообразить, как создать структуры с O(1) у меня не вышло, поэтому я открыл код библиотечной реализации. Но там была не лёгкая и понятная реализация, а <много кода>. Это было описание пальчиковых деревьев, необходимость и элегантность которых для этой структуры данных хорошо раскрывается текущей статьёй.

Пальчиковые деревья

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

Статья будет состоять из 3х частей:

Пальчиковые деревья (часть 1. Представление)

Пальчиковые деревья (часть 2. Операции)

Пальчиковые деревья (часть 3. Применение)

Разрабатывая структуру данных

Основа и мотивация пальчиковых деревьев пришла от 2-3 деревьев. 2-3 деревья — это деревья, которые могут иметь две или три ветви в каждой внутренней вершине и которые имеют все свои листья на одном и том же уровне. В то время, как бинарное дерево одинаковой глубины d должны быть 2^d листьев, 2-3 деревья гораздо более гибкие, и могут быть использованы для хранения любого числа элементов (количество не должно быть степенью двойки).

Рассмотрим следующее 2-3 дерево:



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

В нашем случае, мы добавляем два пальца. Палец просто точка, в которой вы можете получить доступ части структуры данных, в императивных языках это было бы просто указателем. В нашем случае, однако, мы будем реструктуризовать всё дерево и сделаем родителей первых и последних детей двумя корнями нашего дерева. Визуально, рассматривая вопрос об изменении дерева выше, захватываем первый и последний узлы на предпоследнем слое, и тянем их вверх, позволяя остальной части дерева свисать:





Этот новый тип данных известен как пальчиковое дерево. Пальчиковое дерево состоит из нескольких слоёв (обведенные синим цветом), которые нанизаны на ось, показанную коричневым цветом



Каждый слой пальчикового дерева имеет префикс (слева) и суффикс (справа), а также и ссылку на дальнейший поход вглубь. Префикс и суффикс содержат значения пальчикового дерева: на первом слое содержат значения 2-3 деревьев глубины 0, на втором слое — 2-3 деревья глубины 1, на третьем слое они содержат 2-3 деревья глубины 2 и так далее. Главным элементом этого 2-3 дерева сейчас является элемент в самом низу.

Что ж, имея описание, давайте опишем структуру данных. Для начала мы должны определить структуру 2-3 дерева, которую необходимо будет использовать для сохранения вещей, нанизанных на ось.

data Node a = Branch3 a a a    -- Ветка (node) может содержать 3х детей.
            | Branch2 a a      -- ... или только 2х детей.
            deriving Show

Заметим, что ветка параметризована по своим детям. Это позволяет иметь вложенные ветки для репрезентации 2-3 деревьев и гарантировать одинаковость глубины. Например, 2-3 дерево глубиной 1 может быть Node Char:

> -- 2-3 деревья со 2го суффиксного слоя экземпляра пальчикового дерева.
> Branch3 'n' 'o' 't'
Branch3 'n' 'o' 't'
> Branch2 'a' 't'
Branch2 'a' 't'

Однако, мы можем также создать более глубокие 2-3 деревья. Например, 2-3 дерево, глубиной 2 может быть Node (Node Char):

> Branch2 (Branch3 'n' 'o' 't') (Branch2 'a' 't')
Branch2 (Branch3 'n' 'o' 't') (Branch2 'a' 't')

Замечаем, что отображение гарантирует, что 2-3 дерево будет одинаковой глубины, потому что глубина присутствует в типе дерева. Это так же имеет свои недостатки, так как сложнее писать функции, которые параметрические по параметру глубины дерева. Но это не так плохо для нашего случая.

Для дальнейшего нашего удобства, добавим немного методов, которые позволят нам преобразовывать значения веток из списков длиной 2 или 3. Для этого будем использовать расширение OverloadedLists для GHC, которое позволит нам написать функции fromList и toList для различных типов данных, и далее использовать их для сравнений с образцом, если мы используем списки:

{- LANGUAGE OverloadedLists, TypeFamilies -}
import GHC.Exts (IsList(..))

instance IsList (Node a) where
  type Item (Node a) = a
  
  toList (Branch2 x y)   = [x, y]
  toList (Branch3 x y z) = [x, y, z]
  
  fromList [x, y]    = Branch2 x y
  fromList [x, y, z] = Branch3 x y z
  fromList _ = error "Node must contain two or three elements"

Теперь, когда мы имеем наш тип 2-3 дерева, необходим также тип для сохранения префикса и суффиксов, которые нанизаны на ось пальчикового дерева. Если наше пальчиковое дерева является полной аналогией 2-3 дерева, тогда каждые самые первые префиксы и суффиксы могут иметь 2 или 3 элемента, а средние могут иметь только 1 или 2 (потому что один из ссылок идёт вверх на один уровень вверх по оси). Однако, для уменьшения информативности, требование ослаблено для пальчиковых деревьев, и, вместо этого, каждый префикс и суффикс содержат от 1 до 4 элементов. Больше значений быть не может. Мы могли бы позволить сохранять префикс и суффикс в виде списков, но мы вместо этого будем использовать более селективные конструкторы, каждый из которых отвечает за своё правильное количество элементов:

-- Параметризуем аффикс типом данных, который он сохраняет
-- Тип эквивалентен спискам длиной от 1 до 4
data Affix a = One a
             | Two a a
             | Three a a a
             | Four a a a a
             deriving Show

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

-- Работам с аффиксами как со списками
instance IsList (Affix a) where
  type Item (Affix a) = a
  
  toList (One x)        = [x]
  toList (Two x y)      = [x, y]
  toList (Three x y z)  = [x, y, z]
  toList (Four x y z w) = [x, y, z, w]
  
  fromList [x]          = One x
  fromList [x, y]       = Two x y
  fromList [x, y, z]    = Three x y z
  fromList [x, y, z, w] = Four x y z w
  fromList _ = error "Affix must have one to four elements"
  
-- Следующая функция может быть куда более эффективной
-- Мы же будем использовать самую простую реализацию на сколько возможно
affixPrepend :: a -> Affix a -> Affix a
affixPrepend x = fromList . (x :) . toList

affixAppend :: a -> Affix a -> Affix a
affixAppend x = fromList . (++ [x]) . toList

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

-- Как обычно, параметрезируется тип тем типом, который он сохраняет в пальчиковом дереве
data FingerTree a 
  = Empty      -- Дерево может быть пустым
  | Single a   -- Дерево может содержать единственное значение, удобно это записать в отдельный случай
  
  -- Общий случай с префиксом, суффиксом и ссылкой на вглубь дерева
  | Deep {
    prefix :: Affix a,             -- Значения слева
    deeper :: FingerTree (Node a), -- Более глубокая часть пальчикового дерева, хранящая 2-3 деревья
    suffix :: Affix a              -- Значения справа
  }
  deriving Show

В определении выше, глубокое поле FingerTree a имеет тип FingerTree (Node a). Это означает, что значения, хранимые на следующем слое являются 2-3 деревьями, которые находятся на уровень глубже. Так, аффиксы первого слоя FingerTree Char хранят всего лишь Char, второй слой хранит FingerTree (Node Char) и имеет аффиксы, которые хранят 2-3 деревья глубиной 1 (Node Char). Третий слой будет уже FingerTree (Node (Node Char)) и имеет аффиксы, которые хранят 2-3 деревья глубиной 2 (Node (Node Char)).

Сейчас, когда мы определили наш тип пальчикового дерева, проведём немного больше времени и рассмотрим примет, который был показан выше, для того, чтобы понять как мы переводим его в структуру FingerTree Char:



Переведя это в дерево, получим:

layer3 :: FingerTree a
layer3 = Empty

layer2 :: FingerTree (Node Char)
layer2 = Deep prefix layer3 suffix
  where
    prefix = [Branch2 'i' 's', Branch2 'i' 's']
    suffix = [Branch3 'n' 'o' 't', Branch2 'a' 't']

layer1 :: FingerTree Char
layer1 = Deep prefix layer2 suffix
  where
    prefix = ['t', 'h']
    suffix = ['r', 'e', 'e']

exampleTree :: FingerTree Char
exampleTree = layer1

> exampleTree
Deep {prefix = Two 't' 'h', deeper = Deep {prefix = Two (Branch2 'i' 's') (Branch2 'i' 's'), deeper = Empty, 
suffix = Two (Branch3 'n' 'o' 't') (Branch2 'a' 't')}, suffix = Three 'r' 'e' 'e'}

В следующей части статьи мы научимся легко работать с пальчиковыми деревьями как с последовательностями.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.