- PVSM.RU - https://www.pvsm.ru -
Всем привет.
В последнее время я работаю с распределенными системами и часто я встречаюсь с проблемами работы с данными, части которых могут в находится в различных местах. Ну и так как я уже продолжительное время пишу на Haskell, описание проблемы и мощная система типов здорово помогли в дальнейшем развитии этой идеи. Речь пойдет о том, как всего одна несущая алгебраическая конструкция позволила решить задачу рециркулирующих данных в общем виде.
По ходу повествования мы встретим три основных тезиса, которые дадут представление о желаемом результате.
Представьте, что вам нужно написать программу, которая работает с какими-то данными. Если данных слишком много, то вам придется задумываться об организации и хранении — так как хранить их в оперативной памяти слишком ненадежно, может не хватить места или во время аварийного завершения программы вы их полностью потеряете.
Использовать базу данных? Какие? Реляционные, документоориентированные, хранилища типа "ключ-значение" или что-нибудь попроще — просто писать в файлик? Что же, каждая из этих опций имеет собственные достоинства и недостатки.
Где бы мы их не хранили, нам в любом случае, чтобы сделать с этими данными что-то, что выходит за пределы возможностей выбранного нами способа, необходимо загрузить их обратно в оперативную память. Разумеется, только какую-то часть, а не все подряд, по причинам описанным выше.
Тезис 1. Нам не нужно хранить все данные в пямяти, а только какую-то часть.
И правда, когда мы работаем с базами данных, мы пишем запросы, по которым мы эти данные можем получать в память. Запись в базе данных — это ведь только кусочек от всего нашего общего массива с информацией. В случае реляционных — это записи в таблицах. В случае хранилищ типа "ключ-значение" — пара "ключ-значение".
Когда вы пишете приложения для реального мира, вам приходится подстраивать схему организацию данных из своей предметной области под ограничения выбранного вами способа. Это будет зависеть от степени связности, аспектов производительности и многих других факторов.
Тезис 2. Мы хотим абстрагироваться от способа хранения и обработки информации.
Основываясь на двух предыдущих свойствах, нам нужен способ разделения данных, с которыми мы сейчас работаем и которые фактически находятся в оперативной памяти и данными, которые законсервированы где-нибудь на жестком диске. Нам нужен способ их разделения.
Как же мы будем их разделять? Нам нужна такая структура которая позволит безболезненно разделять и соединять данные. Давайте поразмышляем на эту тему?
Тезис 3. Нам нужна несущая конструкция, способная охватить в своем описании многие другие структуры данных.
И такая структура есть!
Многие 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
в качестве нашей несущей конструкции, у структуры данных определенных через последнюю появятся несколько особенностей:
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))
Хорошо, мы разобрались как можно описывать структуры данных на 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, который будет контролировать, какая часть данных где находится.
А теперь, давайте составим иллюстрированный пример. Представьте, что мы хотим поработать с бинарным деревом. Как мы можем описать его через 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
Вот так алгебраические структуры данных и понятия из теории категорий позволили сначала описать, а после и решить задачу рециркулирующих данных в самом общем виде.
Идеи описанные выше были реализованы в библиотеке [1], которой пока нет на Hackage, но находящейся в фазе активного развития.
На данный момент мне удалось описать направленный ацикличный граф, бинарные, префиксные, розовые, АВЛ-деревья и немного отдельных функций для работы с ними.
Сама идея использования Cofree в качестве несущей конструкции для других структур данных была мною подхвачена из описания к модулю Control.Comonad.Cofree
[2] в пакете free
[3] Эдварда Кметта.
Идея алгебраического описания графов была использована здесь из работы Андрея Мохова [4].
В планах также остается:
pipes
[5], conduit
[6], io-streams
[7], machines
[8]).containers
[9].Пишите в комментариях, какие структуры данных вам бы хотелось использовать таким образом и какие комбинаторы могли бы пригодится в повседневной практике. Буду рад любым замечаниям и критике.
Спасибо за внимание.
Автор: Мурат Касимов
Источник [10]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/struktury-danny-h/280589
Ссылки в тексте:
[1] библиотеке: https://github.com/iokasimov/apart
[2] Control.Comonad.Cofree
: https://hackage.haskell.org/package/free-5.0.2/docs/Control-Comonad-Cofree.html
[3] free
: https://hackage.haskell.org/package/free
[4] работы Андрея Мохова: https://doi.org/10.1145/3122955.3122956
[5] pipes
: http://hackage.haskell.org/package/pipes
[6] conduit
: http://hackage.haskell.org/package/conduit
[7] io-streams
: http://hackage.haskell.org/package/io-streams
[8] machines
: http://hackage.haskell.org/package/machines
[9] containers
: http://hackage.haskell.org/package/containers
[10] Источник: https://habr.com/post/358976/?utm_source=habrahabr&utm_medium=rss&utm_campaign=358976
Нажмите здесь для печати.