斯卡拉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]類型的普通號。

所以 - 如何定義加法？

來源

2016-04-22 zapadlo

我的第一個猜測是，它只能對於無類型的lambda微積分，其中value只是* somehting *，而function是從* something *到* something *的映射，所以我可以調用參數類型爲「a：Z - > Z」的函數f可能並不完全符合一個函數'f'：（Z - > Z） - >（Z - > Z）'我應用它。 – zapadlo

也許像「斯卡拉教會數字的添加」這樣的標題會更精確一些。 –

在斯卡拉完全可以實現教會的數字。這裏就是這樣的一個比較直觀的實現：

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數我會添加更多的評論。但考慮到上下文，我不確定在這種情況下要評論什麼。請隨時提問，我會添加更多解釋。

來源

2016-04-22 20:01:12

很漂亮。謝謝。 – 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))))

來源

2016-04-22 21:15:50 pedrofurla

斯卡拉lambda微積分

回答

相關問題