апликативное программирование 6

[juan_gandhi]

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

В предыдущей серии мы познакомились с аппликативным функтором.

Чем эти аппликативные функторы хороши - тем, что композиция двух аппликативных функторов - аппликативный функтор. Вот возьмём

def process (user: User) (phone:Phone) = { val s = user.name + ": " + phone.number; println(s); s }
val result: Set[String] = AppSet.pure(process) <*> db.getUser(userId) <*> db.getPhones(userId)

и представим, что db.getSomething(userId) возвращает не Set[Something], а Future[Set[Something]] - обещание вернуть что-то, когда готово будет. Тогда и результат наш будет иметь форму

val result: Future[Set[String]] = AppFuture.pure(AppSet.pure(process)) <*> db.getUser(userId) <*> db.getPhones(userId)

Тут немножко неуклюже выглядит вызов двух pure AppFuture.pure(AppSet.pure(process)); но на это в скале есть неявные функции. Если мы определим

implicit def singleton[T](t: T) = AppSet.pure(t)
implicit def toFuture[T](t: T) = AppFuture.pure(t)

то можно переписать наш код красивее:

val result = process <*> db.getUser(userId) <*> db.getPhones(userId)

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

Чтобы функтор был аппликативным, мы должны были определить

  def ap[A, B](f: F[A => B], a: F[A]): F[B]

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

  def strength[A, B](F[A], F[B]): F[A × B]

A × B - такого обозначения в Скале нету на самом деле; есть
Pair[A, B], aka Tuple2[A, B] - класс пар; ну мы ж все понимаем, что это декартово произведение и есть, и формально надо было написать

  def strength[A, B](Pair[F[A], F[B]]): F[Pair[A, B]]

Откуда такая эквивалентность?

Если есть strength, то можно определить

  def ap[A, B](ff: F[A => B], fa: F[A]): F[B] = strength(ff, fa).map((f, a) => f(a))

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

Ну и наоборот, если есть аппликативность ap, определим

  def pairing[A, B](a: A): (B => Pair[A, B]) = b => (a, b) // функция такая
  def pairingLifted[A, B](fa: F[A]): (F[B] => F[Pair[A, B]]) = fa map pairing // та же функция, да на F[A]
  def strength[A, B](fa: F[A], fb: F[B]): F[Pair[A, B]] = ap(pairingLifted, fa) // QED

Мы тут, можно сказать, теорему доказали; спасибо akuklev, подсказал.

Вот эта сила, strentgh, традиционно называется монадической силой, если речь идёт о монадах. И в компьютерной науке есть поверие, что всякая монада обладает монадической силой - ну просто мы подымем бинарную операцию в монаду, и всё получится.

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

Comments

[pod-baobabom.livejournal.com]

Я всё жду-жду, когда же пойдут примеры из МакБрайда и Патерсона про силу аппликативного программирования на примерах транспозиции матриц, обхода структур всяких и реактивного программирования. :)

А ещё интересный вопрос -- как завернуть рекурсивно вычисляемое значение в монаду и что от этого произойдёт с эффектом этой монады. Ну то есть в Хаскеле-то есть mdo-notation уже лет 10 как, а вот есть ли это в Scala, я не знаю.

[ivan-gandhi.livejournal.com]

Хм, из МакБрайда и Патерсона. Я как-то в другую сторону заворачивал, но намёк понял. Надо покрыть, конечно.

Про mdo ничего не знаю, придётся ознакомиться. Спасибо.

[pod-baobabom.livejournal.com]

Ну и ещё один вопрос на затравку: как бы выглядела реализация рекурсивно-определённых аппликативных вычислений с эффектами на Scala для аппликативных функторов (Не монад! Передаваемое значение не трогаем!) и насколько сильно бы это отличалось от случая для монад с mdo.

[ivan-gandhi.livejournal.com]

Хороший вопрос, только, в отличие от предыдущего, я его не понял. Ну или если речь о переложении хаскельного кода из макбрайда-патерсона, то я этим вопросом уже озадачился. :)

[pod-baobabom.livejournal.com]

Ну смотри. В случае с рекурсивной монадой, для неё сформулирована аксиома-рекомендация, что при рекурсии значение должно использоваться, а эффект, в который оно обёрнуто -- оставаться неизменным.

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

[ivan-gandhi.livejournal.com]

Я так понимаю, что вопрос стоит об определении монадного умножения для аппликативных функторов. Хороший вопрос.

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

[ivan-gandhi.livejournal.com]

Убедили; эта тема вперёд пойдёт. Не скажу, что знаю ответ, буду разбираться. Спасибо.

[lomeo.livejournal.com]

BTW сейчас mdo deprecated. Сейчас модно do { v <- rec e1(v); e2(v) }

