Чисто функциональные структуры данных

    Признаюсь. Я не очень любил курс структур данных и алгоритмов в университете. Все эти стеки, очереди, кучи, деревья, графы (будь они не ладны) и прочие “остроумные” названия непонятных и сложных структур данных ни как не хотели закрепляться в моей голове. Как истинный “прагматик”, я уже на втором — третьем курсе свято верил в стандартную библиотеку классов и молился на дарованные нам (простым смертным) коллекции и контейнеры, бережно реализованные отцами и благородными донами CS. Казалось, все что можно было придумать — уже давно придумано и реализовано.

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

    И сейчас, я хочу показать вам небольшую частицу этого мира. Через замочную скважину, мы на секунду заглянем в этот удивительный мир, чтобы рассмотреть одного из наиболее ярких его обитателей — функциональное красно-черное дерево (КЧД).

    О чисто функциональных структурах данных


    Чисто функциональные структуры данных (ЧФСД) как класс существуют по двум причинам. Во-первых, для 99% императивных реализаций, камнем преткновения являются так называемые деструктивные апдейты (присваивание в переменную с потерей предыдущего значения). Понятно, что такой сценарий в функциональном мире невозможен, потому как мы всегда имеем дело с неизменяемыми объектами (immutable objects). Во вторых, в функциональном мире, после изменения коллекции мы ожидаем, что ее предыдущая версия нам остается доступной. Отсюда термин “персистетность” (persistent object) — поддержка множества версий объекта.

    Таким образом, нельзя просто взять и портировать известную императивную реализацию в функциональный мир. Необходимо помнить о его ограничениях (нет апдейтов) и требованиях (персистентность). Поэтому, процесс адаптации императивной реализации к функциональной среде — несколько более сложный и даже таинственный. И непревзойденным мастером в этом нелегком деле вот уже 15 лет считается Крис Окасаки со своим фундаментальным трудом — Purely Functional Data Structures.

    О Крисе и его книге


    В 1998 году Крис защитил диссертацию на тему ЧФСД и год спустя издал тезисы в виде книги. Книга Криса — это 200 страниц очень плотного (по информативности) и увлекательнейшего чтива. Текст, стиль которого граничит между научной работой и неформальным разговором с другом в баре, буквально читается как художественный роман. Труд Криса объединяет в себе лучшие практики и подходы в реализации ЧФСД, подкрепленные примерами широко известных (и не очень) структур данных на языках Standard ML и Haskell.

    О двух ключах


    Внимательный читатель скажет, что с такими требованиями и ограничениями все будет жутко тормозить. Создается впечатление, что любое изменение функциональной коллекции сопровождается ее полными копированием, дабы поддержать персистетность. Это не совсем так. Точнее — совсем не так. Копирование действительно присутствует, но в самых минимальных масштабах. Более формально — копируется только то, что действительно меняется. Остальная часть коллекции (как привило бОльшая) — расшаривается между версиями. Эти два предложения — ключи к пониманию чисто функциональных структур данных. Это уникальные инструменты, которые придуманы и отточены острейшими умами ФП. Имя этим инструментам — path copying (копирование только того, что затрагивается в операции) и structural sharing (общие части можно безопасно расшаривать между версиями, так как каждая такая часть сама является неизменяемой).

    О деревьях бинарного поиска


    Для начала рассмотрим обычные несбалансированные деревья бинарного поиска (ДБП), которые очень просто портируются в функциональный мир. Структура их выглядит так:

    abstract sealed class Tree {
      def value: Int
      def left: Tree
      def right: Tree
      def isEmpty: Boolean
    }
    
    case object Leaf extends Tree {
      def value: Int = fail("Empty tree.")
      def left: Tree = fail("Empty tree.")
      def right: Tree = fail("Empty tree.")
      def isEmpty: Boolean = true
    }
     
    case class Branch(value: Int, left: Tree = Leaf, right: Tree = Leaf) extends Tree {
      def isEmpty: Boolean = false
    }
    

    Нас интересует операция вставки, которая позволит нам сполна оценить силу и красоту инструментов path copying и structural sharing.

    def add(x: Int): Tree =
      if (isEmpty) Branch(x)
      else if (x < value) Branch(value, left.add(x), right)
      else if (x > value) Branch(value, left, right.add(x))
      else this
    

    Как и в императивном алгоритме, задача вставки сводится к задаче поиска подходящего места для нового узла. Однако, наша функциональная реализация будет слегка интереснее. Операция вставки в функциональное дерево объединяет два прохода — нисходящая (top-down) цепочка вызовов add (поиск места для вставки) и восходящая (bottom-up) цепочка вызовов конструктора Branch (копирование измененной части дерева вдоль search path). Первый проход (нисходящий поиск места вставки) является очевидной проекцией императивного алгоритма. Нас же интересует второй проход (восходящий path copying), который и делает нашу реализацию полностью функциональной (персистентной).


    Для сохранения свойства персистетности, необходимо поддерживать две версии коллекции — “до” и “после” вставки. Поэтому, любые изменения внутренней структуры узлов должны осуществляться над их копиями. В результате вставки в дерево, возникает своего рода “цепная реакция” обновления узлов (изменение ссылок на левого/правого потомка), распространяющаяся вдоль search path от места вставки к корню дерева. Именно так можно описать ту “магию”, которую реализует восходящий проход, объединяя в себе идеи и path copying (узлы «5» и «7» скопированы) и structural sharing (поддерево с ключами «1», «2», «3» содержится в обоих версиях коллекции).

    О красно-черных деревьях


    Красно-черное дерево (КЧД) — это самобалансирующееся дерево бинарного поиска для которого справедливы два инварианта:

    • Красный инвариант: никакой красный узел не имеет красного предка
    • Черный инвариант: каждый путь из корня в лист имеет одинаковое количество черных узлов

    Выполнение этих инвариантов гарантирует, что дерево будет сбалансированным с высотой log n, где n — количество узлов в дереве. Другими словами, основные операции над КЧД гарантированно выполняются за логарифмическое время.

    До 1999 года о КЧД в функциональном мире не было и речи. Императивная реализация имела дурную славу трудно портируемой, так как была полностью построена на сложных манипуляциях с указателями (pointers hell). Так, например, в Кормене рассмотрено восемь возможных случаев нарушения инвариантов и соответствующие меры по их устранению. Слегка отклоняясь от темы, можно добавить что именно из-за излишней сложности КЧД всячески старались заменить альтернативными вещами. Например, Седжевик предложил LLRB дерево в качестве упрощенной версии КЧД.

    Тем не менее, в 1999 Крис Окасаки опубликовал статью, в которой представил чисто функциональную реализацию КЧД. Эта статья до сих пор пользуется большим спросом как среди функциональных программистов так и императивных. Дело в том, что в статье представлена очень простая и понятная идея реализации, которую любой программист сможет понять и запрограммировать за 15 минут. Крис сказал, что есть всего 4 паттерна (см. картинку ниже), которые нарушают один из инвариантов. И наша задача — найти эти паттерны и перестроить их в одну и туже конструкцию с красным корнем и двумя черными детьми (см. картинку). И это все. Т.е. для того, чтобы получить КЧД из ДБП нам достаточно изменить второй (восходящий) проход алгоритма вставки. Теперь второй проход должен не просто копировать узлы вдоль search path, но также в случае соответствия поддерева одному из четырех паттернов, перестраивать его в безопасную конструкцию. Другими словами, фаза копирования в алгоритме совмещается с фазой балансировки.


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

    def add(x: Int): Tree = {
      def balancedAdd(t: Tree): Tree =
        if (t.isEmpty) Tree.make(Red, x)
        else if (x < t.value) balanceLeft(t.color, t.value, balancedAdd(t.left), t.right)
        else if (x > t.value) balanceRight(t.color, t.value, t.left, balancedAdd(t.right))
        else t
    
      def balanceLeft(c: Color, x: Int, l: Tree, r: Tree) = (c, l, r) match {
        case (Black, Branch(Red, y, Branch(Red, z, a, b), c), d) => 
          Tree.make(Red, y, Tree.make(Black, z, a, b), Tree.make(Black, x, c, d))
        case (Black, Branch(Red, z, a, Branch(Red, y, b, c)), d) => 
          Tree.make(Red, y, Tree.make(Black, z, a, b), Tree.make(Black, x, c, d))
        case _ => Tree.make(c, x, l, r)
      }
    
      def balanceRight(c: Color, x: A, l: Tree, r: Tree) = (c, l, r) match {
        case (Black, a, Branch(Red, y, b, Branch(Red, z, c, d))) =>
          Tree.make(Red, y, Tree.make(Black, x, a, b), Tree.make(Black, z, c, d))
        case (Black, a, Branch(Red, z, Branch(Red, y, b, c), d)) => 
          Tree.make(Red, y, Tree.make(Black, x, a, b), Tree.make(Black, z, c, d))
        case _ => Tree.make(c, x, l, r)
      }
    
      def blacken(t: Tree) = Tree.make(Black, t.value, t.left, t.right)
    
      blacken(balancedAdd(this))
    }
    

    В рассмотренной реализации есть еще пара моментов, которые требуют дополнительных комментариев. Во-первых, каждый узел дерева содержит дополнительную информацию — свой цвет (функция color). Во-вторых, функция balance, реализующая балансировку и копирование, разбита на две функции (пара balanceLeft и balanceRight), которые ожидают найти нарушение инвариантов в левом или правом поддереве (только вдоль search patch), и обрабатывают по два паттерна для каждой стороны соответственно.

    О сложности императивной реализации


    Возникает справедливый вопрос — почему реализация КЧД в императивном мире выглядит намного сложнее? Ответ достаточно простой — виной тому производительность. Имеея дело с указателями и изменяемыми переменнымии, мы можем остановить процесс балансировки на самых ранних его итерациях (при определенных условиях), тем самым сократив время работы алгоритма. В функциональной же среде, мы вынуждены копировать все затронутые узлы (affected nodes), поэтому лишние проверки наличия паттернов в поддеревьях нас не сильно смущают. Справедливости ради, стоит заменить, что предложенный алгоритм вставки в функциональное КЧД имеет такую-же асимптотическую сложность как и оригнальный алгоритм из императивного мира — О(log n).

    О дальнейших шагах


    Я собрал несколько отличных ссылок для тех, кто заинтересовался темой.

    Для исследователей:

    1. Моя обзорная презентация ЧФСД с примерами на Scala (видео доклада для Новосибирской Scala встречи тут)
    2. Моя попытка портирования бинарной кучи в функциональный мир
    3. Код КЧД и других структур на GitHub
    4. Удаление из КЧД от Метта Майта
    5. Блог Криса Окасаки

    Для практиков:

    1. Anre Andersonin в этой статье предложил сократить количество сравнений с «2 * d» на «d + 1», где d — глубина дерева (длина search path). Модифицируйте операцию вставки в ДБП так, чтобы она использовала меньшее количество сравнений.
    2. Напишите функцию fromOrderedList, которая строит сбалансированное ДБП из отсортированного списка. Hint: Hinze, Ralf. 1999 «Constructing red-black trees».
    Share post

    Comments 21

      –2
      А зачем портировать в функциональный мир именно бинарную кучу? Есть несколько весьма хороших чисто функциональных подходов к организации кучи, например goo.gl/VMgdG2
        +1
        Отличная статья, спасибо!
        Мне остался непонятен один момент: чем чисто функциональные структуры данных отличаются от обычных персистентных структур данных?
          +3
          Спасибо за фидбек!

          По делу. Во-первых, не совсем понятно что имеется ввиду под «обычные персистентные структуры». Не секрет, что ЧФСД можно реализовать и в императивной среде (например на Java), но там они не очень популярны, потому как выглядят чужеродными. Другое дело функциональные языки, где мутации, как правило, физически не-возможны — тут и выбора то большого нет. Во-вторых, эта терминология очень скользкая дорожка. Часто говоря «персистентная структура (persistent)» подразумевают ЧФСД (purely functional) и на оборот. Более того, есть еще одно смежное определение «неизменяемая структура (immutable)», которое часто используется вместо двух предыдущих. Пример. Есть совершенно идентичная реализация чисто-функционального вектора (bit-mapped vector trie) в Scala и Сlosure. В Scala он называется "immutable.Vector", в Closure — "PersistentVector".
            +1
            Мартин Одерски в своей книге исключительно зовет такие структуры неизменяемыми. Специально указывыет, что они часть функциональной парадигмы, но именно функциональными никогда не называет (как раз из-за того, что в императивных языках они тоже есть). Персистентность отмечена лишь как свойство.
              0
              >> не совсем понятно что имеется ввиду под «обычные персистентные структуры».
              Ну, например, есть такой класс задач, в котором нужно хранить всю историю изменений объекта. Временами встречал олимпиадные задачки такого рода, да и в реальной жизни аналогичных проблем хватает: скажем, для history viewer или undo/redo tracker. Понятно, что хранить каждую версию объекта отдельно — не очень здорово, поэтому переходим к персистентности. Я писал подобные решения на Java и C#, они вовсе не выглядели чужеродно, всё смотрелось вполне мило.
              И в общем случае в персистентной структуре речи об функциональности (как мне кажется) не идёт, можно даже не мыслить в функциональных терминах. Мы просто создаём новые элементы структуры, а старые не затираем. И требования неизменности в общем случае нет: скажем, пишу я history editor, который предусматривает перезапись истории. Меняю какой-нибудь элемент для одного состояния, а получается так, что он меняется для всех состояний — profit. И в таком подходе получаем изменяемость структуры by design. Поэтому, я считаю, нельзя считать персистентные структуры и ЧФСД синонимами.
              Понимаю, что с терминологией тут всё сложно, но хотелось бы разобраться, чтобы употреблять правильные термины по месту.
                0
                Пример с редактором истории странный. Персистентность предполагает, что вместо изменения объекта вы получаете модифицированную копию в довесок к сохранившемуся оригиналу. При редактировании истории вы хотите поменять какой-то элемент объекта (вероятно расшаренный участок памяти, если он не изменялся постоянно), и в этот момент структура должна потерять свою устойчивость.
                  0
                  Ну, всё зависит от структуры. Я не говорил, что такой манёвр всегда и легко реализуется для произвольной структуры, но на уровне подхода к решению абстрактной задачи такую идею рассматривать вполне можно. Просто хотелось привести какой-нибудь максимально простой пример изменяемой персистентной структуры.
                    0
                    Я как раз про то, что в момент изменения всей истории это уже эфемерная структура, так как предыдущих состояний больше нет.
                      0
                      Ну, тут опять возникает вопрос терминологии. Структура как бы эфемерная, но для её построения мы используем персистентный подход. Оригинально структура персистентная (стандартные операции добавления/удаления/модификации элементов идут как персистентные), просто мы навешиваем сверху дополнительную операцию.
                        0
                        Угу, именно терминологии. Она скорее устойчива до момента использования операции по изменению всего и вся. К сожалению в функциональных подходах я еще слаб, но насколько помню такие ситуации разрешаются с помощью монад.
                  +1
                  Я попробую ответить. Для меня лично, это тоже больное место — эта терминология. В умных книжках, все эти моменты ненавязчиво опускаются (т.к. видимо являются чем-то сверхэлементарным для авторов, не требующим пояснений). Что для нас — перфекционистов — является большим испытанием. Я для себя решил разграничить эти вещи следующим образом:

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

                  Неизменяемость — свойство объекта/структуры запрещяющее его любые изменения. Понятно, что неизменяемая структура после модификации представляет собой копию предыдущей версии + конкретные изменения (например новый элемент). При этом, неизменяемые объекты всегда персистентны (т.е. версию которую мы когда-то создали мы не можем изменить/удалить). Такие структуры тоже есть в императивном мире, например java.lang.String (моя любимая коллекция). Неизменяемость — это ограничение функционального мира (т.е. отсутствие деструктивных апдейтов). Может ли неизменяемая структура быть построена на изменяемом внутреннем состоянии? Я думаю да. Есть такое понятие как локализация мутации. Отличный пример такой мутации Паша Павлов рассказывает в этом видео на примере очереди банкиров. Т.е. формально коллекция неизменяемая (по набору элементов), но во внтуренней структуре есть некоторые места, которые подвержены мутациям, т.е. нельзя сказать, что такие структуры всегда без сайд-эффектов.

                  ЧФСД — это класс структур без сайд-эффектов. Баста.
                    +5
                    Внесу свои пять копеек.

                    Персистентность бывает разной. Различают три вида.
                    1. Частичная. Можем читать любую версию, но менять только последнюю. Граф версий представляет собой односвязный список.
                    2. Полная. Можем читать и менять любую версию. Граф версий — это дерево.
                    3. Конфлюэнтная. Это полная персистентность с возможностью мерджа версий. Граф версий — даг (ориентированный ациклический граф).

                    ЧФСД гарантирует все три уровня персистентности. С другой стороны, почти любую императивную структуру данных можно превратить в частичную или полную с амортизационно константным ухудшением по памяти и времени. Правда, она не будет ЧФСД.
                +3
                В первую очередь — отсутствием сайд-эффектов от операций над ними.
                  0
                  Это уж скорее как следствие устойчивости проявляется. Персистентные данные не изменяемы, не может там быть побочных действий.
                0
                Про асимптотическую сложность интересен комментарий от Gaperton:

                2) Это важно по той причине, что существуют алгоритмы, которые, будучи записаны в функциональном стиле, поимеют добавочный log(N) в своей асимптотике (и никакие фокусы вроде монад и уникалных типов не помогут). И по другому никак. Depth-first graph traversal — пример такого алгоритма (O(N) императивный, О(N)log(N) ффункциональный). А испорченная асимптотика во многих случаях гораздо хуже плохой кодогенерации.

                Программист на OCaml здесь выкрутится, выделив в алгоритме небольшую императивную часть и избавившись от log(N). А вот программистам на Clean и Haskell придется хуже — в тяжелом случае придется выносить часть алгоритма в С++. Что, впрочем, не фокус — прямо скажем. Вставки на ассемблере в программу на С лет десять назад никого не пугали, надо заметить.

                И это еще не все. В функциональном коде применяются доволно специфические структуры данных, имеющие, с одной стороны, большуу константу при О для основных операций, но с другой стороны, аллокаторы этих языков заточенны под элементы таких структур данных. Так что впрямую сравнивать производительность программ нельзя — в случае ФЯ выбирается другая структура данных, а значит, будет отличаться и алгоритм. Естественно — в медленную сторону. Т.е либо будет больше константа в алгоритме, либо до кучи все еще и умножится на log(N).

                  +3
                  Хочу добавить, что Геогий Бронников (переводчик SICP) готовит перевод книги Окасаки на русский, причём каждый может ему в этом помочь, т.к. книга выложена на GitHub.
                    0
                    эм, а кто следит за версионностью структуры? как удаляются старые версии? По празнаку отсуствия ссылок на объект?
                      +6
                      Старые версии удаляются сборщиком мусора.
                        0
                        а в языках без гц?
                          0
                          В языках без GC придётся реализовать собственную сборку мусора, например, через Boehm GC или std::shared_ptr<const Node>.
                      0
                      Все эти стеки, очереди, кучи, деревья, графы (будь они не ладны) и прочие “остроумные” названия непонятных и сложных структур данных ни как не хотели закрепляться в моей голове
                      Ну вот к названиям ленивые студенты ещё не прикапывались.

                      Only users with full accounts can post comments. Log in, please.