juan_gandhi: (Default)
As promised (to myself), started writing the "three myphs of FP".

https://vpatryshev.wordpress.com/2017/01/07/three-popular-fp-myths/
 - part 1, "not every monad is strong" 
juan_gandhi: (VP)
http://community.haskell.org/~simonmar/papers/haxl-icfp14.pdf

Или у меня синдром Даннинга-Крюгера, или я не нашел ничего, чего бы не было у Патерсона и МакБрайда, а также поразительно похожие куски на слайды моего рассказа на Codecamp в 2012-го году. Хотя, конечно, у дураков и великих умов мысли сходятся; да и у меня там не было ничего такого, что бы не написали уже Патерсон с МакБрайдом.

Или я чего-то не понял.

Но у меня в парсерах нынче подобного кода пруд пруди.

  for {(name, sDob, membernumber, claimnumber) <-
        Result.zip(props @ Name, props @ Dob, props @ MemberId, props @ ClaimNr)
       dob <- parseDob(sDob)
       stuff <- buildStuff(name, dob, membernumber, claimnumber)
      } yield stuff
juan_gandhi: (VP)
Extracting PDF from Mozilla Browser - and Doing it Nicely

That's a detailed account of the thing I already posted a couple of days ago. And what I'm enjoying here is Functional Programming. I don't know why Stroustrup does not know that it works. Worked for me. :p
juan_gandhi: (Default)
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

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

Пример. Моноид и Накопление Ошибок


Read more... )
juan_gandhi: (Default)
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

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

Пример. Traversable



Когда у нас есть аппликативный функтор, у нас имеется что-то вроде моноида: есть относительный синглтон (не буду вдаваться в подробности), pure, и есть бинарная операция <*>; с помощью этих двух операций мы можем устраивать свёртку, скажем, списка... ну или дерева, если есть такая возможность, распараллелить, как в map/reduce. trait Traversable как раз обобщает список и дерево - по нему можно итерировать аппликативный функтор.

А именно,
// T будет траверсабельным, если определены:
trait Traversable[T[_]] {
  // для аппликативного функтора app и функции f обход структуры as
  def traverse[A, B, F[_]](app: Applicative[F])(f: A => F[B])(as: T[A]): F[T[B]]
  // и для, скажем, дерева аппликативов можно построить один аппликатив с деревом внутри
  def dist[B, F[_]](app: Applicative[F]) = traverse[F[B], B, F](app)(identity[F[B]]) _
}


Легко определить траверсабельность для списка:
implicit object TraversableList extends Traversable[List] {
  def cons[A](a: A)(as: List[A]): List[A] = a :: as

  def traverse[A, B, F[_]](app: Applicative[F])(f: A => F[B])(al: List[A]): F[List[B]] = {
    al match {
      case Nil => app.pure(List[B]())
      case head :: tail => app.applicable(app.lift(cons[B] _) <@> f(head)) <*> traverse[A, B, F](app)(f)(tail)
    }
  }
}


Тут как бы всё очевидно - если список пустой, то применяем pure, а иначе сканируем весь список, применяя последовательно <*>.

Аналогично поступим и с деревом, только сначала надо как следует определить дерево.

trait Tree[T]
case class Leaf[T](t: T) extends Tree[T]
def leaf[T](t: T): Tree[T] = Leaf(t)
case class Node[T](left: Tree[T], right: Tree[T]) extends Tree[T]
def node[T](left: Tree[T])(right: Tree[T]): Tree[T] = Node(left, right)


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

Вот как определяется траверс на таких деревьях:

implicit object TraversableTree extends Traversable[Tree] {

  def traverse[A, B, F[_]](app: Applicative[F])(f: A => F[B])(at: Tree[A]): F[Tree[B]] = at match {

    case Leaf(a) => app.lift(leaf[B]) <@> f(a)
    case Node(left, right) => {
      implicit def applicable[A, B](tf: F[A => B]) = app.applicable(tf)

      val traverse1: (Tree[A]) => F[Tree[B]] = traverse(app)(f)

      app.pure(node[B] _) <*> traverse1(left) <*> traverse1(right)
    }
  }
}


Обычное дело в Скале - пришлось ввести промежуточную переменную, traverse1, а то Скала в типах запутается. И так всё сложно.

Надо заметить, что не всякий функтор траверсабелен - например, функтор Env, попробуйте-ка его траверсировать с помощью Maybe - это было бы равносильно получению тотальной функции из частичной. Good luck.

Ну а теперь примеры траверса.

Список:
import TraversableList._

val distributor = dist[String, Set](AppSet)
val setOfLists = distributor(List(Set("a", "b"), Set("x", "y")))
setOfLists must_== Set(List("a", "x"), List("a", "y"), List("b", "x"), List("b", "y"))


Дерево:
import TraversableTree._

val distributor = dist[String, List](AppList)
val treeOfLists:Tree[List[String]] = Node(Leaf(List("a", "b")), Node(Leaf(List("x", "y", "z")), Leaf(List("1"))))
val listOfTrees = distributor(treeOfLists)
def tree(s: String) = Node(Leaf("" + s(0)), Node(Leaf("" + s(1)), Leaf("" + s(2))))
listOfTrees must_== List(tree("ax1"), tree("ay1"), tree("az1"), tree("bx1"), tree("by1"), tree("bz1"))


В следующей части - моноиды, и траверс с моноидами.
juan_gandhi: (Default)
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

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

Пример аппликативного функтора: Вычислитель Выражений (монада Env)



