Легкая прогулка от функтора через монаду к стрелке

Давайте совершим прогулку по цепочке Pointed, Functor, Applicative Functor, Monad, Category, Arrow, в процессе которой я попытаюсь показать что все это придумано не для того что бы взорвать мозг, а для решения вполне реальных проблем, притом существующих не только в haskell. Большая часть кода написана на C#, но думаю и без его знания можно будет понять что к чему.

Примеры

Хотя в примерах используются примитивные операции над int, при желании, в место них можно придумать что нибудь более жизненное, например в аппликативном функторе, можно рассмотреть такой вариант

Maybe<int> userId = UserService.GetUserId(email)
Maybe<int> productId = ProductService.GetProductId(productCode)
int discount = DiscountService.GetDiscount(userId.Value, productId.Value)

Введение

Рассмотрим один из распространённых сценариев, когда функция может не вернуть результат, и представим ответ такой функции в виде класса Maybe, хотя в подавляющем большинстве языков данный подход не используется, но по сути это тот же null только более цивилизованный.

	public class Maybe<T> {
		public static readonly Maybe<T> Nothing = new Maybe<T>();
		public T Value { get; private set; }
		public bool HasValue { get; private set; }

		private Maybe() { }

		public Maybe(T value) {
			Value = value;
			HasValue = true;
		}

		public override string ToString() {
			if (HasValue)
				return Value.ToString();
			return "Nothing";
		}
	}

Пример

Maybe<User> GetUserById(int id){...}

Что есть класс Maybe<A>? Можно считать его функцией над типом, которая все обычные типы A переводит в специализированные типы Maybe<A>, int -> Maybe<int>, будем называть их уровнями, а преобразование — переходом между ними.

Pointed

Проблема номер один: нам необходима функция которая позволит сделать переход A -> Maybe<A>, напишем ее.

	static class Pointed {
		public static Maybe<A> Pure<A>(this A value) {
			return new Maybe<A>(value);
		}
	}

Для тех кто не знаком с C#, ключевое слово this позволяет использовать функцию через точку после объекта

Пример

	void Pointed() {
		int x = 1;
		Maybe<int> y = x.Pure();
	}

Теперь мы можем все что угодно поднять на уровень Maybe.

Функтор

Хорошо, поднять мы подняли, но у нас осталось куча функций которая работает для предыдущего уровня, то есть все функции вида A → B, и просто так мы их уже использовать не можем. Что же делать? Очевидно, можно каждый раз проверять есть ли в Maybe что либо, и если есть, применять функцию к тому что в нем содержится, если нет, возвращать Nothing, собственно тот сценарий который используется в случае проверки на null. Что бы придерживаться DRYйя поместим эту логику в отдельную функцию.

	static class Functor {
		public static Maybe<B> Map<A,B>(this Maybe<A> maybe, Func<A,B> f) {
			if(maybe.HasValue) return f(maybe.Value).Pure();
			return Maybe<B>.Nothing;
		}
	}

Пример

	void Functor() {
		Func<int, int> inc = y => y + 1;//обычная функция int -> int
		var x = 1.Pure();//получаем переменную на уровне Maybe
		var r = x.Map(inc); //применяем обычную функцию к переменной на новом уровне, r == Some(2)
	}

Таким образом мы подружили старые функции с новым уровнем.

Аппликативный функтор

Функции одной переменной нам покорилась, что делать с функциями принимающих несколько параметров (A,B) → C? Очевидно map нам тут особо не поможет. Решение есть, но для начало вспомним что такое каррирование — это преобразование функции таким образом что бы ее возможно было частично применить и получить на выходе новую функцию. add(x,y) = x + y; inc = add(1); inc(10) == 11;
Напишем вспомогательную функцию для перевода Func к такому виду.

	static class CurryFunc {
		public static Func<T1,Func<T2,R>> Curry<T1,T2,R>(this Func<T1,T2,R> f) {
			return x => y => f(x, y);
		}
	}

Пример

	void Curry() {
		Func<int,int, int> add = (y,z) => y + z;
		var inc = add.Curry()(1);
		var r = inc(1); // r == 2
	}

И напишем метод apply который поможет решить нашу первоначальную проблему.

	static class Applicative {
		public static Maybe<B> Apply<A,B>(this Maybe<Func<A,B>> f, Maybe<A> maybe) {
			if(f.HasValue) return maybe.Map(f.Value); // если функция есть, значит применяем ее с помощью Map
			return Maybe<B>.Nothing;
		}
	}

