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

[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 }

for (user  ← db.getUser(userId); // обычно это максимум один юзер
     phone ← db.getPhones(userId) // телефонов может быть и несколько (драма, если написано на джаве)
    ) process(user, phone)

В переводе на SQL это выглядело примерно так

select user.name, phone.number from user, phone where user.user.id = phone.userId

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

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

def process (user: User) (phone:Phone) = { val s = user.name + ": " + phone.number; println(s); s }

Теперь если мы вызовем process(user), то результат будет иметь тип Phone => String. Зачем бы нам это было нужно? Ну мы могли бы, например, преобразовать наш цикл в такой:

for (user  ← db.getUser(userId);
     f     = process(user);
     phone ← db.getPhones(userId);
    ) f(phone)

Это можно переписать так:

val fs     = db.getUser(userId).map(process)
val phones = db.getPhones(userId)
for (f ← fs; phone ← phones) f(phone)

Обратите внимание на типы.

val fs:     Set[Phone => String] = db.getUser(userId).map(process)
val phones: Set[Phone]           = db.getPhones(userId)

В цикле for (f ← fs; phone ← phones) f(phone)

Мы применяем множество функций к множеству телефонов, получая множество строк. Это то, что математики любят называть свёрткой, а в скале эта операция называется ap:

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

val fs     = db.getUser(userId).map(process)
val phones = db.getPhones(userId)
val result = fs ap phones

В последней строке мы вызываем метод ap типа Set, потому что у этого типа есть такой метод, а этот метод у него есть, потому что этот тип содержит trait Applicative.

Мы определяли val fs = db.getUser(userId).map(process), но на самом деле мы могли бы выполнить эту операцию с участием того же ap:

val processes = Set(process)
ap(processes, db.getUser(userId))

Разумеется, этот ap надо где-то определить для конкретного функтора. Так как определять его всё равно надо, можно определить прямо в функторе (в Скале для этого есть трюк, называется pimping, но я его пропущу для простоты).

  class Set[A]} {
  ...
  def ap[B](f: F[A => B], a: F[A]): F[B]

Правильнее было бы ввести специальный trait; ниже приведён вполне компилируемый и работающий, хотя и не вполне промышленного качества код:

  trait Functor[T[_]]{
    def map[A,B](f:A=>B)(ta:T[A]):T[B]
  }

  trait Applicative[T[_]] extends Functor[T]{
    def pure[A](a:A):T[A]
    def ap[A,B](tf:T[A=>B])(ta:T[A]):T[B]
  }

  implicit def applicablize[A, B](fs: Set[A=>B]) = new {
    def <*>(as: Set[A]) = (for (f <- fs; a <- as) yield f(a)).toSet
  }

  implicit object AppSet extends Applicative[Set] {
    def pure[A](a: A) = Set(a)
    def ap[A,B](fs:Set[A=>B])(as:Set[A]):Set[B] = (for (f <- fs; a <- as) yield f(a)).toSet
    def map[A,B](f:A=>B)(as:Set[A]) = ap(pure(f))(as)
  }

  val p = AppSet.pure((s:String) => "'" + s + "'")
  val p2 = AppSet.pure((first: String) => (second:String) => first + " " + second)
  val names = Set("Jedi", "Michael Valentine")
  p <*> names
  val lasts = Set("Smith", "Frazer")
  p2 <*> names <*> lasts

Теперь мы можем написать нашу операцию так:

  processes = AppSet.pure(process)
  processes <*> db.getUser(userId)

А вся операция выглядит так:

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

Что здесь происходит? Мы берём функцию process, строим из неё синглтон, т.е. применяем монадическую единицу, а потом сворачиваем её с юзерами и телефонами. В результате получаем множество искомых строк.

Вот и весь фокус, казалось бы.

Мы пока что имели дело с монадой, но использовали не все её способности: единицу, и свёртку, которую мы чудесным образом построили, основываясь на монадном умножении и на функториальности монады (наличие map).

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

(ссылки:
http://ivan-gandhi.livejournal.com/1909155.html
http://scalaz.googlecode.com/svn/continuous/latest/browse.sxr/scalaz/example/ExampleValidation.scala.html
http://www.scala-lang.org/node/4052
http://blog.tmorris.net/monads-do-not-compose/
http://blog.tmorris.net/automated-validation-with-applicatives-and-semigroups-for-sanjiv/
https://gist.github.com/1140466
http://debasishg.blogspot.com/2010/12/monads-applicative-functors-and.html
http://stackoverflow.com/questions/7447591/how-do-i-use-name-as-an-applicative
http://stackoverflow.com/questions/7109571/how-does-scalaz-f-applicative-type-constraint-imply-use-of-implicit-param
http://stackoverflow.com/questions/1992532/monad-trait-in-scala
http://stackoverflow.com/questions/8147031/summing-a-list-of-options-with-applicative-functors
http://groups.google.com/group/scala-language/browse_thread/thread/b7d8ba3f1ed76634
http://lockster.posterous.com/applying-applicative-functors-in-scala