闭包和全称量化

Question

我一直在尝试在Scala中实现教会编码数据类型。似乎需要使用rank-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)))

- Apocalisp

---

这是有关Scala中Church数的一个观点：http://jim-mcbeath.blogspot.com/2008/11/practical-church-numerals-in-scala.html - Randall Schulz

Randall：那些是类型级别的教堂数。我所做的不在类型层面上。 - Apocalisp

就其价值而言，Scala方法有效地为您提供了排名n类型。 - Owen

Scala的方法并不能有效地给您提供rank-n类型，但是您可以以这种方式编码大量的rank-n类型。 - Apocalisp

Answer 1

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

我在问题中提到的“Closure”特质实际上是函子之间的自然变换。 这是“函数”概念的一般化。

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

这里，Endo只是将一种类型映射到自身的函数类型（一个Endofunction）的别名。

type Endo[A] = A ->: A

而 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 版本中，列表的构建和折叠（folding）是简洁且无噪音的。

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

- Apocalisp

---

这超出了我的舒适区！ - Andriy Drozdyuk