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?

Try this:

There is no need to actually name the

`C`

type in your example since it is exclusively used to determine the return type.Daniel:

The result type of the fold will then be Any, which is not exactly what we’re after.

How about this?

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

val x = pair(10,20)

x(_ + _) //30

Nevermind my previous comment, I have no idea what I’m doing :D

Again, we end up with Any. We want the fold over a pair to result in C.

I’ve managed to avoid the structural type for pairs, using a new trait “Closure”. See here: http://paste.pocoo.org/show/199304

I’ve managed to avoid the structural type for pairs and cons, using a new trait “Closure”. See here:

http://paste.pocoo.org/show/199307

However, I’ve not figured out how to define the empty list so that the types are unified. If you can get that working, I’ll buy you a beer.

http://gist.github.com/360425

Usage looks like:

val xs = cons(3)(cons(2)(cons(1)( nil )))

val str = xs( (x: Int) => pure( (y: String) => x + y) )("0")

val num = xs( (x: Int) => pure( (y: Int) => x + y) )(0)

Printing from the interpreter:

scala> str

res0: java.lang.String = 3210

`scala> num`

res1: Int = 6

Mark: The =>: type is exactly what I was missing. That’s brilliant.

See here on Stackoverflow for the solution:

http://stackoverflow.com/questions/2602276/closures-and-universal-quantification/2604057#2604057

Pingback: Non-empty lists « Higher Kinded Tripe