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/

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.