Cofree Will Tear Us Apart

Всем привет.


В последнее время я работаю с распределенными системами и часто встречаюсь с проблемами работы с данными, части которых могут находиться в различных местах. Ну и так как я уже продолжительное время пишу на Haskell, описание проблемы и мощная система типов здорово помогли в дальнейшем развитии этой идеи. Речь пойдет о том, как всего одна несущая алгебраическая конструкция позволила решить задачу рециркулирующих данных в общем виде.


Введение и мотивация


По ходу повествования мы встретим три основных тезиса, которые дадут представление о желаемом результате.


Представьте, что вам нужно написать программу, которая работает с какими-то данными. Если данных слишком много, то вам придется задумываться об организации и хранении — так как хранить их в оперативной памяти слишком ненадежно, может не хватить места или во время аварийного завершения программы вы их полностью потеряете.


Использовать базу данных? Какие? Реляционные, документоориентированные, хранилища типа "ключ-значение" или что-нибудь попроще — просто писать в файлик? Что же, каждая из этих опций имеет собственные достоинства и недостатки.


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


Тезис 1. Нам не нужно хранить все данные в пямяти, а только какую-то часть.


И правда, когда мы работаем с базами данных, мы пишем запросы, по которым мы эти данные можем получать в память. Запись в базе данных — это ведь только кусочек от всего нашего общего массива с информацией. В случае реляционных — это записи в таблицах. В случае хранилищ типа "ключ-значение" — пара "ключ-значение".


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


Тезис 2. Мы хотим абстрагироваться от способа хранения и обработки информации.


Основываясь на двух предыдущих свойствах, нам нужен способ разделения данных, с которыми мы сейчас работаем и которые фактически находятся в оперативной памяти, и данными, которые законсервированы где-нибудь на жестком диске. Нам нужен способ их разделения.


Как же мы будем их разделять? Нам нужна такая структура, которая позволит безболезненно разделять и соединять данные. Давайте поразмышляем на эту тему?


  • Списки? Можно, но есть проблемы. Стоимость доступа к произвольному элементу — O(n). Стоимость объединения двух списков такая же.
  • Какие-нибудь деревья? Если это бинарные, то стоимость доступа в хорошем случае снижается до O(log n). Но нам не всегда будет требоваться хранить отсортированные данные. Слишком частный случай, нам не подходит.
  • Массивы? Стоимость доступа — O(1). Но тоже частный случай, просто столкнемся с другими проблемами — эта структура вообще не алгебраическая.

Тезис 3. Нам нужна несущая конструкция, способная охватить в своем описании многие другие структуры данных.


И такая структура есть!


Несущая конструкция Cofree


Многие Haskell-программисты знакомы с типом Free. Но почему-то его дуальности, Cofree, уделено не так много внимания. А разница между ними составляет одну деталь: Free тип — это сумма из некоторого а и t (Free t a), а Cofree — произведение:


Free t a = a + t (Free t a)
Cofree t a = a × t (Cofree t a)

Это означает, что если мы выберем Cofree в качестве нашей несущей конструкции, у структуры данных, определенной через последнюю, появятся несколько особенностей:


  • Эта структура всегда будет непустой, она всегда будет иметь по крайней мере один элемент.
  • Так как Cofree также имеет экземпляр класса типов Comonad, мы уже имеем много полезных методов задаром:
    • extract — Получить значение, которое находится в фокусе.
    • extend — Обновить значения во всей структуре в зависимости от контекста.
    • unwrap — Получить множитель произведения, сегмент информации.
    • coiter — Сгенерировать структуру из начального значения.

Так каким образом мы собираемся собирать различные структуры данных с помощью Cofree? Нам всего-то и нужно что инстанциировать тип t в Cofree t a, имеющий экземпляр класса типов Functor.


Представим, что нам нужен стэк или непустой список — простая структура данных. Тут нам подойдет Maybe, в этом случае, конструкторы последнего выполняют роль генератора — Just позволят продолжить описывать структуру, а Nothing является терминирующим инвариантом.:


