Scala, Folds, and Universal Quantification

Church encoding of data types is a fun exercise. Something that blew my mind while learning functional programming was that a data structure is completely defined by its catamorphism. So for example, foldr is not just another function over lists. The list data type is the foldr function.

For example, in Haskell, we can encode pairs as this function:

pair x y f = f x y

A pair is then a higher-order function. It takes a function with two arguments and yields the result of applying that function to the two elements with which we constructed the pair.

Doing this in Scala is not quite as pretty. Here’s an attempt:

def pair[A,B,C](a: A, b: B) = (f: (A,B) => C) => f(a,b)

Seems to work:

scala> pair(10,20)(_ + _)
res1: Int = 30

However, that C type parameter is going to give us problems if we try this:

scala> val x = pair(10,20)
x: ((Int, Int) => Nothing) => Nothing = <function>

scala> x(_ + _)
<console>:12: error: type mismatch;
 found   : Int
 required: Nothing
       x(_ + _)
           ^

Oops. It looks like Scala needs all of the type parameters to a function up front. In other words, it seems like its type system is unable to unify the types (∀ a. a -> (∀ b. b -> b)) and (∀ a b. a -> b -> b). Is this accurate? If you know the answer, please comment below.

However, we can be saved with anonymous type syntax (which, I’m told, unfortunately makes use of reflection):

def pair[A,B](a: A, b: B) = new { def apply[C](f: (A,B) => C) = f(a,b) }

Now this works as expected:

scala> val x = pair(1,2)
x: java.lang.Object{def apply[C]((Int, Int) => C): C} = $anon$1@ad8dbc

scala> x(_ + _)
res13: Int = 3

Sweet! Let’s do this for lists. Here’s the Haskell.

nil p z = z
cons x xs p z = p x (xs p z)

Testing this in GHCi:

Prelude> let xs = cons 1 (cons 2 (cons 3 nil))
Prelude> xs (+) 0
6

No sweat. Now, let’s do this in Scala. This is the best I’ve come up with:

def nil =
  new { def apply[A](a: A) =
    new { def apply[B](b: B) = b }}
def cons[A](x: A) =
  new { def apply[B](xs: ((A => B => B) => B => B)) =
    (f: A => B => B) => (b:B) => f(x)(xs(f)(b)) }

This doesn’t completely work:

scala> val xs = cons(1)(cons(2)(cons(3)(nil)))
<console>:20: error: type mismatch;
 found   : java.lang.Object{def apply[A](A): java.lang.Object{def apply[B](B): B}}
 required: ((Int) => (?) => ?) => (?) => ?
       val xs = cons(1)(cons(2)(cons(3)(nil)))
                                        ^

Scala is not able to unify those two types. Let’s help it along:

def objToFun[A,B](o: {def apply[A](a: A): {def apply[B](b: B): B}}) = (a: A) => (b: B) => o(a)(b)
def nilp[A,B] = objToFun[A => B => B, B](nil)

With a little annotation, we can now create a list that has the right type:

scala> cons(3)(cons(2)(cons(1)(nilp[Int,Int])))
xs: ((Int) => (Int) => Int) => (Int) => Int = <function>

scala> xs(x => y => x + y)(0)
res44: Int = 6

Not terrible, but can we do better? Can this be done without the anonymous type syntax? Is using that syntax necessarily bad? Why? Could we modify Scala to get a nicer notation for anonymous function types? Is rank-2 polymorphism required for that, or can we convince the compiler to move universal quantifiers to the left of a single arrow?

Advertisement