Пример

	void Applicative() {
		Func<int, int, int> addF = (y,z) => y + z;
		var add = addF.Curry();
		var x1 = 1.Pure();
		var x2 = 2.Pure();
		var r = add.Pure().Apply(x1).Apply(x2); // Скаррировав функцию и подняв до уровня Maybe мы можем ее применить,  r == Some(3)
		Func<int,int,int> f = DiscountService.GetDiscount;
		var discount = f.Curry().Pure().Apply(userId).Apply(productId); //Пример из самого начала
	}

Подход работает для любого количества переменный, достаточно иметь соответствующую функцию curry.

Func<int, int, int, int, int> addF = (a,b,c,d) => a + b + c + d;
addF.Curry().Apply(x1).Apply(x2).Apply(x3).Apply(x4);

Монада

С обычными функциями окончательно разобрались, но раз у нас есть два уровня, то значит возможны и функции вида A → Maybe<B> например тот самый GetUserById :: int -> Maybe<User>
Решить с помощью map не выйдет. так как в результате получим Maybe<Maybe<B>>, поэтому нам нужна еще одна функция

	static class Monad {
		public static Maybe<B> Bind<A,B>(this Maybe<A> maybe, Func<A,Maybe<B>> f) {
			if(maybe.HasValue) return f(maybe.Value);
			return Maybe<B>.Nothing;
		}
	}

Пример

	void Monad() {
		Func<int, Maybe<int>> solve = y => y == 0 ? Maybe<int>.Nothing : (y + 1).Pure();
		var x = 1.Pure();
		var y = 0.Pure();
		var r1 = x.Bind(solve); // r1 == Some(2)
		var r2 = y.Bind(solve); // r2 == Nothing
	}

Итого, мы решили практически все проблемы которые касаются применения функций, возникшие при создании Maybe.

Категория

Давайте перейдем к вопросу композиционного стиля программирования. Посмотрим какие здесь нам ставить проблемы Maybe и как их можно решить.
Что такое композиционный стиль? Подход когда мы вместо того что бы применять функции одна за другой к результату вычисления, объединяем их в некое подобие конвейера который образует в свою очередь новую функцию, например

f = length . filter (>3) . map (+1) . skip 3  

(.) оператор композиции в хаскеле.
f — функцию пропускает первые три элемента, прибавляет 1 ко всем остальным, фильтрует все что больше трех и возвращает длину полученного списка.
Стиль отличается удобством и наглядность, поэтому достаточно популярен в хаскеле.

Полагаю у вас в подсознии уже начал мелькать образ теории категорий, и это не с проста. Давайте вспомним о чем там идет речь. У нас есть некий класс объектов, для каждой пары из которого задано множество морфизмов. Эти объекты с ихними морфизмами и являются категорией. Для простоты можно представить как направленный граф, где объекты это узлы, а морфизмы это ребра. Так вот для морфизмов как раз и определено понятие композиции, f: A → B, g:B → C получаем f compose g: A → C. Можно определить категорию для языка программирования, где объекты это простые типы, а морфизмы это функции.

Вернемся к композиционному стилю. У обычных функций с ним нет никаких проблем.

	static class Category {
		public static Func<A,C> Compose<A,B,C>(this Func<B,C>f1, Func<A,B> f2) {
			return x => f1(f2(x));
		}
	}

Пример

	void Category() {
		Func<int, int> f1 = y => y + 1;
		Func<int, int> f2 = y => y * 2;
		var fr = f2.Compose(f1);
		var r = fr(1);// r == 4
	}

Однако у функций вида A → Maybe<B>, B → Maybe<C> проблема есть и заключается она в том что выход одной не состыкуется с входом другой.

Так как у нас сейчас пойдет много сигнатур вида A → Maybe<B> давайте напишем для них обертку. Можно и без нее, но с ней как то по нагляднее. Категория Клейсли — категория где морфизмы имеют вид A → M<B>

	class Kleisli<A,B> {
		public Func<A,Maybe<B>> Func { get; set; }
		public Kleisli(Func<A,Maybe<B>> f) {
			Func = f;
		}
	}

Напишем функцию для их композиции.

static class Category {
		public static Kleisli<A,B> ToKleisli<A,B>(this Func<A,Maybe<B>> f) {
			return new Kleisli<A, B>(f);
		}

		public static Kleisli<A,C> Compose<A,B,C>(this Kleisli<B,C> f1, 
			Kleisli<A,B> f2) {
			return ToKleisli<A,C>(x => f2.Func(x).Bind(f1.Func));
		}
	}

