В статье представлена реализация структуры данных “Словарь” в “функциональном стиле” на двух статических методах и делегате в C#.
Написано под впечатлением от главы “Total and Partial Maps” из Software Foundation. Volume 1: Logical Foundation.
Всегда интересно посмотреть на некоторые знакомые и привычные вещи немного под другим углом. Указанная выше глава из Software Foundation как раз способствовала такому “виденью”.
Речь пойдет о структуре данных “словарь” (отображение или ассоциативный массив). В программировании мы чаще всего пользуемся шаблоном мышления, который предполагает, что есть данные и функции, которые над этими данными выполняют различные операции. При этом данные могут быть представлены как некоторые одиночные элементы – объекты простых типов (числа, bool’ы, символы и т.п.) и объекты сложных типов, которые мы проектируем сами (Student, Employer, Car, Factory и т.п.), так и коллекции, состоящие из этих одиночных элементов: множества, словари, списки, массивы, стеки и т.п. Коллекции могу существовать в виде обобщенных вариантов, в этом случае предполагается, что тип объектов, которые будут храниться в ней, задается (заранее известен) до компиляции (для статически типизированных языков), это способствует большей производительности и лучшей безопасности.
Если немного помедитировать над лямбда-исчислением Черча, то в какой-то момент становится понятно, что описанное выше восприятие данных — это всего лишь удобная абстракция, которую мы перетащили из нашего “физического” мира. Например, у нас есть яблоко (это объект данных), и мы над ним с помощью определенной функции (соковыжималка) производим работу, преобразуя его в сок (объект другого типа). А вот само яблоко, мы, как правило, в качестве функции не рассматриваем. В лямба-исчислении всё есть функция – то, над чем выполняются операции и то, что эти операции выполняет. Фон-неймановская архитектура, по дизайну которой построены почти все современные вычислительные системы, также нас толкает к тому, что функции и данные — это одно и тоже: байты в памяти мы можем интерпретировать как данные и как операции для работы над данными, тут другая идея: всё есть данные (биты), а уж как мы их интерпретируем — это наша ответственность.
Вернемся к структурам данных. В C# связный список, состоящий из элементов типа int, объявляется вот так:
LinkedList<int> someList = new();
Обобщенный вариант имеет вид: LinkedList<T>, в этом случае о LinkedList можно думать как о “функции”, которая переводит T -> LinkedList<T>. Внутренняя механика C# так явно это не реализует, но думать о LinkedList как о функции над типами нам никто не запрещает.
Теперь “функционально” подумаем о словаре. Сделаем это с немного другого угла, нежели чем выше представленный LinkedList, то была просто разминка. Вариант объявления словаря в C#:
Dictionary<string, int> someDict = new() { ["a"] = 1 };
Когда мы обращаемся к элементу словаря через ключ, то делаем следующее:
var value = someDict["a"];
Если мысленно квадратные скобки заменить на круглые, то объект типа Dictionary<string, int> можно рассматривать как функцию со следующим прототипом:
int someDict(string key);
Т.е. словарь можно представить как функцию, которая для заданного аргумента возвращает конкретное значение.
Построим такой “функциональный” словарь в C#. Создадим два вида словарей: TotalMap и PartialMap. Особенность TotalMap заключается в том, что если в нем нет записи для заданного ключа, то он вернет предварительно установленное значение по умолчанию. PartialMap работает с Option значением, т. е. если значения по заданному ключу нет, то он вернет None, если есть, то значение, упакованное в Some (более подробно про Option далее).
Сам словарь, как мы сказали выше, будем считать функцией, в C# его можно представить как делегат:
public delegate V TotalMap<K, V>(K key)
where K: IEquatable<K>;
Где K – тип ключа, V – тип значения. Дополнительно, нам нужно наложить ограничение на ключ, чтобы он поддерживал интерфейс IEquatable для сравнения элементов типа K между собой.
Следующий шаг — это построить функцию, которая конструирует словарь с заданным значением по умолчанию (напоминаю, что словарь у нас — это ФУНКЦИЯ!):
static TotalMap<K, V> TEmpty<K, V>(V defaultValue)
where K : IEquatable<K> =>
(K _) => defaultValue;
TEmpty принимает на вход значение по умолчанию и возвращает функцию, которая для любого значения типа K выдает defaultValue.
И последнее, что нужно сделать — это создать функцию, которая “добавляет” в наш словарь элементы (пары ключ-значение):
public static TotalMap<K, V> TUpdate<K, V>(TotalMap<K, V> totalMap, K key, V value)
where K : IEquatable<K> =>
(K k) => k.Equals(key) switch
{
true => value,
false => totalMap(k)
};
TUpdate принимает словарь, в который нужно “добавить” новую пару ключ-значение и возвращает функцию, которая для указанного ключа выдает значение, либо результат применения переданного в TUpdate словаря к ключу.
Объединим все наработки в один статический класс:
public static class TotalMapFn
{
public delegate V TotalMap<K, V>(K key)
where K: IEquatable<K>;
public static TotalMap<K, V> TEmpty<K, V>(V defaultValue)
where K : IEquatable<K> =>
(K _) => defaultValue;
public static TotalMap<K, V> TUpdate<K, V>(
TotalMap<K, V> totalMap,
K key,
V value)
where K : IEquatable<K> =>
(K k) => k.Equals(key) switch
{
true => value,
false => totalMap(k)
};
}
Проверим работу нашего “функционального” словаря:
var tm1 = TUpdate(TUpdate(TEmpty<string, int>(-1), "orange", 1), "apple", 2);
Console.WriteLine($"default value: {tm1("test")}");
Console.WriteLine($"at \"orange\": {tm1("orange")}");
Console.WriteLine($"at \"apple\": {tm1("apple")}");
Если вы запустите этот код, то увидите примерно следующее:
default value: -1 at "orange": 1 at "apple": 2
Разберем более подробно то, что мы написали:
В примере, tm1 – это функция (если быть точнее, то делегат конкретной структуры). Т.е. мы, используя определенный набор функций (TEmpty и TUpdate), построили другую функцию, поведение которой аналогично тому, как ведет себя структура данных “словарь”.
Для того чтобы не указывать явно типы ключа и значения можно создать псевдонимы для функций TEmpty и TUpdate:
Func<TotalMap<string, int>, string, int, TotalMap<string, int>> t_update = TUpdate<string, int>; Func<int, TotalMap<string, int>> t_empty = TEmpty<string, int>;
В этом случае код, создающий словарь, как в предыдущем примере, будет выглядеть так:
var tm2 = t_update(t_update(t_empty(-1), "orange", 1), "apple", 2);
Обратите внимание, нам не пришлось реализовывать функцию для поиска значения по ключу, это нужно было бы сделать, если бы словарь был реализован, например, на списках. В нашем случае, сама конструкция словаря автоматически “реализует” данную функцию.
Теперь перейдем к PartialMap. Для начала разберемся с Option. Довольно часто бывают ситуации, когда функция должна вернуть результат, но значения, которое бы его, по факту, представляло нет. Например, нет значения по заданному ключу в словаре или нет данных по указанному запросу в базе и т.п. Для обработки таких ситуаций существуют несколько решений:
- Вернут
null, но с ним существует огромное количество проблем. Хотелось бы чтобы функция возвращала значение, с которым можно работать, а не что-то при обращении с чем может возникнутьNull Reference Exception. - Выбросить исключение. Если мы пишем какую-то функцию, то хотелось бы по ее прототипу понимать, что она принимает, и что возвращает. Во многих языках программирования в прототипе функции (метода) типы возможных выбрасываемых исключений не прописываются (Python, C#), т. е. мы имеем некоторое недокументированное поведение.
- Вернуть объект типа
MayBe(илиOption), Такой подход применяется в функциональных языках программирования для обработки подобных ситуаций. Суть в том, что мы либо возвращаемNone, что соответствует “отсутствию” “нормального” результата, либоSome x, гдеx– возвращаемое значение, аSome– это конструктор для упаковкиxв элемент типаMayBe. В этом случаеNone– это значение, с которым можно работать, например, вызвать у негоToString().
К сожалению, в C# отсутствуют алгебраические типы данных (в частности, нам тут нужен тип-сумма), и мы не можем сконструировать нормальный Option, поэтому построим его следующим образом:
public abstract record Option<T>
{
public static Some<T> Some(T value) => new(value);
public static None<T> None() => new();
}
public record Some<T>(T Value) : Option<T> { }
public record None<T>() : Option<T> { }
По аналогии с TotalMap, построим PartialMap:
public static class PartialMapFn
{
public delegate Option<V> PartialMap<K, V>(K key)
where K : IEquatable<K>;
public static PartialMap<K, V> PEmpty<K, V>()
where K : IEquatable<K> =>
(_) => Option<V>.None();
public static PartialMap<K, V> PUpdate<K, V>(PartialMap<K, V> partialMap, K key, V value)
where K : IEquatable<K> =>
(k) => k.Equals(key) switch
{
true => Option<V>.Some(value),
false => partialMap(k)
};
}
PartialMap, в случае, если нет значения по указанному ключу, возвращает None, если есть, то Some. Пример, демонстрирующий работу с PartialMap:
var pm1 = PUpdate(PUpdate(PEmpty<string, int>(), "car", 1), "bike", 2);
Console.WriteLine($"Default value of pm1: {pm1("test")}");
Console.WriteLine($"at \"car\": {pm1("car")}");
Console.WriteLine($"at \"bike\": {pm1("bike")}");
По аналогии с TotalMap создадим псевдонимы для конкретных типов:
Func<PartialMap<string, int>, string, int, PartialMap<string, int>> p_update = PUpdate<string, int>; Func<PartialMap<string, int>> p_empty = PEmpty<string, int>;
Построим словарь с использованием указанных выше делегатов:
var pm2 = p_update(p_update(p_empty(), "car", 1), "bike", 2);
Если мы пытаемся получить значение по ключу для pm2, то результатом будет либо запакованное значение, либо None. Это можно использовать в pattern matching’е:
var value = pm2("car") switch
{
None<int> => "No value in dict.",
Some<int> v => $"Value: {v.Value}",
_ => "Something wrong!"
};
Единственное дополнение, которое приходится делать из-за того, что Option не является классическим типом суммой, это строка:
_ => "Something wrong!"
Возникает вопрос: зачем всё это нужно? Зачем строить “словарь” функционально? Если ответить на него в контексте “зачем это делать на C#?”, то: для развлечения; какой-то особой практической пользы, наверное, от такого решения нет. Если же не привязываться к C#, то это вопрос аналогичный, например такому: почему для типа данных unsigned long нужно резервировать 8 байт? Ответ в обоих случаях: потому что так удобно! Здесь следует сразу же уточнить: а для чего удобно? Натуральное число мы можем представить как совокупность из 64 бит, которые последовательно расположены в памяти компьютера, такое представление удобно, когда мы пишем программы практически для любой предметной области (драйверы, мобильные приложения, сервисы) и на любом языке (почти любом). В этом случае удобство связано с разработкой и компиляцией, в итоге мы можем получить работающее приложение с приемлемой производительностью. Но если мы пытаемся рассуждать о свойствах программы и доказывать некоторые утверждения относительно кода, который мы написали — это становится неудобным.
Такие задачи возникаю в области формальной верификации ПО, доказательств теорем и т.п. В этом случае, представление чисел как набора из 64 бит уже не будет удобным. Для данных задач используются специальные языки, в которых тип “Натуральное число” можно построить индуктивным способом (например, так делают в Coq). Такая же история со словарем в “функциональной форме”, с ним удобно строить и доказывать различные утверждения относительно кода в системах типа proof assistant (Coq и прочие), а в том виде как мы привыкли видеть словарь, они хорошо подходят для “классических” задач, с которыми разработчик сталкивается в повседневной работе.
Исходный код всего представленного в статье лежит тут.
Про язык C# можете прочитать в нашем “цикле уроков“.