В этом примере мы сможем вычислять значения выражений с переменными. Откуда берут значения переменные? Из окружающей среды;
эту среду зададим в виде Map[String, Int] - имена переменных будут строками, а значения целыми. Не убавляя общности.

    type Env = Map[String, Int] // хватило бы String=>Int, но для вящей демонстративности...

    type Environmental[X] = Env => X

    trait EnvFunctor extends Functor[Environmental] {
      override def f1[A, B](f: A => B) = (aa: Environmental[A]) => aa andThen f
    }


Здесь всё понятно, наверное. Теперь определим операции; трёх достаточно: выборка по имени, константа и сложение.

        val fetch = (varName: String) => (env: Env) => env(varName)
        val const = (value: Int) => (env: Env) => value
        val add = (i: Int) => (j: Int) => i + j


Я их тут нарочно определил как константы типа функция.
fetch - это константа (типа функция; можете считать референсом, как в Си); fetch("x") - результат
применения указанной функции к строке "x", т.е. функция, которая берёт Env и извлекает оттуда
значение по ключу "x"; fetch("x")(Map("a" -> 42, "x" -> "77", "y" -> 2012)) возвратит 77.

Предположив, что мы уже определили аппликативность (т.е. pure и <*>, напишем, как должна выглядеть
семантика наших выражений.

        trait Expr {
          def eval: Env => Int
        }

        case class Var(name: String) extends Expr {
          override def eval = fetch(name)
        }

        case class Val(i: Int) extends Expr {
          override def eval = const(i)
        }

        case class Add(p: Expr, q: Expr) extends Expr {
          override def eval =  pure(add) <*> p.eval <*> q.eval
        }


Для Var вычисление состоит в выборке, для Val вычисление состоит в возврате константы, а для сложения
нам как раз и нужна аппликативность. Мы не можем взять да пойти и сложить "значения" подвыражений - это не числа, это
функции, заданные на среде (Env); в Си пойнтеры складывать можно, а в Скале нельзя).

Ну и теперь надо поломать голову, как же определить аппликативность.

Начнём с комбинаторов (кто в армии служил лисп изучал, тот знает).

    implicit def K[A](a: A) = (env: Env) => a

    implicit def ski[Env, A, B](fe: Env => A => B) = new {
      val S = (ae: Env => A) => (env: Env) => fe(env)(ae(env))
    }


Здесь мы пишем implicit, чтобы в нужном контексте функция типа Env => A => B, превращалась в нечто, что способно применять комбинаторы.
Канонически комбинаторов три (S,K,I), но нам хватит двух, похоже.
Комбинатор K берёт значение и возвращает постоянную функцию на Env. а комбинатор S применяет функцию к значению.
В нашем же случае мы берём функцию, зависящую от среды и применяем к значению, зависящему от среды - получается другое значение, зависящее от среды.

Сейчас увидим, какая польза от комбинаторов.

    trait AppEnv extends EnvFunctor {
      def pure[A](a: A): Environmental[A] = K(a)

      implicit def applicable[A, B](fe: Environmental[A => B]) = new Applicable[A, B, Environmental] {
        def <*>(fa: Environmental[A]) = fe S fa // aka S(f, a)
      }
    }


Наши обе аппликативных операции выражаются через комбинаторы.
Тот факт, что функция S применяется инфиксно, формально никакого значения не имеет, но эстетически приятно.
      
object Expressions extends AppEnv {

  // эта функция выбирает значение переменной из среды
  val fetch = (varName: String) => (env: Env) => env(varName)
  // константа, не зависит от среды
  val const = (value: Int) => (env: Env) => value
  // сложение двух чисел
  val add = (i: Int) => (j: Int) => i + j

  // абстракция выражения
  trait Expr {
    def eval: Env => Int
  }

  // выражение, состоящее из переменной
  case class Var(name: String) extends Expr {
    override def eval = fetch(name)
  }

  // выражение, состоящее из константы
  case class Val(i: Int) extends Expr {
    override def eval = const(i)
  }

  // выражение, состоящее из суммы двух выражений
  case class Add(p: Expr, q: Expr) extends Expr {
    override def eval =  pure(add) <*> p.eval <*> q.eval
  }

  // пример выражения - это функция, её значение зависит от среды
  val expr = Add(Var("one"), Add(Var("three"), Val(11))).eval

  // а вот теперь мы её вычислим на среде
  expr (Map("one" -> 1, "two" -> 2, "three" -> 3)) must_== 15

}
juan_gandhi: (Default)
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

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

1. Детали


В предыдущих частях мы с изумлением видели, как красиво какой-нибудь список или Maybe, как брюки, превращаются в функтор, в монаду, в аппликативный функтор... причём, List чудесным образом мог превращаться сразу в два различных аппликативных функтора, первый обычный (когда сшивая два списка, получаем все возможные пары), а второй странный, когда сшиваем два списка вдоль, как замок молнию; для различения этот второй список, был назван ZipList - хотя он так-то, как параметризованный класс, ну ничем не отличается.
Дело в следующем. Нам надо бы расстаться с иллюзией, что как только мы имеем какой-нибудь параметризованный класс, так сразу у нас тут функтор. В общем случае это не так. Но в языках программирования мы имеем какую-то особую категорию, и т.наз. "Theorems for Free" обеспечивают нам функциональность, как только мы задали параметрический класс. То есть, таки достаточно задать отображение на типах.

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

Но сначала давайте вернёмся и дадим формальные определения (на Скале).

2.Опять Функтор


