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

[www-dikinet.livejournal.com]

Че-то всё не по-русски?

[xeno-by.livejournal.com]

А какой у флаттена тут возвращаемый тип?

[lomeo.livejournal.com]

scala> sealed abstract class <:<[-S, +T] extends Function1[S, T]
defined class $less$colon$less

scala> implicit def canCast[F <% T, T]: (F <:< T) = new (F <:< T) { def apply(a: F): T = a }
canCast: [F, T](implicit evidence$1: F => T)<:<[F,T]

scala> case class L[X](val x: X) { def double[Y](implicit transformer: X <:< Int) = x*2 }
defined class L

scala> L(42).double
res16: Int = 84

scala> L("a").double
<console>:26: error: diverging implicit expansion for type <:<[String,Int]
starting with method canCast
              L("a").double

А вот с

implicit def canCast[F <: T, T]: (F <:< T) = new (F <:< T) { def apply(a: F): T = a }

уже не работает…

P.S. Сорри за множественные правки: сначала больше-меньше побилось в html, затем заметил, что лишний кусок прихватил.

[vit-r.livejournal.com]

define methods that would only work if X satisfies certain conditions

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