Cofree Will Tear Us Apart

let author   = "Мурат Касимов"
    date     = fromGregorian 2018 may 23
    category = "Пакеты"
    tags     = ["cofree"]

Всем привет.

В последнее время я работаю с распределенными системами и часто встречаюсь с проблемами работы с данными, части которых могут находиться в различных местах. Ну и так как я уже продолжительное время пишу на 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

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

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 и возвращать параметры соединения и ключ для сохраненного сегмента. В общем, не так важно.

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.

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

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