Тем же, кто уже знаком в достаточной мере с монадами, но все равно решит прочитать мой пост, предлагаю выразить критику, буду рад.
Значительная часть блогов лишь мельком затрагивает понятие монады чтобы рассказать о каком-нибудь монадном парсер-комбинаторе, асинхронном workflow или о чем-то пострашнее. Некоторые блоги и материалы отталкиваются от математики, комбинирования чистых функций, пользы монадах в функциональном программировании и прочей теории. А я предлагаю пожевать знакомые большинству концепции и повести читателя не от простого к сложному, а от уже знакомого к более простому.
Знакомство
Полагаю, что многие из разработчиков C# пользуются методом Enumerable.SelectMany либо вложенными друг в друга from clause. На всякий случай напомню, что from clause транслируется компилятором в вызов SelectMany. Тем, кто не понимает эти конструкции (читай не привыкнул к ним) рекомендую начать к ним привыкать как можно скорее. Это не сложно, к хорошему быстро привыкаешь. Вот статья, где упоминаются вложенные from конструкции - Query Expression Basics.Рассмотрим следующий запрос в форме Query Expression:
IEnumerable<City> cityQuery =
from country in countries
from city in country.Cities
select city;Его можно записать в следующем виде: IEnumerable<City> cityQuery = countries
.SelectMany(country => country.Cities);Компилятор собственно и производит подобное преобразование, только он использует более сложную перегрузку метода SelectMany. Нам она пока ни к чему, сосредоточим внимание на более простой функции SelectMany. Вот ее сигнатура: IEnumerable<TResult> SelectMany<TSource, TResult>( this IEnumerable<TSource> source, Func<TSource, IEnumerable<TResult>> selector)Напомню её назначение:
Проецирует каждый элемент последовательности в объект IEnumerable<T> и объединяет результирующие последовательности в одну последовательность.Думаю, стоит обратить внимание на одну деталь:
именно проецирует (связывает), а не выбирает. То что у объекта типа Country есть свойство со списком городов – это лишь совпадение. Для проекции мы могли бы использовать не только свойство Cities, а любой другой способ получения списка городов, будь они записаны в файле, в базе данных или возвращены веб-сервисом. Да и вместо класса страны мог быть ее числовой код.Вобщем, знакомьтесь, SelectMany это и есть монада! Точнее ее часть… Точнее часть одной из монад… Но это пока не важно. Важно то, что если вы раньше не были знакомы с монадами, то теперь вы можете в ответ на вопрос “знаете ли вы что такое монады, используете ли их?” отвечать “А-то!!!” и многозначительно ухмыляться.
Дабы избежать недопонимания, отметём все лишнее, что было помянуто. Сначала исключим Query Expressions (это from … select…). Они к монадам не имеют ровно никакого отношения. Это только синтаксический сахар, который может быть применен в том числе и к монадным вычислениям (позже об этом вспомним). Вообще любое Query Expressions выражение можно записать в эквивалентной форме в стандартном синтаксисе (чем и занимается компилятор) без потери функциональности. Усугубится только вид выражения, да и то не всегда.
Ленивые вычисления (это я про итераторы IEnumerable<T>) тоже не имеют прямого отношения к монадам. Вместо IEnumerable<TSource> и IEnumerable<TResult> мы могли бы использовать List<TSource> и List<TResult> без потери работоспособности выражения. Разве что оно стало бы менее обобщенным, и позволяло бы работать только со списками. Т.е. IEnumerable<T> тоже левый тип.
Extension method-ы не имеют отношения к монадам. Это всего лишь удобная форма записи вызова функций через точку (как если бы это был метод экземпляра).
Итого: тип IEnumerable<?> заменяю на некий C<?>, чтобы не мозолил глаза. Нам не важно что там за тип, главное что это generic тип. Настолько не важно, что я заменю его сразу на M<?> (позже станет ясно, почему именно M). А так же выкину ключевое слово this и заменю название метода SelectMany на более традиционное Bind (в языке Haskell это будет “>>=”). Вот что получилось:
M<U> Bind<T,U>(M<T> source, Func<T, M<U>> selector);Мы получили что-то более широкое, чем SelectMany. Я бы сказал, что мы получили целый класс функций, и SelectMany вместе с типом IEnumerable<?> определенно принадлежит к этому классу. Пора, пожалуй ввести определение монады, а после я покажу, близкие к природе SelectMany монады.
Определение монады
Монадой называется тройка (M, Return, Bind) где- М – одноаргументный generic тип M<T>
- Return – функция, конструирующий экземпляр монадного типа М<T>
- Bind – функция, связывающая монадные вычисления
Пожуём немного определение…
Тип M из определения - это тот самый тип M, которым я выше заменил IEnumerable в сигнатуре метода SelectMany. Он называется монадным типом.
Фунция Return – это функция, которая должна сгенерировать экземпляр монадного типа из экземпляра типа T (generic параметра типа M). Так, если нам требуется определить функцию Return для уже знакомой нам монады (с функцией SelectMany в качестве функции Bind), то она могла бы быть реализованной следующим образом:
IEnumerable<T> Return<T>(T value)
{
return new T[] { value };
}Функция Bind связывает монадное вычисление M<T> с монадным результатом М<U> с помощью функции проекции Func<T, M<U>>. Итого, если мы возьмем определение монады, рассмотрим его в приложении к типу IEnumerable<T>, то тройка (IEnumerable<T>, Return, SelectMany) формально представляет монаду IEnumerable. Выполнение упомянутых монадных законов проверять не будем. Пост и так получился довольно длинным, хотя сложного в этом ничего нет. Заинтригованные читатели смогут проверить выполнение монадных законов сами.
Но тут я ввожу всех в заблуждение. Формально монада называется по названию монадного типа, но монады IEnumerable нет ни в каких анналах. Есть монада List (The List Monad). Так вот, тройка (IEnumerable<T>, Return, SelectMany) – это реализация монады List в .NET платформе.
Итак, после того, как мы узнали, что такое монада, конструкцией SelectMany все еще можно делать разные удобные вещи, какие мы могли делать до того, как узнали, что оно имеет отношение к монадам. Например, можно связывать коллекции с коллекциями и выпрямлять всё в одну коллекцию. Важно отметить, что в результате монадного связывания мы всегда получаем на выходе монадный тип, к которому можно применять связывание и далее.
Рассмотрим более глубокий пример:
var query =
from country in countries
from city in country.Cities
from street in city.Streets
select streets;Eго можно записать в следующей форме:var query = countries
.SelectMany(country => country.Cities)
.SelectMany(city => city.Streets);Может показаться что эти формы эквивалентны, но это не так. Результаты будут совпадать, но способы их получения разные. Вторая форма записи применяет последовательно SelectMany к результатам, полученным в предыдущих вычислениях. Т.е. сначала берется набор стран, потом SelectMany вычисляет плоскую последовательность всех городов стран, к ней применяется SelectMany, вычисляющий плоскую последовательность улиц всех городов.Монадные вычисления используют другую стратегию. Для каждой страны находятся улицы городов страны, а затем улицы городов склеиваются в единую последовательность. Вот как это может выглядеть:
var query = countries.SelectMany(
country => country.Cities.SelectMany(
city => city.Streets));Или так, если записать в нотации без Extension Methodsvar query = SelectMany(countries, country =>
SelectMany(country.Cities, city =>
city.Streets));Это и есть использование воплощения монады List в C#. (Театральная пауза)
Вы спрашиваете:
-Это и есть та самая монада? Что делает обычный метод SelectMany монадой?Я отвечаю:
- Да, это она самая! Выполнение монадных законов наделяет этот метод особенной магией и позволяет вызывать его, получать результат, а потом к результату применять его снова сквозь типы, обстоятельства, время, вытаскивая нужную нам трансформацию из любых глубин!Наверняка вы пока не разделяете мой восторг, но меня просто прёт!
Монада List, вообще говоря, не самая простая монада из списка стандартных монад. Но вот так получилось, что познакомились мы сперва именно с ней. Тем легче будет перейти к более простым монадам.
Если честно, пытался я постичь более простые монады до понимания сути монады List. Не получалось, т.к. их смысл ускользал от меня. Вам я представлю возможность постичь их смысл через монаду List.
The Maybe Monad
В случае с коллекциями мы уже привыкли к тому, что в каждой коллекции элементов может быть много. Вообразим теперь коллекцию, в которой может быть не более одного элемента. Т.е. либо есть элемент, либо нет ни одного. Третьего не дано. От примера со странами, городами, улицами и домами перейдем к другому примеру:Программа открывает файл, читает из него строку и ищет в базе данных значение, соответствующее этой строке. Если на каком-то этапе происходит ошибка, возвращается null.Нет, не нравится. В файле может быть несколько строк, в базе данных может быть несколько значений… Не наш случай. Да и условие задачи стырено отсюда. Так же не очень интересно складывать 5 и Nothing (как здесь).
Возьмем Смерть Кащея! Это есть игла, которая в яйце, которое в утке, утка на сундуке. Дуб, зайцы, селезни, и т.п. – кыш с пляжа! Нам требуется написать программу, которая сможет достать Смерть Кащея, если она там действительно есть, и не сломается, если чего-то не хватает. Т.е. мы не уверены, есть ли сундук, что в сундуке действительно есть утка. Яйцо в утке тоже не факт, что есть. Ну и т.п. Неожиданности вроде двух яиц внутри утки нас не интересуют по условию задачи.
Можем воспользоваться каскадом вложенных if-ов, либо последовательностью выражений if(…==null) return null. Но мы-то тут с монадами знакомимся, а не с if-ами!
Монада List нам почти подходит. Если у сундука есть коллекция уток, у утки коллекция яиц, у яйца коллекция иголок. Можно записать решение в виде последовательного применения SelectMany:
var query = сундуки
.SelectMany(сундук => сундук.Утки)
.SelectMany(утка => утка.Яйца)
.SelectMany(яйцо => яйцо.Иглы);
var смертьКащеяНайдена = query.Any();Либо в виде монадного связывания:var query = сундуки.SelectMany(сундук =>
сундук.Утки.SelectMany(утка =>
утка.Яйца.SelectMany(яйцо =>
яйцо.Иглы)));
var смертьКащеяНайдена = query.Any();получилось довольно компактно, но вот вместо коллекций уток, яиц и игл хорошо бы воспользоваться чем-то более простым. Нам не нужны здесь коллекции на самом деле. Тип Nullable<T> подошел бы вместо коллекций, не будь у него ограничения на тип параметра (только структуры). Впрочем, если вся наша предметная область описана структурами, то вполне подойдет. Введем класс Maybe<T>, который будет устроен в точности как Nullable<T>, но без ограничений на тип T. Я его прямо скопирую из блога Wes Dyer-а вместе с реализацией метода SelectMany и ToMaybe (это аналог нашей функции Return):
class Maybe<T>
{
public readonly static Maybe<T> Nothing = new Maybe<T>();
public T Value { get; private set; }
public bool HasValue { get; private set; }
Maybe()
{
HasValue = false;
}
public Maybe(T value)
{
Value = value;
HasValue = /*true;*/ (value != null);
}
}
public static Maybe<U> SelectMany<T, U>(
this Maybe<T> m,
Func<T, Maybe<U>> k)
{
if (!m.HasValue)
return Maybe<U>.Nothing;
return k(m.Value);
}
public static Maybe<T> ToMaybe<T>(this T value)
{
return new Maybe<T>(value);
}Я немного модифицировал конструктор типа Maybe, чтобы он мог принимать null-ы и возвращать экземпляр со свойством HasValue равным false (модификация будет работать только с reference типами. Инициализация Maybe Value-типами всегда будет возвращать экземпляр со значением). Тогда выражение примет вид:
var query = сундук.ToMaybe().SelectMany(сундук =>
сундук.Утка.ToMaybe().SelectMany(утка =>
утка.Яйцо.ToMaybe().SelectMany(яйцо =>
яйцо.Игла.ToMaybe())));
var смертьКащеяНайдена = query.HasValue;Знакомьтесь – монада Maybe. Связывает каскад вычислений, каждое из которых может окончиться ничем, тогда последующие вычисления не потребуются. Не уговаривайте меня, что if(сундук.Утка != null) проще чем монада. Я сегодня лишь демонстрирую монаду Maybe, а не склоняю к отказу от if-ов :)
The Identity Monad
Для понимания монады Identity потребуется представить списки с точностью одним обязательным элементом. Можно так же представить тип Maybe с отсутствующим флагом о наличии значения.Так же нам потребуется упростить задачу о Смерти Кащея: теперь в сундуке есть в точности одна утка, в утке есть яйцо, в яйце есть игла. Никаких неожиданностей.
Вводим тип Identity и соответствующие ему методы (снова спасибо Wes Dyer-у):
class Identity<T>
{
public T Value { get; private set; }
public Identity(T value) { this.Value = value; }
}
public static Identity<T> ToIdentity<T>(this T value)
{
return new Identity<T>(value);
}
public static Identity<U> SelectMany<T, U>(this Identity<T> id, Func<T, Identity<U>> k)
{
return k(id.Value);
}Теперь мы можем записать решение с помощью последовательных применений SelectMany: var query = сундук.ToIdentity()
.SelectMany(сундук => сундук.Утка.ToIdentity())
.SelectMany(утка => утка.Яйцо.ToIdentity())
.SelectMany(яйцо => яйцо.Игла.ToIdentity());
var смертьКащея = query.Value;Решение задачи о Смерти Кащея с использованием Identity монады будет выглядеть так: var query =
сундук.ToIdentity().SelectMany(сундук =>
сундук.Утка.ToIdentity().SelectMany(утка =>
утка.Яйцо.ToIdentity().SelectMany(яйцо =>
яйцо.Игла.ToIdentity())));
var смертьКащея = query.Value;Решение такой постановки задачи гораздо проще записать без монады: var смертьКащея = сундук.Утка.Яйцо.Игла;Впрочем, как сказал автор статьи о монадах на rsdn.ru,
Такая монада находит применение с монадными трансформерами, которые в данной статье не рассматриваются. Будем считать, что это чисто иллюстративный простейший пример.В отношении Identity монады мне добавить нечего.
Пристегиваем Query Expression (припудрим сахаром)
Внимательный читатель наверняка обратил внимание, что при том что утка, яйцо и игла имеют кол-во экземпляров не более одного, название метода связывания остается “SelectMany”, будто сущностей может быть больше одной. Вот тут пришла пора вспомнить Query Expressions.В спецификации языка C# можно найти информацию о том, что Query Expressions может быть смаппирован в функцию со следующей сигнатурой:
C<V> SelectMany<T,U,V>(
C<T> source,
Func<T,C<U>> selector,
Func<T,U,V> resultSelector);При внимательном анализе можно заметить, что это функция есть более общая форма известной нам Bind (SelectMany), где к значению типа T и результату работы селектора C<U> применяется еще одна функция, возвращающая некоторое значение V, потом с помощью функции Return (ToMaybe) возвращается монадный тип с параметром V. Именно эта функция SelectMany используется компилятором для трансляции Query Expression выражений.Назначение третьего аргумента выяснить оказалось несложно (покажу чуть позже).
Вот код более навороченной функции SelectMany:
static Maybe<V> SelectMany<T, U, V>(
this Maybe<T> m,
Func<T, Maybe<U>> k,
Func<T, U, V> s)
{
return m.SelectMany(x => k(x).SelectMany(y => s(x, y).ToMaybe()));
}Пока примем его на веру. Теперь можно скомпилировать и выполнить следующий код: static void Main()
{
var m = from x in 1.ToMaybe()
from y in 2.ToMaybe()
from z in 3.ToMaybe()
select x + y + z;
Console.WriteLine(m.HasValue);
}Посмотрев на результат с помощью Reflector-а можно увидеть (отформатировано мной): Console.WriteLine(
1.ToMaybe()
.SelectMany(
x => 2.ToMaybe(),
(x, y) => new { x = x, y = y })
.SelectMany(<>h__TransparentIdentifier0 =>
3.ToMaybe(),
(<>h__TransparentIdentifier0, z) =>
((<>h__TransparentIdentifier0.x + <>h__TransparentIdentifier0.y) + z))
.HasValue);Похоже что компилятор преобразовал исходный код так, как если бы он был написан следующим образом:static void Main()
{
var m = from x in 1.ToMaybe()
from y in 2.ToMaybe()
select new {x, y}
into t
from z in 3.ToMaybe()
select t.x + t.y + z;
Console.WriteLine(m.HasValue);
}И дейсвтительно, если посмотреть Reflector-ом на результат компиляции этого выражения, мы увидимConsole.WriteLine(
1.ToMaybe()
.SelectMany(
x => 2.ToMaybe(),
(x, y) => new { x = x, y = y })
.SelectMany(
t => 3.ToMaybe(),
(t, z) => ((t.x + t.y) + z))
.HasValue);что в точности есть результат предыдущей декомпиляции с точностью до именования идентификатора t.Внимательно сопоставим выражение QueryExpression с декомпилированным выражением:
from x in 1.ToMaybe() было преобразовано в 1.ToMaybe() и подано первым аргументом первого SelectMany метода.
from y in 2.ToMaybe() было преобразовано в 2.ToMaybe() и подано вторым аргументом первого SelectMany метода. Третьим аргументом стало сопоставление паре (x, y) выражения new { x, y }.
Результатом этих действий будет new { x, y }.ToIdintity(), который подается на вход второго метода SelectMany. Так же туда подается 3.ToMaybe() и выражение второго select clause.
Таким образом, трехаргументный SelectMany метод подставляется во все выражения from ? in expr, кроме самого первого. Третьим аргументом этого метода становится выражение в select clause, и если такого нет, то оно синтезируется компилятором искусственно. Это не совсем соответствует монадным связываниям выражений, однако на результате сказываться не должно.
Теперь можно делать выводы о том, что же делает супер версия SelectMany и как она реализована. Приведу вариант реализации без использования синтаксиса Extension Method:
static Maybe<V> SelectMany<T, U, V>(
this Maybe<T> m,
Func<T, Maybe<U>> k,
Func<T, U, V> s)
{
return SelectMany(
m,
x => SelectMany(
k(x),
y => s(x, y).ToMaybe()));
//return m.SelectMany(x => k(x).SelectMany(y => s(x, y).ToMaybe()));
}Внимание! Внешний метод SelectMany (двухаргументный) принимает значение m и лямбда функцию. Если значение m пусто, то внешний метод тут же возвращает Nothing, иначе он подаст m.Value на вход к переданной лямбда-функции и вернет ее результат. В свою очередь лямбда-функция устроена так, что она проверит результат выполнения метода k над первым аргументом. И если он Nothing, вернет Nothing. Иначе вернет результат выполнения метода s над x и y, завернутый в монадный тип Maybe. Итак, в случае наличия значения в m, и наличия значения в результате k(m.Value), выполнится s(m.Value, k(m.Value).Value) и результат обернется в монадный тип Maybe. Точно так же мы могли бы определить сперва большой трехаргументный метод SelectMany, а потом выразить малый двухаргументный через большой. Возможно читателю будет интересно проделать это самостоятельно.
Ну в общем, надеюсь теперь понятно, почему связывающие методы Bind в C# принято называть “SelectMany”. Это связано с Query Expression паттерном, позволяющим записывать монадные преобразования в удобном синтаксисе. В то же время, мы могли бы малые методы SelectMany назвать и Bind и SelectOne и как-нибудь по другому, ничего бы не изменилось.
Заключение
Надеюсь, что с помощью данного поста удалось выяснить- что монады не так страшны, как их название
- что читатели уже знакомы в какой-то мере с монадными вычислениями (в лице монады List, реализованной в LINQ-е)
- что Query Expression связывает с монадами только лишь укороченный синтаксис, который можно пристегнуть к монаде с помощью доопределения более развернутого метода SelectMany (который даже имеет другую форму, нежели монадный Bind).
- что существуют другие монады кроме той, что реализована в LINQ-е, и что их можно использовать в языке C# (правда польза монад Maybe и Identity осталась нераскрыта в данном посте)
Не буду обещать, что расскажу о них в ближайшее время, вместо этого предлагаю заинтересовавшимся шагнуть в мир монад самостоятельно, используя следующие ссылки:
Ссылки
- http://www.rsdn.ru/article/funcprog/monad.xml
- http://blogs.msdn.com/wesdyer/archive/2008/01/11/the-marvels-of-monads.aspx
- http://weblogs.asp.net/podwysocki/archive/2008/10/13/functional-net-linq-or-language-integrated-monads.aspx
- http://blogs.msdn.com/lukeh/archive/2007/08/19/monadic-parser-combinators-using-c-3-0.aspx
- http://www.haskell.org/all_about_monads/html/index.html
