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

June 2017

S M T W T F S
     1 2 3
4 5 67 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
252627282930 

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jun. 25th, 2017 08:52 pm
Powered by Dreamwidth Studios