and more on type classes in Scala

[juan_gandhi]

This part is not exactly a theory of algebraic theories, but anyway.

Imagine we have a parametric class (e.g. List[X]) for which we would like to define methods that would only work if X satisfies certain conditions. E.g. define sum if it is a numeric type, or define flatten if it is some kind of sequence (Traversable[Y] would be enough). How can we accomplish it in Scala?!

Suppose we want to declare flatten

trait List[X] {
// bla-bla-bla

  def flatten[X <% Iterable[Y]] { ... } // no way, we already mentioned X; this one would shadow the previous one
// OOPS!
}

The trick would be to have an implicit transformation handy that transforms X into Iterable[Y] for some Y; and define it so that if X is actually some kind of Iterable, the implicit would be available, and otherwise not available.

Where can we find such a general transformation? The only thing that comes up to mind is an identity:

implicit def itsme[Y, X <% Iterable[Y]](x: X): Iterable[Y] = x

This would be enough in this specific case... but then we would have to define another one for numeric types, and so on.

We can go generic, and write something like this:

abstract class SafeToCast[-S, +T] extends Function1[S, T]
implicit def canCast[X <% Y, Y]: SafeToCast[X, Y] = new SafeToCast[X,Y] { def apply(x:X) = x }

Now we can define flatten, like this:

class List[X] { ...
  def flatten[Y](implicit transformer: SafeToCast[X, Iterable[Y]]) { ... }
}

All the conditions are satisfied now. Contravariance in the first argument and covariance in the second argument ensure that a subtype can be cast to its supertype... to be more precise, an instance of supertype can be substituted by an instance of subtype.

The only thing is that we can try to make the code more readable, by refactoring.

Step 1. Use the trick in Scala that binary operations can be written in an infix way, even for types. E.g. you can declare val map: (String Map Int) - this is the same as Map[String, Int].

sealed abstract class SafeToCast[-S, +T] extends Function1[S, T]
implicit def canCast[X <% Y, Y]: (X SafeToCast Y) = new (X SafeToCast Y) { def apply(x: X) = a }
...

class List[X] { ...
  def flatten[Y](implicit transformer: X SafeToCast Iterable[Y]) { ... }
}

Step 2. Rename the method, giving it a more "type-relationship" name: SafeToCast -> <:<.

sealed abstract class <:<[-S, +T] extends Function1[S, T]
implicit def canCast[X <% Y, Y]: (X <:< Y) = new (X <:< Y) { def apply(x: X) = a }
...

class List[X] { ...
  def flatten[Y](implicit transformer: X <:< Iterable[Y]) { ... }
}

That's the trick.

(if you have questions, ask; if you have corrections, please tell me)

Comments

[sassa-nf.livejournal.com]

алсо,

case class L[X](val x: X) { def double[_ >: X <: Int] = /* safe to cast now */ (x.asInstanceOf[Int])*2 } жаль, конечно, что скала не умеет умозаключить, что X - субкласс Int из экзистенциального баунда на _.

[xeno-by.livejournal.com]

