juan_gandhi: (Default)
Уже чуть не месяц прошел. Присоветовали добрые люди МакБрайда с Патерсоном перепереть на язык родных Скал. Перепёр - не работает. Только что багу у себя нашел. Теперь работает.

implicit def ski[env,a,b](ef:env=>a=>b) = new { val S = (ea:env=>a) => (e:env) => ef(e)(ea(e))}
def K[env,a](x:a) = (gamma:env) => x
type E = Any => Int
def KEnv[X](x: X) = K[E, X](x)

val add = (i: Int) => (j: Int) => i+j

def fetch(x: String) = (env: E) => 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 eval(exp: Expr): (E => Int) = exp match {
  case Var(x) => fetch(x)
  case Val(i) => KEnv(i)
  case Add(p,q) => KEnv(add) S eval(p) S eval(q)
}

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


Пойду на огороде поработаю, на велике покатаюсь, и дальше чесать.
juan_gandhi: (Default)
Yesterday at Intel we Martin Odersky was giving an informal talk on how things are etc. Mostly on the features of 2.10. Pretty cool. Macros are experimental, if included. Anyway; good stuff.

There were over 50 people in total, and a kind of warm atmosphere; after the talk we stood chatting for about an hour, this and that, and functional, and monads (everybody gives me a nudge as soon as the word "monad" is mentioned... talking about myself - Martin seems to remember my name, weird.)

Next two meetings are next week; Monday at Twitter ("Scala at Twitter" - they are pretty advanced indeed), and Wednesday at LinkedIn ("Scala at LinkedIn") - this one I'm planning to attend.

It's all on meetup, so there.

P.S. [livejournal.com profile] xeno_by, I talked with Bill Venners regarding macros; seems like he's looking for more details, to use this stuff in his scalatest; do you have a fresh preso? I'd forward it to him. Or you could.
juan_gandhi: (Default)
def take[X](n: Int) = { var i = 0; (x:X) => {i = i + 1; i <= n}}   
take: [X](n: Int)(X) => Boolean

scala> 2 to 100 by 7 filter (take(5))                                  
res5: scala.collection.immutable.IndexedSeq[Int] = Vector(2, 9, 16, 23, 30)
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)
  def fileContent(key: String): Either[Any, String] = 
    BootConfig.settings.get(key).toRight.
    right.flatMap(probablyFile).
    right.flatMap(_.probablyText)


I love Either.