Пример

	void Category2() {
		Func<int, Maybe<int>> f1 = y => (y + 1).Pure();
		Func<int, Maybe<int>> f2 = y => (y * 2).Pure();
		var fr = f2.ToKleisli().Compose(f1.ToKleisli());
		var r = fr.Func(1); //r == Some(4)
	}

Если не использовать оберток, запись была бы точно такое же как и у обычных функций f2.Compose(f1)
Теперь мы можем создавать композиции из Клейсли морфизмов.

Стрелка

Вот мы и подошли к последней проблеме. У нас есть функции двух видом А -> B, B -> Maybe<C> и законное желание соединять их между собой. При текущем раскладе это у нас не получится, но как всегда можно написать функцию которая решит все наши проблемы

	static class Arrow {
		public static Kleisli<A,B> Arr<A,B>(this Func<A,B> f) {
			return Category.ToKleisli<A,B>(x => f(x).Pure());// Преобразуем обычную функцию в Клейсли
		}
	}

Пример

	void Arrow() {
		Func<int, int> f1 = y => y + 1;
		Func<int, int> f2 = y => y * 10;

		Func<int, Maybe<int>> fm1 = y => (y * 2).Pure();
		Func<int, Maybe<int>> fm2 = y => (y - 5).Pure();
		var fa1 = f1.Arr();
		var fa2 = f2.Arr();
		var fk1 = fm1.ToKleisli();
		var fk2 = fm2.ToKleisli();
		var fr = fk2.Compose(fa1).Compose(fk1).Compose(fa2);
		var r1 = fr.Func(2); // r1 == Some(36)
		// опять же без обертки можно было бы написать var r1 = f2.Compose(f1.Arr()).Compose(f1).Compose(f2.Arr())(2)
	}

Итого: мы можем комбинировать функции обоих видом, как нам заблагорассудится.

У стрелок еще есть много интересных функций, с помощью которых можно виртуозно жонглировать конвейерами практически любой сложности. Например, как так compose по сути последовательное вычисление, то можно предположить что есть и параллельное: (&&&) — распаралеливает конвейер, (***) — производить параллельные вычисления и пр. Но пожалуй на этом мы остановимся.

Заключение

Надеюсь я смог передать некую красоту и логичность всех вышеописанных конструкций, и возможно у вас возникнет вопрос, почему же такая иерархия практически ни в каких языках не встречается. Ответ скорее всего в том что, для нормальной реализовать нужна система типов сложнее чем в том же C#. Например если мы заходим написать все тоже для списков, которые являются точно таким же переходом между уровнями A -> List<A>, то нам придется продублировать ~90% кода, так как возможности для обобщения практически никакой нет. Для примера можно посмотреть как это все может выглядеть на хаскеле, где за счет типов классов и полиморфизма высшего порядка существенная часть абстракций выделена, и вместо того что бы работать с Maybe все манипуляции происходят над обобщенным типом M<A> где M может быть любым типом с одним параметром Maybe<A> List<A> и пр.

Для желающих углубиться в затронутую тему, рекомендую учебник http://anton-k.github.com/ru-haskell-book/book/toc.html, в нем уделено внимание как практической составляющей хаскеля, так и теоретическим основаниям, плюс это возможно единственных учебник(или по крайней мере один из не многих) на русском где описывается теория категорий в контексте программирования.

Код на haskell

import Prelude hiding (Functor,map,Monad)

class Pointed f where
	pure :: a -> f a

instance Pointed Maybe where
	pure = Just

class Functor f where
	map :: (a -> b) -> f a -> f b

instance Functor Maybe where  
	map f (Just x) = Just (f x)  
	map f Nothing = Nothing  

class (Functor f, Pointed f) => Applicative f where
	apply :: f (a -> b) -> f a -> f b

instance Applicative Maybe where  
	apply Nothing  _ = Nothing  
	apply (Just f) something = map f something  

class Applicative f => Monad f where
	bind :: f a -> (a -> f b) -> f b

instance Monad Maybe  where
	bind (Just x)  k      = k x
	bind Nothing   _      = Nothing

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }

class Category cat where
	compose :: cat b c -> cat a b -> cat a c

instance Category (->) where
	compose f g = x -> f (g x) 

instance Monad m => Category (Kleisli m) where
	compose (Kleisli f) (Kleisli g) = Kleisli (b -> bind (g b) f)

class Category a => Arrow a where
	arr :: (b -> c) -> a b c

instance Arrow (->) where
	arr f = f

instance Monad m => Arrow (Kleisli m) where
	arr f = Kleisli (compose pure f)

Автор: dotneter