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