2.1. Определение


trait Functor[T[_]] { self =>
  // mapping on objects of a category
  type f0[_] = T[_]

  // mapping on arrows of a category
  def f1[A, B](f: A => B): T[A] => T[B]

  // builds a composition of two functors
  def andThen[U[_]](u: Functor[U]) = new Functor[({type UT[X] = U[T[X]]})#UT] {
    def f1[A, B](f: A => B): (U[T[A]]) => U[T[B]] = u.f1(self.f1(f))
  }
}


Это функтор; в частности, композиция двух функторов - тоже функтор.

2.2. Примеры


  /**
   * Functorial features of List type
   */
  trait ListFunctor extends Functor[List] {
    override def f1[A, B](f: A => B) = (aa: List[A]) =>  aa map f
  }

  /**
   * Functorial features of Seq type
   */
  trait SeqFunctor extends Functor[Seq] {
    override def f1[A, B](f: A => B) = (aa: Seq[A]) => aa map f
  }

  /**
   * Functorial features of Set type (covariant version)
   */
  trait SetFunctor extends Functor[Set] {
    override def f1[A, B](f: A => B) = (sa: Set[A]) => sa map f
  }

  /**
   * Functorial features of Either[X,Y], for the second parameter
   */
  trait RightEitherFunctor[L] extends Functor[({type Maybe[A] = Either[L, A]})#Maybe] {
    def f1[A, B](f: A => B): Either[L, A] => Either[L, B] = _.right.map(f)
  }


Напомню, что Seq в Скале примерно соответствует джавному Iterable.

Последний пример - здесь тип RightEitherFunctor[L] параметризован - это означает, что для каждого L полученный Either[L, _] является функтором.

Более сложный пример - функтор Env:
  type E = Any => Int

  type Env[X] = E => X

  trait EnvFunctor extends Functor[Env] {
    override def f1[A, B](f: A => B) = (aa: Env[A]) => aa andThen f
  }


В данном примере изображается зависимость от окружения. Вместо констант типа X мы начинаем манипулировать функциями, зависящими от окружения (в данном случае, для простоты, окружение возвращает какие-то целые числа.)

А, и мы тут приплели монаду Env - хотя никакой монадичности пока что не определяли, а только вот функториальность.

3. McBride and Paterson



Мне предложили пройтись по статье Conor McBride, Ross Paterson, "Applicative programming with effects". Я перепёр большую часть их хаскельного кода на Скалу, и в этой части продемонстрирую, как оно выглядит и что оно делает.

3.1. Аппликативный функтор (по МакБрайду-Патерсону)


trait Applicative[T[_]] extends Functor[T] { self =>
  def pure[A](a: A): T[A]

// below are additional enrichments, not exactly pertaining to Applicative
  def ap[A, B](fs: T[A => B]): (T[A] => T[B]) = (ta: T[A]) => fs <*> ta

  implicit def applicable[A, B](tf: T[A => B]): Applicable[A, B, T]

  trait Lifted[A, B, T[_]] { def <@>(ta: T[A]): T[B] }

  implicit def lift[A, B](fun: A => B) = new Lifted[A, B, T] {
    def <@>(ta: T[A]) = pure(fun) <*> ta
  }

  def andThen[U[_]](u: Applicative[U]) = new Applicative[({type UT[X] = U[T[X]]})#UT] {
    type UT[X] = U[T[X]]
    def f1[A, B](f: A => B): (U[T[A]]) => U[T[B]] = u.f1(self.f1(f))

    def pure[A](a: A) : U[T[A]] = u.pure(self.pure(a))

    implicit def applicable[A, B](utf: U[T[A => B]]) = {
      val uta2tb: U[(T[A]) => T[B]] = u.f1(self.ap[A, B])(utf)
      new Applicable[A, B, UT] {
        def <*>(uta: UT[A]) = u.applicable(uta2tb) <*> uta
      }
    }
  }
}

trait Applicable[A, B, T[_]] { def <*>(ta: T[A]): T[B] }


3.2. Конкретные примеры аппликативных функторов


Должен извиниться, скальный вывод типов как-то мне не очень помогает, всё-таки не Хиндли-Милнер; поэтому ввожу и декларирую промежуточные переменные по мере необходимости. Если есть идеи как это упростить, буду рад. [livejournal.com profile] sassa_nf постоянно подбрасывает идейки; огромное ему спасибо.

object AppList extends ListFunctor with Applicative[List] {
  override def pure[A](a: A) = List(a)

  override implicit def applicable[A, B](lf: List[A => B]): Applicable[A, B, List] = {
    new Applicable[A, B, List] {
      def <*>(as: List[A]) = (for (f <- lf; a <- as) yield f(a)).toList
    }
  }
}


Здесь мы построили аппликативный функтор для списка, с операцией <*>, строящей декартово произведение списков; ну а остальное оттуда следует.

Вот этот тест иллюстрирует:
    "ApplicativeList" should {
      "combine two lists" in {
        import applicative.All.AppList._
        def pp(i: Int) = (j: Int) => i + j * j

        val combinations:List[Int] = ap(List(pp(1), pp(2)))(List(10, 20, 30))
        combinations must_== List(101, 401, 901, 102, 402, 902)
      }
    }


То же самое мы можем повторить и с Set
object AppSet extends SetFunctor with Applicative[Set] {
  override def pure[A](a: A) = Set(a)

