The question we are trying to answer in this post is:
How easy can we make it to construct a natural transformation?
That is, we can define an ordinary anonymous function in Scala for rank-1 types using some succinct special syntax:
val a: Char => Boolean = _.isUpper val b = (_: Char).isUpper val c = (c: Char) => c.isUpper
We run into problems when we proceed to natural transformations. We are not able to define a function that maps an Option[T] to List[T] for every T, for example. If this is not obvious, try to define `toList` so that the following compiles:
val toList = ... val a: List[Int] = toList( Some(3) ) assert( List(3) == a ) val b: List[Boolean] = toList( Some(true) ) assert( List(true) == b )
In order to define a natural transformation M ~> N (here, M=Option, N=List), we have to create an anonymous class because Scala doesn’t have literals for quantified functions. So, we’ll explore in this post is how close we can get to a literal syntax.
First, one representation of a natural transformation in Scala looks like:
trait ~>[-A[_], +B[_]] {
def apply[T](a: A[T]): B[T]
}
We use a strict argument here, but you could certainly make it call-by-name.
The filled in definition of toList in the motivating example using this representation is:
val toList = new (Option ~> List) {
def apply[T](opt: Option[T]): List[T] =
opt.toList
}
For any type T, this will turn an Option[T] into an List[T] by calling toList.
There is no simpler way to write this in plain Scala. We can’t write this as a function literal. There is no type that you can give a function literal such that you can apply `toList` to an arbitrary `Option[T]` and get back a `List[T]`. For example:
def toList[T](opt: Option[T]): List[T] = opt.toList val hOptFun = toList _
The type of hOptFun is actually `Option[Nothing] => List[Nothing]` and not the quantified function `[T] Option[T] => List[T]`. Try applying hOptFun to a value:
hOptFun(Some(3))
error: type mismatch;
found : Int(3)
required: Nothing
hOptFun(Some(3))
^
What can we do? Well, we can look to abstract types for some help. The idea is to define a trait representing a quantified type parameter where the quantified type is represented by an abstract type.
First, the trait:
trait Param[A[_], B[_]] {
type T
def in: A[T]
def ret(out: B[T]): Unit
def ret: B[T]
}
We will use this like so:
val f = (p: Param[Option, List]) => p.ret( p.in.toList )
and define an implicit conversion from `Param[A, B] => Unit` to `A ~> B` :
object Param {
implicit def pToT[A[_], B[_]](p: Param[A,B] => Unit): A~>B = new (A ~> B) {
def apply[s](a: A[s]): B[s] = {
val v: Param[A,B] { type T = s} =
new Param[A,B] { type T = s
def in = a
private var r: B[T] = _
def ret(b: B[T]) {r = b}
def ret: B[T] = r
}
p(v)
v.ret
}
}
}
We could add logic to the original scheme to ensure `r` gets set exactly once in the mutable case, although this would be a runtime error and not a compile error. If we had dependent method and function types, we could keep it immutable:
trait Param[A[_]] {
type T
def in: A[T]
}
object Param {
implicit def pToT[A[_], B[_]](f: (p: Param[A]) => B[p.T]): A~>B = new (A ~> B) {
def apply[s](a: A[s]): B[s] = {
val v: Param[A] { type T = s} = new Param[A] { type T = s
def in = a
}
f(v)
}
}
}
// usage:
val f = (p: Param[Option, List]) => p.in.toList
So, we didn’t exactly succeed. In the absence of some help from the compiler, we’re stuck with some verbosity.
In part 8, we will apply natural transformations to higher-kinded heterogeneous lists. There it will be useful to define some auxiliary types and an identity transformation :
object ~> {
type Id[X] = X
trait Const[A] { type Apply[B] = A }
implicit def idEq : Id ~> Id = new (Id ~> Id) { def apply[T](a: T): T = a }
}
Related links:
http://article.gmane.org/gmane.comp.lang.scala.user/697
http://existentialtype.net/2008/05/26/revisiting-higher-rank-impredicative-polymorphism-in-scala/
Apocalisp 
Any way to do the same for partial functions? So that an object (Option ~>? List) will be an instance of a partial function?
But Option to List is total.
Yeah, I meant something in general. For a specific case, Option ~>? Id ({case Some(x) => x})
trait ~>?[F[_], G[_]] {
def apply[A](a: F[A]): Option[G[A]]
}
It seems toList (defined as instance of Option ~> List) cannot be used as a function everywhere:
scala> Array(Some(1), Some(2)).map(toList)
:8: error: type mismatch;
found : java.lang.Object with ~>[Option,List]
required: (Some[Int]) => ?
Array(Some(1), Some(2)).map(toList)
^
~> doesn’t extend Function1. This would not make sense, since it is more general than Function1. It has a type parameter on ‘apply’ that Function1 does not have.
You can define an implicit conversion to Function1 of course:
implicit def toFun1[A[_],B[_],T](f: A ~> B): A[T] => B[T] =
(x: A[T]) => f[T](x)
Then,
scala> Array(Some(1), Some(2)).map(toList)
res0: Array[List[Int]] = Array(List(1), List(2))
If ~> gives me just objects that I can use as functions, but not pass as functions, then It’s less useful.
def toList[A](opt: Option[A]) = opt.toList
Seems more strait forward then.
Sure, if you don’t need a value, def is fine. But just like a value of type A => B is useful, so is a value representing the type [T] A[T] => B[T]. At a minimum, you can’t compose defs, but you can compose instances of Function1 and ~>. For a more detailed example, consider the following.
In your example, you are calling a map function that is essentially:
def map[F[_], B](f: F[A], g: A => B): F[B]
where F == Array and g has type Option[Int] => List[Int]. Nothing requires ~> there. However, let’s say you have a data structure representing a pair where both elements share a type constructor:
case class KTuple2[ F[_], A, B ](a: F[A], b: F[B])
For example:
// these are so that we get Option[T] as the type
// and not Some[T] or None
def some[T](t: T): Option[T] = Some(t)
def none[T]: Option[T] = None
scala> val a = KTuple2( some(3), some("asdf") )
a: KTuple2[Option,Int,java.lang.String] = KTuple2(Some(3),Some(asdf))
scala> val b = KTuple2( some(3), none[String] )
b: KTuple2[Option,Int,String] = KTuple2(Some(3),None)
One useful transformation looks like:.
def transform[F[_], A, B, G[_]] (k: KTuple2[F, A, B], g: F ~> G): KTuple2[G, A, B] =
KTuple2( g(k.a), g(k.b) )
This applies the provided natural transformation to each element, preserving the underlying type parameter, but with a new type constructor.
As you might guess, an example is to apply toList:
scala> transform( a, toList )
res1: KTuple2[List,Int,java.lang.String] = KTuple2(List(3),List(asdf))
scala> transform( b, toList )
res2: KTuple2[List,Int,String] = KTuple2(List(3),List())
You cannot pass a ‘def’ (it is not a value) nor a Function1 (it’s ‘apply’ has no type parameters) to ‘transform’. You need a type like ~>. Generalize KTupleN to KList like TupleN generalizes to HList and you have the subject of part 8.