scala - Scala 中的 lambda 演算

Question

好的，所以我正在尝试实现 basics of lambda calculus .就到这里了。

我的号码:

def zero[Z](s: Z => Z)(z: Z): Z = z
def one[Z](s: Z => Z)(z: Z): Z = s(z)
def two[Z](s: Z => Z)(z: Z): Z = s(s(z))

它们的部分(实际上，非)应用版本是这样的:

def z[Z]: (Z => Z) => (Z => Z) = zero _

在我继续之前，我定义了一些类型:

type FZ[Z] = Z => Z
type FFZ[Z] = FZ[Z] => FZ[Z]

很好， succ函数是这样的(应用顺序应该完全一样!我接受了定义 here ):

def succ[Z](w: FFZ[Z])(y: FZ[Z])(x: Z): Z = y((w(y))(x))

它的未应用版本变得如此可怕:

def s[Z]: FFFZ[Z] = successor _

请原谅，这里是缺少的类型:

type FFFZ[Z] = FFZ[Z] => FFZ[Z]
type FFFFZ[Z] = FFFZ[Z] => FFFZ[Z]

但我被困在 add功能。如果符合类型和定义(也采用 here)，它就像

def add[Z](a: FFFFZ[Z])(b: FFZ[Z]): FFZ[Z] =
  (a(s))(b)

但我要 a成为普通号码 FFZ[Z] .

那么 - 我如何定义加法？

Answer 1

在 Scala 中实现教堂数字是完全可能的。这是一种相当直接的实现:

object ChurchNumerals {

  type Succ[Z] = Z => Z
  type ChNum[Z] = Succ[Z] => Z => Z

  def zero[Z]: ChNum[Z] =
    (_: Succ[Z]) => (z: Z) => z

  def succ[Z] (num: ChNum[Z]): ChNum[Z] =
    (s: Succ[Z]) => (z: Z) => s( num(s)(z) )

  // a couple of church constants
  def one[Z] : ChNum[Z] = succ(zero)
  def two[Z] : ChNum[Z] = succ(one)

  // the addition function
  def add[Z] (a: ChNum[Z]) (b: ChNum[Z]) =
    (s: Succ[Z]) => (z: Z) => a(s)( b(s)(z) )

  def four[Z] : ChNum[Z] = add(two)(two)

  // test
  def church_to_int (num: ChNum[Int]): Int =
    num((x: Int) => x + 1)(0)

  def fourInt: Int = church_to_int(four)

  def main(args: Array[String]): Unit = {
    println(s"2 + 2 = ${fourInt}")
  }
}

编译和打印:

$ scala church-numerals.scala
2 + 2 = 4

如果我要从头开始解释教会数字，我会添加更多评论。但考虑到上下文，我不确定在这种情况下该评论什么。请随时提问，我会添加更多解释。