data Maybe a = Just a | Nothing

type Stack = Cofree Maybe

example :: Stack Int
example = 1 :< Just (2 :< Just (3 :< Nothing))

Вспомогательная конструкция Shape


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


data Shape t raw value
    = Ready (t value) -- ^ Сегмент данных в оперативной памяти
    | Converted raw -- ^ Cегмент данных где-нибудь в другом месте

data Apart t raw value = Apart (Cofree (Shape t raw) value)

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


Пример использования Apart


А теперь, давайте составим иллюстрированный пример. Представьте, что мы хотим поработать с бинарным деревом. Как мы можем описать его через Cofree? Через "функтор ветвления". Узел дерева может не иметь потомков, иметь левого потомка, правого потомка или обоих. Давайте прямо так и закодируем:


data Crotch a = End | Less a | Greater a | Crotch a a

type Binary = Cofree Crotch

Отлично, теперь мы можем написать значение для этого типа, пример бинарного дерева поиска возьмем с одноименной статьи Википедии:


image


example :: Binary Int
example = 8 :< Crotch
    (3:< Crotch 
        (1 :< End) 
        (6 :< Crotch 
            (4 :< End) 
            (7 :< End)))
    (10 :< Greater 
        (14 :< Less 
            (13 :< End)))

Опробуем первый комбинатор — limit, он позволит нам обрезать наше дерево по высоте:


limit 3 do_something_with_the_rest example

Я намеренно абстрагировался от способа сохранения, чтобы не заострять на этом внимание — мы можем хранить не вошедшие в диапазон сегменты в файл и функция do_something_with_rest может возвращать нам название файла и номер строки. Или вовсе класть в Redis/Memcashed/Tarantool и возвращать параметры соединения и ключ для сохраненного сегмента. В общем, не так важно.


scattered :: Scattered Binary Int _
scattered = 8 :< Crotch 
    (3 :< Crotch 
        (1 :< {RESTORE_INFO}) 
        (6 :< {RESTORE_INFO})) 
    (10 :< Greater 
        (14 :< {RESTORE_INFO}))

И вот, что осталось от нашего дерева — оно обрезалось по высоте. Но информация для восстановления осталась на месте исчезнувших трех сегментов. Представление выше на самом деле скрывает конструктор Ready, а Converted заменен на фигурные скобочки (спасибо хитрому экземпляру класса Show).


С помощью комбинатора recover мы можем вернуть всю структуру данных в память:


recover back_to_RAM scattered

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


fluent do_something_whereever_they_are scattered

В качестве заключения


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


Идеи, описанные выше, были реализованы в библиотеке, которой пока нет на Hackage, но находящейся в фазе активного развития.


На данный момент мне удалось описать направленный ацикличный граф, бинарные, префиксные, розовые, АВЛ-деревья и немного отдельных функций для работы с ними.


Сама идея использования Cofree в качестве несущей конструкции для других структур данных была мною подхвачена из описания к модулю Control.Comonad.Cofree в пакете free Эдварда Кметта.


Идея алгебраического описания графов была использована здесь из работы Андрея Мохова.


В планах также остается:


  • Реализовать пальчиковые, Splay-деревья и другие структуры посложнее.
  • Написать побольше функций для работы с ними (вставки, удаления, балансировки и т.п.).
  • Естественные преобразования между ними (так как функтор как раз и определяет особенности отдельной структуры).
  • Оптические интерфейсы для работы с внутренностями структур.
  • Изучить способы совместимости комбинаторов со стриминговыми библиотеками (pipes, conduit, io-streams, machines).
  • Написать полноценные тесты свойств отдельных структур данных.
  • Бенчмарки, в первую очередь с популярными containers.

Пишите в комментариях, какие структуры данных вам бы хотелось использовать таким образом и какие комбинаторы могли бы пригодиться в повседневной практике. Буду рад любым замечаниям и критике.


Спасибо за внимание.

Поделиться публикацией

Похожие публикации

Комментарии 0

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое