闭包和通用量化

我一直在努力研究如何在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)))

来源

2010-04-08 Apocalisp

这里有一个采取在斯卡拉Church数：HTTP：// jim- mcbeath.blogspot.com/2008/11/practical-church-numerals-in-scala.html – 2010-04-08 18:23:57

Randall：这些是类型级别的教堂数字。我正在做的不是类型的级别。 – Apocalisp 2010-04-08 19:34:06

对于它的价值，斯卡拉方法有效地给你排名n类型。 – Owen 2013-01-13 21:19:00

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

问题中的“闭包”特质实际上是函子之间的自然变换。这是“功能”概念的概括。

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

函数a -> b然后应该是这种性状的特殊化，在Scala的类型类别2个endofunctors之间的天然转化。

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的版本折叠是简洁，无噪音：

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

来源

2010-04-08 23:05:54 Apocalisp

这是超出我的舒适区！ – drozzy 2011-02-19 17:53:59

闭包和通用量化

回答

相关问题