-
25-09-2019 - |
题
我一直在尝试如何在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编译器统一类型。
您可以定义零,以便给定上述定义以下编译吗?
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
这里, Endo
只是将映射到本身映射到本身的函数类型的类型(一个)(一个) 函数).
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的类型系统。因此,一旦创建的列表实际上折叠清单仍然很冗长,而且很乏味。这是比较的同等哈斯克尔:
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
不隶属于 StackOverflow