foldr.scala

// in comments, the syntax:
//   [A](B => C)
// represents a quantified function literal parameterized by type A

object Z
{
	// The main type, a quantified function object
	trait Q[M[_], N[_]] { def apply[C](m: M[C]): N[C] }
	
		// Helper Types
	
	// Alias for a simple quantified function that ignores its type parameter
	type =>:[A,B] = Q[Const[A]#Apply, Const[B]#Apply]
	// simple quantified function that has the same type for its argument and return
	type S[A] = A =>: A
	// partial type application
	trait PApp[A[_,_], B] { type Apply[C] = A[B,C] }
	// constant type constructor, ignores the parameter B and returns A
	trait Const[A] { type Apply[B] = A }
	// A fold as a simple quantified type
	type Fold[A, B] = A =>: B =>: B
	// F[A] = [B]( Fold[A,B] => [C](B => B) )
	type F[A] = Q[PApp[Fold, A]#Apply, S]
	
	// Converts a function to a quantified function that ignores its type parameter
	implicit def pure[A,B](f: A => B): A =>: B =
		new =>:[A,B] { def apply[C](a: A): B = f(a) }
		
	// [B]( (Int => B => B) => [C](B => B) )
	def nil[A]: F[A] = new F[A] {
		def apply[B](f: Fold[A,B]): S[B] = (b: B) => b // pure gets applied here
	}
	// [A]( A => [B]( F[A] => F[A])
	def cons[A](x: A): S[F[A]] =
		new S[F[A]] { def apply[C](xs: F[A]): F[A] =
			new F[A] { def apply[B](f: Fold[A,B]): S[B] = 
				(b:B) =>  f(x)(xs(f)(b))  // pure gets applied here
			}
		}
		
	val xs = cons(3)(cons(2)(cons(1)( nil )))
	// the only noise we need is 'pure' on the inner literal
	// the outer literal is converted ok, however
	val str = xs( (x: Int) => pure( (y: String) => x + y) )("0")
	val num = xs( (x: Int) => pure( (y: Int) => x + y) )(0)
	
	// for running as an application
	def main(args: Array[String])
	{
		println(str)
		println(num)
	}
}
/* or, at the interpreter
scala> Z.str
res0: java.lang.String = 3210

scala> Z.num
res1: Int = 6
*/