Typelevel hackery tricks in Scala

There’s a lot of talks about typelevel things in Scala. Shapeless has gained huge amount of attention lately. There are a lot of cool typelevel tricks out there, coined by Miles Sabin, the type astonaut. Some even say, he does not exist at the runtime. Anyway, I’d like to collect some of those tricks here, for future reference. I’m also doing this to get a better understanding of those tricks.

Table

Trick Short description
Unboxed Tagged Types Something like Haskell’s newtype, but better.
Dependent types Have types depend on values
Unapply Reduce needed type annotations by guiding scala’s type inference
Ambiguous implicits A way to guarantee that a polymorphic function will not return some specific type

Unboxed Tagged Types

There’s already a great explanation, including the needed intuition, in Eric Torreborre’s blog. This technique allows for having some typelevel guarantees on the values. Here’s a motivating example. Say, you want to create a function, which operates on positive doubles. Here’s how you could go about this:

def log(i: Double): Option[Double] =
    if(i > 0) scala.math.log(i)
    else None

It’s a totally ok way to do this, but imagine, you want several such functions, and you want to chain them afterwards. You might create something like

def positive(i: Double): Option[Double] =
    if(i > 0) Some(i) else None

def log(i: Double) = scala.math.log(i)

//positive(x) map log map func2 ...

Let’s try that out:

scala> positive(5) map log
res0: Option[Double] = Some(1.6094379124341003)

scala> positive(-1) map log
res1: Option[Double] = None

But what would prevent someone from just

scala> log(-1)
res2: Double = NaN

You would probably like to express your intents in types, if possible trying not to overuse single-valued case-classes and boxing/unboxing values. Here’s a possible solution:

import scalaz._, Scalaz._
trait Positive
def positive(i: Double): Option[Double @@ Positive] =
    if(i > 0) Some(Tag[Double, Positive](i)) else None

def log(i: Double @@ Positive) = scala.math.log(i)

//positive(x) map log map func2 ...

Here positive is the so-called smart constructor. Let’s try it out. As before:

scala> positive(5) map log
res1: Option[Double] = Some(1.6094379124341003)

scala> positive(-1) map log
res2: Option[Double] = None

But now:

scala> log(-1.0)
<console>:16: error: type mismatch;
 found   : Double(-1.0)
 required: scalaz.package.@@[Double,Positive]
              log(-1.0)
                   ^

Here’s an implementation of this thing in scalaz. Scalaz uses this technique a lot, specifically for differentiating between different typeclass instances for the same type. For example, there are different semigroups for Int (default, under addition), Int @@ Multiplication, Int @@ MaxValue, Int @@ MinValue.

Dependent types

With the next scala version and some shapeless magic stuff like this is possible:

scala> import shapeless.SingletonTypes._
import shapeless.SingletonTypes._

scala> val evidence: ^(5.0 > 0) = true
evidence: Boolean(true) = true

scala> val evidence: ^(-1.0 > 0) = true
<console>:13: error: type mismatch;
 found   : Boolean(true)
 required: Boolean(false)
       val evidence: ^(-1.0 > 0) = true
                                 ^

I was not able to push it to the level of functions though:

scala> def positive(res: Double): Double = {
     |     val evidence: ^(res > 0) = true
     |     res
     | }
error: exception during macro expansion: 
scala.tools.reflect.ToolBoxError: reflective compilation has failed: 

object > is not a member of package res
	at scala.tools.reflect.ToolBoxFactory$ToolBoxImpl$ToolBoxGlobal.throwIfErrors(ToolBoxFactory.scala:314)
	at scala.tools.reflect.ToolBoxFactory$ToolBoxImpl$ToolBoxGlobal.compile(ToolBoxFactory.scala:250)
	at scala.tools.reflect.ToolBoxFactory$ToolBoxImpl.compile(ToolBoxFactory.scala:409)
	at scala.tools.reflect.ToolBoxFactory$ToolBoxImpl.eval(ToolBoxFactory.scala:412)
	at scala.reflect.macros.contexts.Evals$class.eval(Evals.scala:16)
	at scala.reflect.macros.contexts.Context.eval(Context.scala:6)
	at shapeless.SingletonTypeMacros$class.eval(snat.scala:40)
	at <macroinvokers>.SingletonTypeMacros_invoker_2107abc6e1de498e8212e5249a547bda.eval(compileLateSynthetic-0480dadcf9774235b72d647816247166.scala:37)
	at shapeless.SingletonTypeMacros$class.singletonType(snat.scala:44)
	at <macroinvokers>.SingletonTypeMacros_invoker_2107abc6e1de498e8212e5249a547bda.singletonType(compileLateSynthetic-0480dadcf9774235b72d647816247166.scala:37)

Anyway, this makes typelevel hanoi towers extremely easy.


Ambiguous implicits

Enforcing that we don’t get a specified return type.

As pointed out by Miles, this works because the ambiguous implicits (nsubAmbig1 and nsubAmbig2) are more specific (specification).

Unapply trick

I’ve recently answered one of the SO questions, using this technique. Here’s the implementation in scalaz repo. The trick allows for reducing the number of type annotations by guiding scala’s type inference.

Comments

blog comments powered by Disqus