What I miss is OptionEither transformer (natural transformation I'd say).
juan_gandhi: (Default)
src

// Encoding for "A is not a subtype of B"
trait <:!<[A, B]

// Uses ambiguity to rule out the cases we're trying to exclude
implicit def nsub[A, B] : A <:!< B = null
implicit def nsubAmbig1[A, B >: A] : A <:!< B = null
implicit def nsubAmbig2[A, B >: A] : A <:!< B = null

// Type alias for context bound
type |¬|[T] = {
  type λ[U] = U <:!< T
}


def foo[T, R : |¬|[Unit]#λ](t : T)(f : T => R) = f(t)

foo(23)(_ + 1) // OK
foo(23)(println) // Doesn't compile


So, how it works.

First we define the trait <:!< which looks like a negation of <:< - in Scala this notation means that one type can be, via implicits or whatever, converted into another.
Note that when you declare a type, and the type depends on two parameters, you can write the type in the infix form, e.g. String Map Int; in our case, instead of val x: <:!<[A, B] we can write val x: A <:!< B

E.g.
scala> def f(m: String Map Int) = Map("one" -> 1)
f: (m: Map[java.lang.String,Int])scala.collection.immutable.Map[java.lang.String,Int]


Why do we need a trait that does not specify any functionality? See below.

We define three implicits. The first one, implicit def nsub[A, B] : A <:!< B = null, is applicable in a case of any two types A and B; if we had just this one, the compiler would be never confused. Now we add two more to confuse the cat the compiler:
implicit def nsubAmbig1[A, B >: A] : A <:!< B = null
implicit def nsubAmbig2[A, B >: A] : A <:!< B = null


Their role is that whenever we encounter a context where <:!<[A, B] is required, and B is a supertype of A, the cat the compiler gets confused. It does not get confused if there is no such relationship between the two types. Namely, we get this error:
:27: error: ambiguous implicit values:
both method nsubAmbig1 in object $iw of type [A, B >: A]=> <:!<[A,B]
 and method nsubAmbig2 in object $iw of type [A, B >: A]=> <:!<[A,B]
 match expected type <:!<[Unit,Unit]


So, what do we do to use this feature? We declare a type function (seems like a new term) that is negation type for type T: whenever we apply this function to type U, it only allows to compile if U is not a subtype of T.
type |¬|[T] = {
  type λ[U] = U <:!< T
}


This is a kind of a type trap; let's see how we use it.

Declare a function foo that takes first parameter of type T, and second parameter a function from T to R:

def foo[T, R](t : T)(f : T => R) = f(t)


We can call it as val n24 = foo(23)(_ + 1) or as foo(23)(println). Now how do we make sure that it does not take a function that returns Unit? We have to delimit the second type parameter, R, so that it's never a Unit or a subclass of Unit. This is how we do it:
def foo[T, R : |¬|[Unit]#λ](t : T)(f : T => R) = f(t)


Now the second example, foo(23)(println), won't compile. Ta-da!

More questions?
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)
object FS {
  class TextFile(val file: File) {
    def text = Source.fromFile(file).mkString

    def text_=(s: String) {
      val out = new PrintWriter(file, "UTF-8")
      try{ out.print(s) } finally{ out.close }
    }

    def parent = new Folder(file.getParentFile)
    override def toString = file.getAbsolutePath
  }

  class ExistingFile(file: File) extends TextFile(file) {
    require(file.exists(), "File " + file.getAbsolutePath + " must exist")
  }

  class Folder(path: File) extends ExistingFile(path) {
    require(path.isDirectory, "File " + path.getAbsolutePath + " must be a directory")
    def file(name: String) = new TextFile(new File(path, name))
    def subfolder(name: String) = new Folder(file(name))
    def existingFile(name: String) = new ExistingFile(file(name))
  }

  implicit def asFile(file: TextFile) = file.file
  implicit def textFile(file: File) = new TextFile(file)
  implicit def existingFile(file: File) = new ExistingFile(file)
  implicit def asFolder(file: File) = new Folder(file)
  implicit def file(name: String) = new File(name)

}


and the usage is:

  val configFiles = List("ac_office.xml", "broker.xml", "dse.xml", "pe.xml", "ao_office.xml", "dashboard.xml", "license.txt"")
  for (name <- configFiles) {
    val d = bootDir.file(name)
    if (!d.exists) d.text = setupDir.subfolder("setup").existingFile(name).text
  }

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)
 
 val serverSocket = try {new ServerSocket(port)} catch {
    case e: java.net.BindException => {
      println("wtf, several copies? what is it? ")
      throw new IllegalStateException("this port, " + port + ", is already taken!")
    }
  }
juan_gandhi: (Default)
So, I decided, wtf, why should I write it in sh or python if I can use scala, right? Here's the code I'm writing

Read more... )
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 можно уподобить мокрым штанам, в си всякий такой сегфолт - практически теракт, в следующее мгновение иранские хакеры проникнут к вам в компьютер и скачают номер вашей кредитной карточки. И ничего не поделаешь! Пойнтер так и норовит занулиться сам по себе, как будто это его естественное состояние! Но в си программисты более напуганные, и поэтому в си это значительно реже случается - что, конечно, обходится недёшево.

(продолжение следует... кстати, не думайте, что я тут заявляю рецепт лекарства от рака; нет, у меня с головой вроде бы в порядке, я просто хочу включить в одном из тёмных углов лампочку поярче)
juan_gandhi: (Default)
  def tryOr[T](message: String)(action: => T) = {
    try {
      Some(action)
    } catch {
      case e: Throwable => {
        Log.error(message, e)
        None
      }
    }
  }


using like

tryOr("Oi-vei, could not find...") { database.findUserNamed("Captain Nemo") }


Could use Either as well, I don't know.
Gradually morphing from Java.

Profile

juan_gandhi: (Default)
Juan-Carlos Gandhi

November 2025

S M T W T F S
       1
23456 7 8
9 1011 12 1314 15
16171819 20 2122
23 24 252627 28 29
30      

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Dec. 1st, 2025 02:35 am
Powered by Dreamwidth Studios