闭包和通用量化

我一直在尝试研究如何在 Scala 中实现 Church-encoded 数据类型。看起来它需要 n 级类型，因为你需要一个一流的const类型函数forAll a. a -> (forAll b. b -> b).

然而，我能够这样对对进行编码：

import scalaz._

trait Compose[F[_],G[_]] { type Apply = F[G[A]] }

trait Closure[F[_],G[_]] { def apply[B](f: F[B]): G[B] }

def pair[A,B](a: A, b: B) =
  new Closure[Compose[({type f[x] = A => x})#f,
                      ({type f[x] = B => x})#f]#Apply, Id] {
    def apply[C](f: A => B => C) = f(a)(b)
  }

对于列表，我能够编码cons:

def cons[A](x: A) = {
  type T[B] = B => (A => B => B) => B
  new Closure[T,T] {
    def apply[B](xs: T[B]) = (b: B) => (f: A => B => B) => f(x)(xs(b)(f))
  }
}

然而，空列表的问题更大，我无法让 Scala 编译器统一类型。

你能否定义 nil，以便根据上面的定义，下面的代码可以编译？

cons(1)(cons(2)(cons(3)(nil)))

感谢 Mark Harrah 完成了这个解决方案。诀窍是Function1标准库中没有以足够通用的方式定义。

我在问题中的“闭包”特征实际上是函子之间的自然转换。这是“函数”概念的概括。

trait ~>[F[_],G[_]] { def apply[B](f: F[B]): G[B] }

一个功能a -> b那么应该是这个特性的特化，是 Scala 类型类别上两个内函子之间的自然转换。

trait Const[A] { type Apply[B] = A }
type ->:[A,B] = Const[A]#Apply ~>: Const[B]#Apply

Const[A]是一个函子，将每种类型映射到A.

这是我们的列表类型：

type CList[A] = ({type f[x] = Fold[A,x]})#f ~> Endo

Here, Endo只是将类型映射到其自身的函数类型的别名（内功能 http://en.wikipedia.org/wiki/Endofunction).

type Endo[A] = A ->: A

And Fold是可以折叠列表的函数类型：

type Fold[A,B] = A ->: Endo[B]

最后，这是我们的列表构造函数：

def cons[A](x: A) = {
  new (CList[A] ->: CList[A]) {
    def apply[C](xs: CList[A]) = new CList[A] {
      def apply[B](f: Fold[A,B]) = (b: B) => f(x)(xs(f)(b))
    }
  }
}

def nil[A] = new CList[A] {
  def apply[B](f: Fold[A,B]) = (b: B) => b
}

需要注意的是，需要将 (A ->: B) 显式转换为 (A => B) 以帮助 Scala 的类型系统顺利进行。因此，在创建后实际折叠列表仍然非常冗长和乏味。这是用于比较的等效 Haskell：

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

Haskell 版本中的列表构造和折叠非常简洁且无噪音：

let xs = cons 1 (cons 2 (cons 3 nil)) in xs (+) 0