У нас констрейнты на type vars весьма ограниченные + очень локальные (одно из размышлений на эту тему с участием Мартина и Спивака: http://pchiusano.blogspot.ch/2011/05/making-most-of-scalas-extremely-limited.html).

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

Конкретно по деталям реализации, есть символ X, у него есть сигнатура, однозначно определяемая его дефинишеном и никак не изменяемая. Types.isSubType определен в scala-reflect.jar, т.е. он ничего не знает про контексты тайпчекера, определенные в scala-compiler.jar, т.е. единственное, что он может сделать - спросить у символа сигнатуру => фейл.

[sassa-nf.livejournal.com]

спасибо.

а почему implicit вот такого вида не работает:

implicit def safeCast[X,Y, _ >: X <: Y]( x:X ):Y = x.asInstanceOf[Y]
case class L[X](val x: X) { def double[_ >: X <: Int] = x*2 }

[xeno-by.livejournal.com]

Можно, пожалуйста, полный сниппет, который не компилируется? Я, если честно, не понял, куда safeCast должен примениться в твоем примере.

[sassa-nf.livejournal.com]

он должен был попасть в x*2, заменяя x.asInstanceOf[Int], который был изначально.

http://ideone.com/bpLenc - не компилируется; говорит, x не Int

http://ideone.com/MlYeRN - всё в порядке, но и каст explicitly

[xeno-by.livejournal.com]

Вот, что пишет -Xlog-implicits:

13:33 ~/Projects/Kepler_snippet00/sandbox (topic/snippet00)$ scalac -Xlog-implicits Test.scala 
Test.scala:3: safeCast is not a valid implicit value for L.this.x.type => ?{def *: ?} because:
inferred type arguments [X,L.this.x.type,X] do not conform to method safeCast's type parameter bounds [X,Y,_ >: X <: Y]
  case class L[X](val x: X) { def double[_ >: X <: Int] = x*2 }

Сейчас подумаю, почему так.

[xeno-by.livejournal.com]

Ну в плане оно-то да, что X это не подтип x.type. Но почему оно x.type не расширяет до X - это от меня ускользает. Если не лень, можешь спросить вот тут: http://groups.google.com/group/scala-language.

[sassa-nf.livejournal.com]

переписываем, чтобы не было путаницы с X

    implicit def safeCast[Z,Y, _ >: Z <: Y]( z:Z ):Y = z.asInstanceOf[Y]
    case class L[X](val x: X) { def double[_ >: X <: Int] = x*2 }

safeCast is not a valid implicit value for L.this.x.type => ?{val *: ?} because:
incompatible: (z: X)X does not match expected type L.this.x.type => ?{val *: ?}
safeCast is not a valid implicit value for => L.this.x.type => ?{val *: ?} because:
incompatible: (z: X)X does not match expected type => L.this.x.type => ?{val *: ?}

а почему он говорит (z: X)X? Это он о чём? Что Z и Y ему одним типом кажутся в том контексте?

Ок, поспрашиваю.

[xeno-by.livejournal.com]

Стоп, подожди. А откуда компилятору знать, что у X есть мембер *?

[xeno-by.livejournal.com]

Он говорит (z: X)X потому, что это сигнатура метода safeCast с выведенными аргументами.

Причем здесь сигнатура? Когда компилятор не находит мембера, он ищет имплисит конвершн, преобразующий ресивер в нечто, что содержит нужный мембер. Как вот тут: implicit value for L.this.x.type => ?{val *: ?}.

Так как у Y нет мембера * (в силу того, что тот экзистенциальный тип, как мы выяснили, не влияет на тайп инференс), то соответственно safeCast не соответствует нужной сигнатуре.

[sassa-nf.livejournal.com]

ну это совсем странно. или не очень понятно.

    implicit def safeCast[Z,Y, _ >: Z <: Y]( z:Z ):Y = z.asInstanceOf[Y]
    def asInt( x: Int ): Int = x
    case class L[X](val x: X) { def double[_ >: X <: Int]: Int = asInt(x)*2 }

a.this.safeCast is not a valid implicit value for X => Int because:
incompatible: (z: X)X does not match expected type X => Int
a.this.safeCast is not a valid implicit value for => X => Int because:
incompatible: (z: X)X does not match expected type => X => Int
...(и ещё куча)

тут уже я даже сказал, чему x должен быть равен. На входе в asInt должен быть Int, почему не пробует safeCast с Z=X, Y=Int?

[sassa-nf.livejournal.com]

тут ещё оказывается, что несмотря на одинаковый синтаксис, в double[ _ >: X <: Int ] запись интерпретируется по другим законам, не связанными с existential types. (не компилируется перезапись по "законному" раскрытию того типа: double[ T forSome { type T >: X <: Int } ])

внезапно.

[lomeo.livejournal.com]

А, точно. Так же гораздо проще.

[sassa-nf.livejournal.com]

     case class L[X](val x:X) {
        def double[P >: X <: Int]: Int = (x:P) * 2
    }

(this scala awesomeness brought to you courtesy of Roland Kuhn)

(всё ещё жаль, что не догадывается, что x is Int, но уже значительно лучше!)

[ivan-gandhi.livejournal.com]

Funny, how much effort it took to figure out this specific format.
And it involved great minds, too. :)

[sassa-nf.livejournal.com]

Great to listen to great minds!

But frustrating that you need to know which way will work (vs which way is correct)