juan_gandhi: (Default)
2012-01-11 11:20 pm

strong monads in cartesian-closed categories are applicative functors

Got it eventually. Thanks to [livejournal.com profile] huzhepidarasa and "Applicative programming with effects" by McBride and Paterson.

So, let's see.

In Haskell, in Scala, and I don't know... in PHP? every monad is an applicative functor, with the help of lift2. But I could not figure out where does it come from?

Say we have a category C that has products a × b and power objects, ba; an endofunctor T is called applicative if it is supplied with two natural transformations,
pure: a → T(a) and (*): T(ba) → T(b)T(a) that have obvious properties.

The statement is that every monad is an applicative functor.

Turned out not every monad, but a strong one.

A strong monad is a monad that has a natural transformation ta,b: a × T(b) → T(a×b) with a bunch of good properties that could be found on wikipedia (are they called coherence? something like that - MacLane studied them eons ago).

Anyway, a strong monad is an applicative functor.

We already have pure; have to define (*).

The trick is this.

Given a binary operation f: a×b → c then we will lift this binary operation (since we deal with a function of two parameters, the operation is called lift2) to T(a)×T(b) → T(c)

Namely, we have

tT(a),b: T(a)×T(b) → T(T(a)×b)
T(flipT(a),b): T(T(a)×b) → T(b×T(a))
T(tb,T(a)): T(b×T(a)) → T(T(b×a))
T(T(flipb,a)): T(T(b×a)) → T(T(a×b))
T(T(f)):T(T(a×b)) → T(T(c))
mc: T(T(c)) → T(c)

Composing them, we will have the lift2 we were looking for.

Now take evala,b: a × ba → b, and apply lift2

We will have T(a) × T(ba) → T(b); currying it, we get (*): T(ba) → T(b)T(a)

