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

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/

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

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

  2. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s