  override implicit def applicable[A, B](ff: Set[A => B]) = {
    val sf: Set[A => B] = ff
    new Applicable[A, B, Set] {
      def <*>(fa: Set[A]) = (for (f <- sf; a <- fa) yield f(a)).toSet
    }
  }
}


Так как списки в Скале неленивы, то строить из них такой же зиплист как в Хаскеле не получится на самом деле. Ну то есть можно, но без ленивости получится ерунда.

Сначала посмотрим на код: в данном случае тензорное произведение двух последовательностей - это диагональ их декартова произведения.

object AppZip extends SeqFunctor with Applicative[Seq] {

  override def pure[A](a: A): Seq[A] = Stream.continually(a) // повторяем пока кому-нибудь не надоест

  implicit def applicable[A, B](ff: Seq[A => B]) = {
    new Applicable[A, B, Seq] {
      def <*>(az: Seq[A]) = ff zip az map ({ case (f: (A => B), a: A) => f(a) }) // в Скале уже есть зип; применим его
    }
  }
}


Смотрите, когда мы зипуем два списка, то полученный список прекращается по исчерпанию любой из компонент. Поэтому для того, чтобы, к примеру, одну и ту же функцию применить к списку (или наоборот, список функций к одному значению), мы вместо синглтона берём бесконечную последовтельность. Если б мы использовали списки, тут бы наш код и завис - чтоб зазиповать, он бы возжелал перечислить весь список. В Хаскеле списки ленивы. А в Скале ленивы потоки (Stream).

"ZipList" should {
  import All.AppZip._

  "be able to zip functions with values" in {

    def prepend(prefix: String) = (s: String) => prefix + " " + s
    val result = (List(prepend("a"), prepend("the")) <*> List("quick brown fox jumps over ", "lazy dog "))
    result must_== List("a quick brown fox jumps over ", "the lazy dog ")
  }
}