This may be obvious from the fp point of view, but I am a categorist, not a functional programmer (although you should have seen the rich loops I've been writing lately in Scala), so I needed a sound proof, not just a sound of a proof.

Thank you.

Questions and remarks greatly welcome.
juan_gandhi: (Default)
2011-11-30 12:50 pm
Entry tags:

славный наброс

пусть ярость благородная вскипает как волна

"Right now at Yammer we're moving our basic infrastructure stack over to Java"

Here's what Josh Suereth writes on this topic.
juan_gandhi: (Default)
2011-11-27 10:34 pm

демагогия о типах

Не о каких-нибудь там особо хитрых; в принципе, чуть ли не двоичных значений хватает, чтобы продемонстрировать.

Начнём, конечно, с Джавы. В которой сплошь и рядом, у "плохих программистов" встречается такое:
  if (message inscanceof CancellationMessage) { application.cancelnahren(); }
  else if (message instanceof EncouragementMessage) { galera.trabalha(); }
// etc


и хорошим программистам это не нравится, и они говорят "делегейшен давай", или "смартенумы давай!"

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

Ну или енум использовать - но енум контента не имеет, это константа... тогда люди ещё как поступают: в класс вставляют этот самый енум, "тип инстанса нашего класса".
  class Message {
    enum type {
      CANCEL,
      ENCOURAGE,
      DGAF} myType;
    ....
  }
...
  switch(message.type()) {
    case CANCEL: ...
    case ENCOURAGE: ...
    case DGAF: ...
  }


и это кошернее, чем было бы писать
  class mc = message.getClass();
  if (mc.equals(CancelMessage.class)) { ... }
  else if (....


В Скале же, на самом деле, не особо стесняются расписывать по классам, но на то есть другая причина: unapply, а ещё лучше сказать, линза (обратная сторона); с помощью её можно устраивать сравнение по образцу и, в зависимости от типа, выполнять какие-то действия с параметрами конструктора.
  message match {
    case CancelMessage(timeout: TimeInSeconds) => app.cancelato(timeout)
    case EncourageMessage(text: String) => galera.listen(text); galera.trabalha
    ...
  }


Фактически эта конструкция в некотором смысле помещает исполяемый, специфический для класса параметра, код немножко в контекст этого класса (видны только параметры конструктора).

В Скале есть немножко тенденция некоторые классы объявить более равными, например Option[T], Either[Left,Right] - для них как бы некошерно употреблять кейсы, а надо использовать функциональную функцию map. В принципе, скальные библиотеки любят возвращать Option[T], и тут-то бы и применять map, да штука в том, что в случае None ничего ни к чему применяться не будет. Так что приходится расписывать кейс. И со списками, что характерно, кейс приходится писать: как правило, разбивая ситуацию на два случая - пустой список или голова с хвостом, неважно, пустым или нет.

Так же и на Хаскеле - или мы матчим список, или Maybe, или data type.

И вот это вот "перечисление случаев" меня как-то смущает; нельзя ли для этого дела пристроить что-то вроде map? Но блин, это ж надо передавать, вообще говоря, по специальному исполнителю на каждый отдельный жизненный случай. Как в Джаве любят писать - лисинеры, listeners - они будут теперь здоровкаться на каждый чих.

Это практически cps, continuation passing style. Как в Джаваскрипте, если вы ещё помните, что такое xhr, а не вызываете что-нибудь там вроде JQuery.doAjaxForMeHurry(), то у вас как правило два-три таких слушателя: - пока читает, - когда закончили, - если ошибка. А могли бы написать (если б могли)

  reset {
    switch {
      case STILL_READING: ...; break
      case GOT_RESULT: ...; return
      case ERROR: ...; return
    }
    shift(k) {
      do {
        var resp = XHR.doPost(myStuff)
        k(resp)
      }
    }
  }


Это было бы почти идеальное решение, да?

Не знаю, не знаю.
juan_gandhi: (Default)
2011-11-09 10:49 am
Entry tags:

intellij puzzle really

Imagine, imported a pom project in intellij, and somehow it tries to parse all scala code as if it were java.

mvn clean install does compile stuff perfectly.

Any ideas?!
juan_gandhi: (Default)
2011-10-26 11:02 am

какой облом, боже мой

Сегодня утром читал офигенную статью, типа Тони Морриса, а может Майлса Сабина, а может и свою, где разъяснеяется как сиквельные транзакции и синхронизация через delimited continuations и актёров в скале (кстати, ходит слух, что акковские актёры заменят скальных) вполне могут быть объединены в одно чистое, легко читаемое, монадическое явление, типа на основе STM.

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

Дочитал.

Проснулся.

В голове пустыня.

И ещё простуженный к тому ж.
juan_gandhi: (Default)
2011-10-15 12:01 pm
Entry tags:

negation of a type

(from Miles Sabin's post)
// 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

(src)
juan_gandhi: (Default)
2011-07-31 02:32 pm
Entry tags:

scala fun (or defun)

scala> lazy val xvii = println("oh shit")
xvii: Unit = 

scala> def schroedinger(x: => Any) { if (java.lang.System.nanoTime %100 == 1) x }
schroedinger: (x: Any)Unit

scala> schroedinger(xvii)
oh shit

scala> schroedinger(xvii)

scala> 

juan_gandhi: (Default)
2011-07-31 02:32 pm
Entry tags:

scala fun (or defun)

scala> lazy val xvii = println("oh shit")
xvii: Unit = 

scala> def schroedinger(x: => Any) { if (java.lang.System.nanoTime %100 == 1) x }
schroedinger: (x: Any)Unit

scala> schroedinger(xvii)
oh shit

scala> schroedinger(xvii)

scala> 

juan_gandhi: (Default)
2011-07-22 07:13 pm
Entry tags:

an introspection into Scala and Chinese

"The scala code with implicit is similar like classical Chinese with metaphor.
It could express things with little or without word.

But it ask the code writer have much knowledge , experiences.
And the code reader should family with the full code context."
juan_gandhi: (Default)
2011-06-19 10:50 am

easiest caching in scala

def cached[K,V](f: K => V) : K => V = {
       val cache = new scala.collection.mutable.HashMap[K,V]
       k => cache.getOrElseUpdate(k, f(k))
     }
juan_gandhi: (Default)
2011-05-25 11:26 am
Entry tags:

on variance, common sense in several short sentences


Why is type inference failing here?

scala> val xs = List(1, 2, 3, 3)
xs: List[Int] = List(1, 2, 3, 3)

scala> xs.toSet map(_*2)
<console>:9: error: missing parameter type for expanded function ((x$1) => x$1.$times(2))
       xs.toSet map(_*2)
juan_gandhi: (Default)
2011-05-18 09:16 pm
Entry tags:

scalac warning

"recovering from existential Skolem type error"
juan_gandhi: (Default)
2011-05-10 11:17 pm

Now again


  1. a not totally trivial example implemented using JPA and Scala

  2. an event sourced implementation using explicit state changes

  3. a straightforward translation of the mutable event sourced implementation into an immutable implementation

  4. encoding domain knowledge into the type system to make the domain easier to understand and reduce the number of runtime error checks

  5. Towards an immutable domain model – monads (part 5) the stuff above translated into monads (where it should be)
juan_gandhi: (Default)
2011-04-22 11:12 am

Oleg Kiselyov explains why not Order extends Equals

Subclassing errors, OPP, and practically checkable rules to prevent them

P.S. I believe the problem is that with stateful objects, we do not know exactly which category are we dealing with; roughly speaking, for class A subclassing class B, there are actually two monads, with a natural transformation from one to another; and we think we have a functor from, not sure yet, one Kleisli category to another, or from one Eilenberg-Moore category to another, or even an interesting relationship between two categories of adjoints generated by the monads.

Have to look closer; maybe this explains the problem with "Liskov substitution".
juan_gandhi: (Default)
2011-04-18 05:14 pm

impenetrable scala

implementing Oleg Kiselyov's multiprompt continuations

// CC monad: general monadic operations
trait MonadicCCScope[P[M[_],_],M[_]] {
  type MonadM  CCC[B]
    ) : CCC[B] = {
      def check ( ccv : CCV[P,M,A] ) : M[CCV[P,M,B]] = {
ccv match {
...


(imho, something between J and Brainfuck)
juan_gandhi: (Default)
2011-04-18 05:00 pm
Entry tags:

Tony Morris said

"Every
single function that exists on List can be written using foldRight.
Indeed, List *is* foldRight.

The following trait is exactly equivalent to scala.List in its structure:
trait List[A] {
 def foldRight[B](b: B, f: (A, B) => B): B
}

As an exercise, implement the entire List API using this single abstract
method."