Ну и если в Scala for - это do-нотация, то рекурсивные определения там не поддерживаются. Впрочем, если писать mfix руками, то, конечно, сделать это можно. Но это уже будет не так красиво (мы избавляемся от рекурсивного определения).

[ukh.livejournal.com]

Что-то Вы такое описываете подозрительно похожее на коды для мобильников. Нет, ошибаюсь?

[ivan-gandhi.livejournal.com]

О нет. Это глубокий математический подход, объясняющий, а что это именно мы делаем когда код пишем, и как это делать максимально надёжно и эффективно. Хотя многие тут присутствующие не согласятся - им лень математику учить.

[ukh.livejournal.com]

А, вот так! Понятно. Спасибо.

[lomeo.livejournal.com]

> и представим, что db.getSomething(userId) возвращает не Set[Something], а Future[Set[Something]]

А зачем? Может писать более generic? Пусть это будет

def getSomething[A](userId: Int)(implicit app: Applicative[A])

где A - это нужный аппликативный функтор. Future(Set(process)) вынудит нас использовать аппликативный функтор для Future[Set[_]]. Может в другом месте мы в виде списка захотим получить значения из базы, а в другом в виде Option.

[ivan-gandhi.livejournal.com]

Конечно. Ну я ж тут не оптимальный код пишу, а иллюстрацию.

[lomeo.livejournal.com]

А, ок. Кстати, за strength спасибо, понравилось.

[lomeo.livejournal.com]

Даже, наверное, лучше иметь для этого

implicit def toConcreteApp[T](t: T): ConcreteApp[T] = ...

тогда вообще не придётся мучиться. Кстати, твой пример с implicit работать, к сожалению, не будет. Scala типы смотрит слева направо. Вот если бы сначала встретился db.getUser и по нему стало понятно, что мы работаем с Future-Set, то process бы обернулся implicitly, а в представленной записи будет ошибка компиляции. Не Haskell :-(

[sassa-nf.livejournal.com]

я второй раз не понял, почему ap между process и db.getUser(userId) Про infix помницца только о методах написано, так что, не совсем понятно, по какому правилу здесь ap и process переставятся местами.

[ivan-gandhi.livejournal.com]

Спасибо огромное! Пофиксил в разных местах.

[sassa-nf.livejournal.com]

а ещё об эквивалентности def strength[A,B](p:Pair[A,F[B]]):F[Pair[A,B]] и def strength[A, B](p:Pair[F[A], F[B]]): F[Pair[A, B]]

а то из второго следует F(eval_X)=eval_Y, а из первого - не очевидно.

[sassa-nf.livejournal.com]

т.е. чтобы из одного другое получить, нужно, чтобы помимо силы ещё и косила была. А это разве всегда?

[sassa-nf.livejournal.com]

а, все продукты A и B имеют изоморфизмы друг в друга, и в CCC есть и AxB, и BxA, а потому ко-сила существует для всех монад, у кого есть сила, ибо с помощью изоморфизма можно "менять местами" A и B.

тьфу, но и это ещё не всё. Это же годится для тех категорий, где tensor product is a cartesian product.

[ivan-gandhi.livejournal.com]

Я о втором; это тензорная сила (вроде бы). Первое ж вообще вроде не участвует в тексте.

[sassa-nf.livejournal.com]

да, спасибо. Я просто по случаю решил расспросить. Там ранее обсуждалась сила в другом виде, а потом в другом посте упоминалось, что есть между ними простая зависимость.

На википедии в разделе, где сила в втором виде, речь идёт о commutative strong monads. Вот я и думал, что раз дополнительно упоминается "commutative", то силу в таком виде не у всех монад можно обнаружить.

Теперь почитал, выходит, что в CCC категории тензорное произведение можно всегда задать через декартово, ибо терминальный объект в A=1xA=Ax1 ведёт себя совершенно как единица тензорного произведения.

[sassa-nf.livejournal.com]

а, стоп, это было два вопроса.

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

2. Почему говорят о commutative strong monads, когда задают силу во втором виде. Точное условие этого я ещё не до конца понял, но хоть стало понятно, каким образом второе из первого вытекает. Поскольку в CCC есть декартовы произведения всех объектов, а между всеми произведениями одинаковых объектов (например, AxB и BxA) есть изоморфизмы, то в CCC всегда определен морфизм flip.

[ivan-gandhi.livejournal.com]

По-моему, первый пункт не вопрос, а ответ. Да и второй тоже. У нас же декартово везде... На самом деле, когда я параметризую запрос с помощью userId, то имеет место расслоенное произведение (pullback), но это всё равно декартово в нужной категории.

[sassa-nf.livejournal.com]

ага, это сейчас ответ, когда покопал :) а сначала был вопрос.

А можно для иллюстрации диаграмку, где тут пулбэк получается?

[ivan-gandhi.livejournal.com]

Like this?