апликативное программирование 3. немножко про монады

1, 2, 3, 4, 5, 6, 7, 8, 9, 10


В предыдущей части я это слово упоминал, и даже определил, правда, не полностью.

Разные люди определяют монаду по-разному; главная проблема в том, что специалисты по компьютерным наукам слишком спешат со своими альтернативными определениями, не дочитав научное определение до конца. Это происходит сплошь и рядом; такое ощущение иной раз, что мы имеет дело с бытовой алхимией а не с бытовой химией. Ну да ладно; я не вижу никакого интереса в изучении альтернативной, "компьютерной" математики.

Так что я переложу для нашего контекста настоящее определение. Да, нотация будет скальная; надеюсь, всё будет понятно.

функтор

Возьмём параметризованный тип Т[X] (с одним параметром X); для каждого типа X мы получаем типа T[X]. Это преобразование типов можно называть функтором при следующих условиях:

- для всякой функции f: X → Y определена функция T(f): T[X] → T[Y]. Эта операция, превращение f в T(f) обычно называется map (в хаскеле, в скале, в functional java) или transform (c++, гугловская джавная библиотека Guava).

- эта трансформация (определённая в предыдущем пункте) сохраняет тождественную функцию - т.е. если взять identity[X]: X → X, то T(identity[X]) будет равна identity[T[X]]. (Что такое равенство двух функций, я тут лучше не буду обсуждать.)

- эта трансформация сохраняет композицию двух функций - т.е. если возьмём f: X → Y и g: Y → Z, и функцию h = f.andThen(g): X → Z, то T(h) = T(f).andThen(T(g)): T[X] → T[Z].

Итак, функтор. Одни параметризованные типы являются функторами, другие нет.

Например, Class[T] не является функтором - тот факт, что имеется функция f: X → Y не даёт нам никакой функции из Class[X] в Class[Y].

Другое дело скальный List[T] - по каждому f: X → Y строится список List[X].map(f) - т.е. мы имеем ту самую трансформацию f ↦ List[X].map(f).

(Примечание для тех, кто не в курсе. Стрелка ↦ употребляется для обозначения того факта, что каждому значению слева сопоставляется значение справа. Например, функция "синус" даёт следующее сопоставление: x ↦ sin(x) - каждому x сопоставляем его синус. В случае, когда мы имеет дело с множествами, совокупность всех таких сопоставлений и задаёт функцию.)

монада

Монада - это функтор, снабженный двумя семействами функций - я их уже упоминал в предыдущей части.

А именно:

единица

u[X]: X → T[X], она иногда называется pure, кой-где называют return.

Для списков это функция, по значению строящая одноэлементный список. Для других монад... вернёмся к этому позже.

Этого мало, что для каждого типа X каким-то произвольным образом задали функцию; надо, чтобы она хорошо вела себя по отношению к map.

То есть, если есть f: X → Y, то мы же можем из X в T[Y] попасть двумя путями, один через Y, , а другой через T[X], . Так вот, эти две функции должны быть равны. Категорщики это изображают в виде коммутативного квадрата:

умножение

m[X]: T[T[X]] → T[X]. Ещё известно под именем join и flatten.

Последний термин, разглаживание, иллюстрируется тем, как это делается на списках: берём список списков и вытягиваем его в линейный список.

Умножение тоже должно соблюдать условие естественности, аналогично u[X]; не буду выписывать.

законы монады

1. Умножение должно быть ассоциативно. T[T[T[X]]] → T[T[X]] → T[X] можно выполнить двумя способами; результат должен совпадать.

Для списков - список списков списков можно плющить двумя способами - сначала снаружи, потом сплющиваем результат, или же сплющиваем каждый элемент (список списков), а потом уже результат.

2. Единица должна быть единицей относительно умножения, справа и слева.
T[X] → T[T[X]] → T[X] - можно построить две таких функции, и они обе тождественные.

На пальцах (на списках) - берём список, строим из него синглтон с одним списком внутри, сплющиваем - получили исходный список. Берём список, превращаем каждый элемент в синглтон (получили список списков), сплющиваем - получили исходный список.

(Тут может возникнуть вопрос, в каком смысле мы понимаем равенство. Это вопрос скользкий; давайте предположим, что у нас внутре jvm, и у каждого типа есть разумно определённое равенство, которое на самом деле, по научному, не равенство, а изоморфизм.)

примеры

В принципе, примеров полно. List, State, Maybe (Option), Set (ковариантая версия), Environment, Read, Continuation... В мои планы не входит разбираться с ними со всеми, это отдельная тема. Я пока что возьму четыре, List, Option, Set, которые в джаве и в скале вполне формализованы, а также exception, тайная монада, из тех, про которые Эрик Мейер говорил, что во всяком языке прячется неявная монада.

List

Единица - это синглтон, умножение - сплющивание. List - самая любимая народом монада, на ней, как на белой мыши, можно ставить любые опыты.

Option

Единица - это функция x ↦ Some(x), умножение - сплющивание (Some(Some(x)) ↦ Some(x), остальное в None).

Set

С этой монадой легко запутаться, т.к. есть два функтора Set, визуально не отличимые. Я сейчас имею в виду вот какой:

если задана f: X → Y, то Set(f) представляет собой следующую функцию:
(s: Set[X]) ↦ Imagef(s) = {(y:Y)| s.contains(f-1(y))}.
По-русски, каждому множеству s элементов типа X сопоставляется его образ под действием f.

Единица представляет собой построение синглтона, а умножение задаётся на множестве множеств, Set[Set[T]] и представляет собой объединение.
(ssx: Set[Set[T]]) ↦ ∪{sx | ssx.contains(sx)}.

исключение

Чтобы о нём рассуждать как о монаде, нужно или несколько выйти за пределы языка, или моделировать его, добавляя уровень косвенности - приём, который, как известно, решает любую проблему программирования взятую отдельно (общего конструктивного решения всех проблем, к сожалению, не существует... в рамках теории, конечно).

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

trait Exceptional[T] { def apply(); }
case class Ok[T](value: T)       extends Exceptional[T] { def apply = value }
case class Oops[T](x: Exception) extends Exceptional[T] { def apply = throw x }

Из этого дела легко построить монаду, практически то же самое, что и Option[T]; умножение можно задать примерно так:

def m[T](eet: Exceptional[Exceptional[T]]): Exceptional[T] = eet match {
  case Ok(et) => et // just extract the content which is an Exceptional anyway 
  case ex     => ex // it's the same exception

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

Вопросы ловли исключений и как тут быть с монадой выходят за пределы данного дискурса.

На сегодня всё; дальше я собираюсь рассказать, что, собственно, за проблема если у нас всё кругом монады, как эти вопросы решают в некоторых языках, почему эти вопросы неразрешимы в общем случае, и как нам быть.

С другой стороны, монаду можно вообще не признавать - считать землю плоской, вселенную однородной и изотропной, пространство евклидовым, вакуум непробиваемым.

kerning again

(10x art_of_arts)

a sin a day...

will keep Jesus Christ away

Буду публиковать грехи из списка женских грехов (мужского списка не видел, буду благодарен)

Без нужды отдыхала.

creation v2