Вот более сложный пример - транспонирование матриц. (Я лично не приветствую идею представлять матрицу в виде списка списков, но это просто пример...
Так как zip у нас применяется к последовательностям, то на самом деле мы транспонируем последовательность списков.

"be able to transpose a matrix" in {

  trait matrices[A] { // матрицы с абстрактными элементами
    type matrix = Seq[Seq[A]]

    val glue: Seq[A => List[A] => List[A]] = pure(cons _) // функция, конкатенирующая элемент и список, применяется к последовательности

    def transpose(m: matrix): matrix = if (m.isEmpty) Nil else transposeNonempty(m) // приходится различать пустую и непустую, потому что размерность не указывать

    def transposeNonempty(m: matrix): matrix = { // нетривиальная часть
      m match {
        case Nil => pure(Nil) // это на случай, когда непустой вектор склеиваем с пустой матрицей
        case row :: rows => { // типичный случай - применим клей к row и остатку
          glue <*> row <*> transposeNonempty(rows)
        }
      }
    }
  }

  object m extends matrices[Int]
  import m._

  val m0x0: m.matrix = transpose(List[List[Int]]()).toList
  m0x0 must_== List() // мы не можем даже выразить m0x1

  val m0x1: m.matrix = transpose(List(List[Int]()))
  m0x1 must_== List()

  val m2x1: m.matrix = transpose(List(List(1, 2)))
  m2x1 must_== List(List(1), List(2))

  val m1x2: m.matrix = transpose(List(List(1), List(2))).toList
  m1x2 must_== List(List(1,2))

  val m2x2 = transpose(List(List(11, 12), List(21, 22))).take(12).toList
  m2x2 must_== List(List(11, 21), List(12, 22))
}



Этого, пожалуй, хватит на этот раз; в следующей части будет аппликативный функтор, вычисляющий арифметические выражения - не с константами, а с функциями (зависимость от "среды").
Затем моноид и "накопление сообщений об ошибках" (накапливаем в моноиде) и обход... ну не дерева, а Traversable - мапредьюс на самом деле - опять с моноидом.
juan_gandhi: (Default)
  trait RightEitherFunctor[L] extends Functor[({type Maybe[A] = Either[L, A]})#Maybe] {
    def f1[A, B](f: A => B): Either[L, A] => Either[L, B] = _.right.map(f)
  }
  
  
  trait AccumulatingErrors[Bad] {
    val errorLog: Semigroup[Bad]
    implicit def acc(err: Bad) = errorLog.acc(err)
    type Maybe[T] = Either[Bad, T]
    
    object App extends Applicative[({type Maybe[A] = Either[Bad, A]})#Maybe] with RightEitherFunctor[Bad] {

      def pure[A](a: A):Either[Bad, A] = Right[Bad, A](a)

      implicit def applicable[A, B](maybeF: Maybe[A => B]) = {
        new Applicable[A, B, Maybe] {
          
          def <*>(maybeA: Maybe[A]) = maybeF match {
            case Left(badF) => maybeA match {
                case Left(errorA) => Left(badF <+> errorA)
                case Right(_)     => Left(badF)
              }
            case Right(f)   => maybeA match {
                case Left(badA) => Left(badA)
                case Right(a)   => Right(f(a))
              }
          }
        }
      }
    }
  }




Со стрелками пока не буду разбираться, а добавлю ещё пример какой-нибудь, положу всё на гитхаб ([livejournal.com profile] sassa_nf, you are welcome to participate!), и перепишу часть 7.

И такое ощущение, что эту же хрень, в сокращённом виде, надо будет вставлять в рабочий код. В частности, недавно обсуждавшийся вопрос накопления ошибок - вот же ж решение, моноид. Ну в смысле полугруппа; моноид это у МакБрайда с Патерсоном; достаточно полугруппы.

Disclaimer. Эти знания бесполезны для 99% программистов.
juan_gandhi: (Default)
trait Applicative[T[_]] extends Functor[T] {
  def pure[A](a:A):T[A]
  def ap[A,B](tf:T[A=>B]): T[A] => T[B]
  def map[A,B](f:A=>B) = ap(pure(f))
}

abstract class Applicable[A, B, T[_]](fs: T[A=>B]) {
  def <*>(at: T[A]):T[B]
}
abstract class Lifted[A, B, T[_]](f: A=>B) {
  def <@>(ta:T[A]): T[B] // in Haskell it is <$>; can't use $ in Scala, and can't have lt;&s> either.
}

trait RichApplicative[T[_]] extends Applicative[T] {
  implicit def applicable[A,B](tf:T[A=>B]): Applicable[A, B, T]
  implicit def lift[A,B](f: A=>B) = new Lifted[A, B, T](f) { def <@>(at: T[A]) = ap(pure(f))(at)}
}

trait Traversable[T[_]] extends RichApplicative[T] {
  def traverse[A, B](f: A => T[B])(as: List[A]): T[List[B]] = as match {
    case Nil => pure(Nil)
    case head::tail => lift(cons[B] _) <@> f(head) <*> traverse(f)(tail)
  }

  def dist[A] = traverse(identity[T[A]] _) _
}


Work in progress. I'm on page 5. (dumb, eh)

Comments? Ideas?
juan_gandhi: (Default)
Still struggling implementing McBride/Paterson in Scala.
def K[env,a](x:a) = (gamma:env) => x
implicit def ski[env,a,b](ef:env=>a=>b) = new { 
  val S = (ea:env=>a) => (gamma:env) => ef(gamma)(ea(gamma))
}

val add = (i: Int) => (j: Int) => i+j
  type Env = String => Int
  def fetch(x: String) = (env: Env) => env(x)

  trait Expr
  case class Var(x: String)        extends Expr
  case class Val(i: Int)           extends Expr
  case class Add(p: Expr, q: Expr) extends Expr
  def Ke[T](x:T) = K[Env, T](x)
  
  def eval(exp: Expr): (Env => Int) = exp match {
    case Var(x) => fetch(x)
    case Val(i) => Ke(i)
    case Add(p,q) => (Ke(add) S (eval(p))) S (eval(q))
  }

eval(Add(Var("one"),Add(Var("three"), Val(11))))(Map("one" -> 1, "two" -> 2, "three" -> 3))



Kind of funny how one has to bypass the lack of Hindley-Milner... oh, whatever.

Will explain all this later, when I'm done with McBride-Paterson.
juan_gandhi: (Default)
[livejournal.com profile] sassa_nf высказал недоумение, если не больше, по вопросу как это мы вставляем ap между нашими аппликативными штучками, как это? Я думал, э, всё просто.

Протрахался с 7 до 11. Вот код с примером; а текст потом поправлю, спать же уже пора, ё.

  import scala.collection.immutable._

  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
juan_gandhi: (Default)
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


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

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

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

juan_gandhi: (Default)
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
juan_gandhi: (Default)
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Читатели спрашивают, а на хрена нам, практикам, сдались эти ваши монады? Мы и без монад хорошо зарабатываем.

Тут можно спросить собеседников, а нужна ли им также проза? Зачем им проза, они и без прозы хорошо могут обсуждать вопросы, например, у кого какая зарплата или почём хонда у дилеров. А что они сами употребляют прозу, обсуждая эти вопросы, то ещё Мольер писал в 17-м веке, но кто нынче читает Мольера - он ни в жж, ни в твиттер не пишет, так чо.

Итак, вы можете писать что угодно на чём угодно, в смысле программирования, и монады у вас там будут независимо от того, в курсе вы или нет. Если вы в вашу функцию вставляете System.out.println("Mom, I'm in a function!"), то это у вас монада. Если вы вставляете
String myDrive = new File(".").getAbsolutePath().split(":")[0]
, то это тоже монада. Если у вас в коде
User user = DaoFactoryManager.getUserDaoFactory().getUserDao().getUserByUserId(userId); if (user != null) ...
то это тоже монада, даже две.

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

Итак, проблемы.

Скажем, какой-нибудь метод livejournal.getFriends(userid: String): Option[Set[String]] - он возвращает или Some[Set[String]], или None когда жж в дауне, т.е. довольно часто.

В нашем коде мы можем не мудрствовать особо-то, а прям так и писать:

  livejournal.getFriends("ivan_gandhi") match {
    case None          => err.println("ну вот, опять Носик сломал код")
    case Some(friends) => { println("Это всё мои друзья:"); for (friend <- friends) println(" - " + friend) }
  }

Мы тут употребили три монады как минимум (на самом деле пять), но ощутили только одну. Это ничего.
А вот представьте теперь, что нам за каким-то хреном понадобилось составить список fof - friends-of-friends, Друзья Друзей. Ну и как мы это будем делать?

Если бы livejournal никогда не ошибался, а всегда бы возвращал Set[String], то мы ж могли бы выразить это наше действие одним циклом:

for (f   <- livejournal.getFriends("ivan_gandhi");
     fof <- livejournal.getFriends(f)
    ) println(" - " + fof)

или, эквивалентно и идиоматично, в одну строчку:
livejournal.getFriends("ivan_gandhi").flatMap(f => livejournal.getFriends(f)).foreach(x => println(" - " + x))


На то она и монада, что все эти действия происходят автоматически. И кстати, я не поминал раньше flatMap.

flatMap - это map за которым следует flatten - сначала мы применяем map, получая, в нашем случае, Set[Set[String]], а потом уже сплющиваем Set[Set[String]] → Set[String]. Сплющивание монады Set вещь не совсем тривиальная; могут попадаться дубликаты, их игнорируем.

Ну хорошо, а что же делать в нашем случае? Теоретически, в качестве результата мы получаем Option[Set[Option[Set[String]]]]. Мы можем получить ошибку при выборке списка наших друзей, и при выборке списка друзей любого из наших друзей, и неоднократно. Что можно предпринять? Можно прописать решение руками, например:


for (fOpt   <- livejournal.getFriends("ivan_gandhi");
     f      <- fOpt;
     fofOpt <- livejournal.getFriends(f);
     fof    <- fofOpt
    ) println(" - " + fof)


Такое решение годится для данного конкретного случая. Но не для общего случая. Представьте такое:


for (stockOpt   <- etrade.getPortfolio("vpatryshev", "password1");
     stock      <- stockOpt;
     batchOpt   <- etrade.getTrades("vpatryshev", "password1", stock);
     batch      <- batch
    ) println(stock + ": " + batch.size + "@" + batch.purchasePrice)


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

То есть смотрите - если у нас есть Set[Set[T]], то мы это можем сплющить. А если Set[Option[Set[Option[T]]]], то неочевидно. Если бы мы могли это преобразовать в Set[Set[Option[Option[T]]]], то можно было бы отдельно плющить Set[Set[...]] и Option[Option[T]]. Но проблема в том, что в общем виде такого преобразования не существует.

Монады не коммутируют. Не существует, в общем виде, преобразования M[N[x]] → N[M[x]]. Но, разумеется, в каждом конкретном случае можно какое-нибудь такое преобразование выдумать. Такие преобразования называются monad transformers по-английски; как они называются по-русски, я понятия не имею; не трансформеры же, и не трансформаторы же. Буду употреблять слово "преобразование" пока меня не поправят. Если б алгебраисты знали, какой тут катаклизм, они б подсказали - да коммутатор это, коммутатор. Но алгебраисты обычно такой фигнёй не занимаются.

Посмотрим, что можно сделать в случае Option. Нам нужно преобразование optionT: Option[M[T]] → M[Option[T]], независимо от природы M. Вот стандартное решение:

def optionT[M[_], T](optionalmt: Option[M[T]]) = optionalmt match {
  case None => M.unit(None)                // засунули None внутрь M, получив M[Option[T]]
  case Some(mt) => mt.map(t => Some(t))    // засунули Some() внутрь M, получив M[Option[T]] 
}


Хотя такое преобразование и не годится для примера с акциями, оно годится для примера с друзьями друзей. В примерах выше оно не используется, однако. На самом деле, в скальном цикле происходит вот что: и Set[T], и Option[T] наследуют от Iterable[T]; поэтому мы фактически сплющиваем Iterable[Iterable[Iterable[Iterable[T]]]], получая в конце концов Iterable[T]; дальше его можно вручную превратить в Set[T].

Аналогично можно определить преобразование List[M[T]] → M[List[T]]. Но не в общем виде. Поэтому в скале и в хаскеле существуют чуть ли не библиотеки преобразований; а т.к. решение в общем случае довольно произвольно, то нельзя сказать, что это единственно правильные преобразования.

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

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

На эту тему много интересного можно почитать у [livejournal.com profile] akukleva, у Дебасиша, у Тони Морриса (Monads do not compose), ну или, если ваш уровень хаскеля достаточен, можно прочитать 18-ю главу rwh, или вот это.

Итак, мы не можем произвольно строить монады из данных нам природой монад; но в жизни-то мы хотим соединять преобразования данных так, как нам надо; и, следовательно, надо искать какую-то не то чтобы замену монадам, а послабление. Можем же мы обойтись без чего-то?

Это послабление в компьютерной науке называется аппликативным функтором. В следующей части мы постепенно перекатимся от монад к аппликативным функторам. В компьютерной науке есть поверие, что всякая монада является аппликативным функтором. Это не так, но это ещё более другая тема.
juan_gandhi: (Default)
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


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

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

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

С другой стороны, монаду можно вообще не признавать - считать землю плоской, вселенную однородной и изотропной, пространство евклидовым, вакуум непробиваемым.
juan_gandhi: (Default)
1, 2, 3, 4, 5, 6, 7, 8, 9, 10


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

Чтобы справиться с нетотальностью функций, с которыми мы имеет дело, есть несколько альтернатив.

Рассмотрим очевидные:
- null
- exceptions
- null object
- Option

1. null


В принципе, джава унаследовала null из си, и жила не тужила, пока не появились ещё дженерики, и стало как-то неудобно. До монад далеко, но уже неудобно.

То есть, вернуть null - да никаких проблем, кто только не возвращает null; и принять null в качестве параметра тоже милое дело, дескать, нетути этого вашего параметра, ну не шмогла я.

И люди вполне спокойно пишут функции, которые проверяют параметр на null и если что, возвращают null; чем не Option. Да тем, что всё это нужно явно прописывать.

  String countryName(User user) {
    if (user == null) return null;
    String phone = user.getPhone();
    if (phone == null) return null;
    String countryCode = PSTN.extractCountryCode(phone);
    if (countryCode == null) return null;
    Country country = Countries.findByCode(countryCode);
    if (country == null) return null;
    return country.getName();


Этот же код можно написать более прилично (10x [livejournal.com profile] sab123):
  String countryName(String userId) {
    User user; Phone phone; String cc; Country country;
    return userid != null
       && (user = db.findUser(userid)) != null
       && (phone = user.getPhone) != null
       && (cc = phone.getCountryCode) != null
       && (country = Countries.findByCode(cc)) != null ? country.getName() : null
  }


Ниоткуда не известно, что функция, получающая null, волшебным образом должна вернуть null, или что метод, вызванный на объекте null, вернёт null, а не, к примеру, 0, если хотим длину. Поэтому и пишут методы isEmpty(String s) { return s == null ? 0 : s.isEmpty(); }.

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

Но в принципе, если нам попался null вместо осмысленного значения, и нам надо с него что-то взять, то мы получим NPE; исключение - более-менее монада, в отличие от null.

2. exceptions


Если б мы были циниками, а не серьёзным джава-программистами, озабоченными производительностью компьютера, наносекундами и килобайтами, мы б могли писать так:

  String countryName(User user) {
    try {
      return Countries.findByCode(PSTN.extractCountryCode(user.getPhone()));
    } catch (NPE npe) {
      return null;
    }
  }


Согласитесь, выглядит не очень прилично - но гораздо более осмысленно. К тому же, вполне монадично - если NPE на нас не бросится, то вернём "данное", ну а если бросится, так только одно. Может быть, так и надо на джаве писать.
Тут только такая проблема, что мы не знаем, откуда прибежал этот NPE - может, вовсе и не из-за того, что у нас данных нету; для прототипа такой код годится, а в реальной программе вряд ли. Но для прототипа годится.

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

3. Null Object Pattern



Истинный джавщик не может без паттерна. Null Object горячо рекомендуют наши кумиры, Нил Гафтер и Джош Блок. Имеет смысл - если ничего не нашли в базе, возвращаем не страшный null, а его представителя в данном типе;
NullUser
, у которого есть
NullPhone
у которого есть пустой номер (""), по которому PSTN возвращает пустой код страны (или код пустой страны... хм, я знаю одну пустую страну, называется Атолл Диего Гарсиа - код страны есть, но нет ни одного опубликованного телефона; все на кораблях. Но мы введём пустую страну, NullCountry, и тогда Всё Будет Правильно.

Смысл этой операции такой, что теперь в коде мы можем предполагать тотально определённые функции и не отвлекаться на исключения.
Функция
  String countryName(User user) {
      return Countries.findByCode(PSTN.extractCountryCode(user.getPhone()));
  }

вернёт пустую строку.

В сущности что мы сделали - это каждый тип пополнили своим отдельным None/NAN/Not_a_Country/Not_a_Phone/Not_a_Pipe. Практически монада Option, но имплементированная для каждого типа отдельно, вручную; для различения ещё нужно добавить метод boolean isValid(), который будет возвращать true для нормальных значений и false для нашего None.

4. Option


Ну или можно сделать умственное усилие и добавить интерфейс Option<T>, у которого будет две имплементации, None и Some(T value).

Она монада потому, что имеются две стандартные операции:

единица монады, строящая по значению T x значение new Some<T>(x) - т.е. просто конструктор, и

монадное умножение, часто называемое операцией flatten - если есть Option<Option<T>>, то из него получается Option<T>.

Монады бывают разной степени сложности, Option из них самая простая. Её и плющить особенно легко:
None превращается в None,
Some(None) превращается в None,
Some(Some(x)) превращается в Some(x).

Сравните с плющеньем списка: List<List<T>> → List<T> - в данном случае мы пробегаем по списку списков и возвращаем список всего, что нам попалось по дороге:

  <T> List<T> flatten(List<List<T>> lol) {
    List<T> result = new // something
    for (List<T> list : lol) {
      for (T element : list) {
        result.add(element);
      }
    }
    return result;
  }


На Скале ту же операцию можно выразить проще:
  def flatten[T] (lol: List[List[T]]): List[T] = {
    val result = new scala.collection.mutable.// какой-нибудь список подходящего типа
    for (list    <- lol
         element <- list) result.add(element)
    result
  }


Ну или ещё проще: def flatten[T] (lol: List[List[T]]) = lol.flatten

С помощью Option с частичными функциями обращаться проще - вместо списка, вместо null, вместо исключения мы просто возвращаем всегда Option; а чтобы применить функцию к "содержимому Option", мы можем использовать цикл:

  for (User user : db.findUser(userid)) {
  for (Phone phone : user.getPhone()) {
  for (String countryCode: phone.getCountryCode()) {
  for (Country country: Countries.findByCode(countryCode)) {
    System.out.println("User " + user + " is from " + country);
  }}}}


Чтобы можно было писать цикл, нужно вот что: Option<T> implements Iterable<T> - ну это несложно. None всегда возвращает пустой Iterable, а Some возвращает одноэлементный Iterable.

На скале такая конструкция записывается в виде одного цикла:
  for (user    <- db.findUser(userid)
       phone   <- user.getPhone
       cc      <- phone.getCountryCode
       country <- Countries.findByCode(cc)
  ) println("User " + user + " is from " + country)


За сценой такой хитрый цикл разворачивается в последовательность сплющиваний.

Нет, на самом деле надо добавить ещё одну операцию, преобразование, fmap

Если у нас есть функция <A,B> B f(A a) {...}, то монада... ну, скажем, та же Option, определяет функцию
<A, B> Option<B> Option_f(Option<A> aOpt) { 
  for (a : aOpt) { return new Some<B>(f(a)); }
  return None;
}


На скале это выглядит практически так же:
def Option_f[A,B](aOpt: Option[A]) = {
  for (a <- aOpt) return Some(f(a))
  None
}


Или просто def Option_f[A,B](aOpt: Option[A]) = aOpt map f

Думаю, Вы можете написать аналогичную операцию для монады списка (List).

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

К сожалению, и с монадами нас подстерегают неприятности, о которых я расскажу в следующей части. Но не думайте, что без монад всё здорово и можно обойтись if-ами. Напротив; с if-ами вы просто не замечаете проблем в вашем коде - они парят как коршуны где-то над головами, а мы как мыши суетимся, ищем, где бы тут соптимизировать да все случаи учесть. "Книги про паттерны" не помогают.
juan_gandhi: (Default)
1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Вот вы приходите на интервью, и вас просят написать, скажем, на джаве, программу, вычисляющую факториал. И Вы пишете
int fact(int n) {
  return n < 2 ? 1 : n * fact(n-1);
}


и довольны типа. И интервьюёр доволен. А того не смекнули, что ваша функция для 17 вернёт -288522240. Разве ж це факториал? Это уже скорее гамма-функция от -0.0000000346593739, примерно, то есть, (-1.0000000346593739)! (примерно).

На самом деле ещё смешнее, fact(13) = 1932053504 даже не делится на 13; правильный ответ был бы 6227020800.

Тут что-то не так. И для отрицательных чисел тоже фигня получается; гамма функция для них, для целых отрицательных, не определена.

Правильнее было бы написать что-нибудь вроде

int fact(int n) {
  if (n < 0 || n > 12) throw new IllegalArgumentException("won't calculate factorial for " + n + ", should be between 0 and 12");
  return n < 2 ? 1 : n * fact(n-1);
}


Так, конечно, никто не делает, потому что непривыкшие мы. Мы, зато, можем легко найти объяснения, почему такое происходит и даже винить особенности JVM, или предлагать использовать long вместо int (и, соответственно, 20 вместо 12). Проблема, конечно, не в этом. Всегда найдутся обстоятельства.

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

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

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

С таким оптимизмом можно ж и в Вегас ездить - вы ведь не лох, вы обязательно выиграете!

Я что хочу сказать - в реальности наш код имеет дело не с результатом, а с возможным результатом. Это монада такая. Если нам пофиг если что не так, но мы знаем, что бывает что-то не так, то это у нас монада Option, aka Maybe. В принципе, вполне моделируется списком или множеством из не более чем одного элемента. Да и в цикле неплохо смотрится:

for (int f: factorial(n)) {
  System.out.println("factorial(" + n + ") = " + f);
}

List<int> factorial(final int n) {
  if (n < 0 || n > 12) return Collections.emptyList<Integer>();
  return n < 2 ? Arrays.asList(1) :
      factorial(n-1).map(new Function <Integer, Integer>() {
        public Integer apply(Integer k) {
          return n * k;
        }
      });
}


Это я написал в предположении, что в джаве у класса List есть метод map; такого метода, конечно, нету, поэтому нам тут надо бы переписать без рекурсии, с циклом. Но это неважно; важен принцип.

И тут я собираюсь покинуть простую нашу народную джаву и буду дальше использовать скалу в качестве иллюстрации, потому что на скале всё проще, и тот же пример пишется так:

for (f <- factorial(n)) {
  println("factorial(" + n + ") = " + f);
}

def factorial(n: Int): List[Int] = {
  if      (n < 0 || n > 12) List()
  else if (n < 2)           List(1) 
  else                      factorial(n-1) map (x => n * x)
}


Точнее, вместо списка в скале, конечно, надо использовать Option:

def factorial(n: Int): Option[Int] = {
  if      (n < 0 || n > 12) None
  else if (n < 2)           Some(1) 
  else                      factorial(n-1) map (x => n * x)
}


В случае, если нам важно как-то сохранить и передать подробности о случившейся неудаче, тут уже или исключение используем, или скальное Either, которое в случае удачи содержит результат, а в случае неудачи содержит информацию об ошибке.

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

В джаве это у нас любимый приём: вызвать функцию и потом проверять, уж не null ли нам вернула эта функция. И понеслась, if (connection != null)... if (userId != null)... if (user != null).... Этим говнокодом, как фликр фотографиями кошек, заполнены все гиты, эсвээны, сивиэсы, перфорсы, виэсэсы, и в наибольшей степени - клиеркейсы.

И всё мало - процента на 84 беды джавного софтвера состоят в NPE, NullPointerException, внезапно выскакивающем неведомо откуда, хоть ты святой водой кропи этот код, а всё равно.

Я уж про си и говорить не буду, в отличие от джавы, где NPE можно уподобить мокрым штанам, в си всякий такой сегфолт - практически теракт, в следующее мгновение иранские хакеры проникнут к вам в компьютер и скачают номер вашей кредитной карточки. И ничего не поделаешь! Пойнтер так и норовит занулиться сам по себе, как будто это его естественное состояние! Но в си программисты более напуганные, и поэтому в си это значительно реже случается - что, конечно, обходится недёшево.

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

Profile

juan_gandhi: (Default)
juan_gandhi

March 2017

S M T W T F S
    1 2 3 4
5 6 7 8 9 1011
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 293031 

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Mar. 29th, 2017 09:09 pm
Powered by Dreamwidth Studios