scala – 关闭和普遍量化

发布时间：2020-12-16 09:10:09 所属栏目：安全来源：网络整理

导读：我一直在努力解决如何在 Scala中实现Church编码的数据类型.似乎它需要等级n类型,因为您将需要一个类型为A的所有a类的第一类const函数. a – (所有b.b – b). 但是,我能够编码对： import scalaz._trait Compose[F[_],G[_]] { type Apply = F[G[A]] }trait Cl

我一直在努力解决如何在 Scala中实现Church编码的数据类型.似乎它需要等级n类型,因为您将需要一个类型为A的所有a类的第一类const函数. a – > (所有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

在这里,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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!