 Type-Level Programming in Scala, Part 7: Natural transformation literals

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 }
}

8 thoughts on “Type-Level Programming in Scala, Part 7: Natural transformation literals”

1. Ittay says:

Any way to do the same for partial functions? So that an object (Option ~>? List) will be an instance of a partial function?

• Rúnar says:

But Option to List is total.

• Ittay says:

Yeah, I meant something in general. For a specific case, Option ~>? Id ({case Some(x) => x})

• Rúnar says:

trait ~>?[F[_], G[_]] {
def apply[A](a: F[A]): Option[G[A]]
}

2. Ittay says:

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)
^

• Mark says:

~> 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))

• Ittay says:

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.

• Mark says:

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.