斯卡拉lambda微积分
问题描述:
好的,所以我试图实现basics of lambda calculus。在这里。斯卡拉lambda微积分
我的号码:
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]
类型的普通号。
所以 - 如何定义加法?
答
在斯卡拉完全可以实现教会的数字。这里就是这样的一个比较直观的实现:
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
如果我来解释从头Church数我会添加更多的评论。但考虑到上下文,我不确定在这种情况下要评论什么。请随时提问,我会添加更多解释。
+0
很漂亮。谢谢。 – zapadlo
答
我已经编码了数字,布尔和对:https://github.com/pedrofurla/church/blob/master/src/main/scala/Church.scala遵循教会的风格。
我注意到的一件事是使用curried函数语法比使用多个参数列表容易得多。一些有趣的片段
type NUM[A] = (A => A) => A => A
def succ [A]: NUM[A] => NUM[A] = m => n => x => n(m(n)(x))
def zero [A]: NUM[A] = f => x => x
def one [A]: NUM[A] = f => x => f(x)
def two [A]: NUM[A] = f => x => f(f(x))
def three [A]: NUM[A] = f => x => f(f(f(x)))
def plus [A]: (NUM[A]) => (NUM[A]) => NUM[A] = m => n => f => x => m(f)(n(f)(x))
现在打印出来(非常类似于Antov Trunov的溶液):
def nvalues[A] = List(zero[A], one[A], two[A], three[A])
val inc: Int => Int = _ + 1
def num: (NUM[Int]) => Int = n => n(inc)(0)
def numStr: (NUM[String]) => String = n => n("f (" + _ + ") ")("z")
一些输出:
scala> println(nvalues map num)
List(0, 1, 2, 3)
scala> println(nvalues map numStr) // Like this better :)
List(z, f (z) , f (f (z)) , f (f (f (z))))
我的第一个猜测是,它只能对于无类型的lambda微积分,其中value只是* somehting *,而function是从* something *到* something *的映射,所以我可以调用参数类型为“a:Z - > Z”的函数f可能并不完全符合一个函数'f':(Z - > Z) - >(Z - > Z)'我应用它。 – zapadlo
也许像“斯卡拉教会数字的添加”这样的标题会更精确一些。 –