闭包和通用量化
闭包和通用量化
提问于 2010-04-09 01:56:34
我一直在努力研究如何在Scala中实现教堂编码的数据类型。它似乎需要rank-n类型，因为您需要一个forAll a. a -> (forAll b. b -> b)类型的一流const函数。
但是，我可以这样编码成对：
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)))回答 1
Stack Overflow用户
回答已采纳
发布于 2010-04-09 07:05:54
感谢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]#ApplyConst[A]是一个将每个类型映射到A的函数器。
下面是我们的列表类型：
type CList[A] = ({type f[x] = Fold[A,x]})#f ~> Endo在这里，Endo只是将类型映射到自身( endofunction)的函数类型的别名。
type Endo[A] = A ->: AFold是可以折叠列表的函数类型：
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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2602276
复制相关文章
相似问题
腾讯云开发者
