非遞推lambda微積分函數

Question

如何在不使用lambda演算遞歸的情況下編寫階乘函數？意思就是數學符號不能在任何特定的編程語言中實現。

Answer 1

如果「不使用遞歸的」你的意思是不一般的遞歸和 因此沒有固定點（或自申請），我們可以簡單地觀察到階乘函數是原始遞歸（即，迭代，在本質），並且通過迭代（由教會數字提供）和對，存在非常普遍和簡單的原始遞歸編碼。 我會討論一個非常具有啓發性的一般情況。 假設< M，N>是對的一些編碼，並且讓fst和snd是相關聯的投影（ ）。例如，可以定義

<M,N> = λz. z M N 
fst = λp. p (λxy.x) 
snd = λp. p (λxy.y) 

假設爲具有原始遞歸定義（不帶參數的 爲簡單起見）

f(0) = a 
f(x+1) = h(x,f(x)) 

其中和h已經被定義

。

總的想法是使用輔助函數f '其中

     f'(x) = <x,f(x)> 

所以，F'（0）= < 0時，>，和給定的一對p = < X，F（X ）> = f'（x），我們通過計算第一個組件 的後繼並將h應用於這對參數（即，利用以下優點來構建 下一對< x + 1，f（x + 1）我們的 編碼對，只是等於將連續h作爲輸入傳遞給對p）。

總結，

next = λp.< succ (fst p), p h> 

最後，計算F（N），我們需要從< 0，一>，然後採取第二組分迭代n次函數下 開始：

f = λn. snd (n next <0,a>) 

Answer 2

我沒有說什麼我不是那個意思

通過「不使用遞歸的」您一定意味着

「沒有一個函數的名字自稱 」

無論如何，讓我們寫階乘

fact := λn. zero? n one (mult n (fact (dec n)))

現在，我們並不特別在意在本示例中約爲zero?,mult,dec或甚至one;你可以實現那些對自己的 - 我們只是想去掉粗體，通過名遞歸，

... fact (dec n)

要做到這一點，最簡單的方法是將一個拉姆達適用於自身 - 滿足üCombinator的

現在

U := λf. f f 

，我們可以換我們原來的表達拉姆達以及應用U

fact := U (λf. λn. zero? n one (mult n (??? (dec n))))

但是我們怎麼落實到位fact ??? - 回想一下，f是對外部lambda本身的引用，所以爲了在下一次「迭代」中得到相同的結果，我們必須將f應用於自身，就像U所做的那樣 - 事實上，您可以想到U作爲一種鏡子，你的功能可以反射回那個鏡子以便重現;只是這一次，不使用名稱^ _^

fact := U (λf. λn. zero? n one (mult n (f f (dec n))))

是的，沒錯，但更精明會發現，你可以利用鏡子（ü）直接拉姆達裏面，太

fact := U (λf. λn. zero? n one (mult n (U f (dec n))))

---

擴大無u

我們知道如何擴大內 - 我們寫的是辦法在第一時間

fact := U (λf. λn. zero? n one (mult n (f f (dec n))))

現在擴大外ü

fact := (λf. λn. zero? n one (mult n (f f (dec n)))) (λf. λn. zero? n one (mult n (f f (dec n))))

---

工作的呢？

所有教堂的數字表示爲＃N

fact := U λf. λn. zero? n #1 (mult n (U f (dec n))) 

fact #4 

U (λf. λn. zero? n #1 (mult n (U f (dec n))) #4 

(λf. f f) (λf. λn. zero? n #1 (mult n (U f (dec n))) #4 

(λf. λn. zero? n #1 (mult n (U f (dec n))) (λf. λn. zero? n #1 (mult n (U f (dec n))) #4 

(λn. zero? n #1 (mult n (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec n))) #4 

zero? #4 #1 (mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (dec #4))) 

zero? #4 #1 (mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (deC#4))) 

// (zero? #4); false; returns second argument 
(mult #4 (U (λf. λn. zero? n #1 (mult n (U f (dec n))) (deC#4))) 

// which is #4 * ... 
(U (λf. λn. zero? n #1 (mult n (U f (dec n))) (deC#4)) 

// which is ... 
(U (λf. λn. zero? n #1 (mult n (U f (dec n))) #3) 

// which is equivalent to... 
fact #3 

// so ... 
(mult #4 (fact #3)) 

// repeating this pattern ... 
(mult #4 (mult #3 (fact #2)) 
(mult #4 (mult #3 (mult #2 (fact #1))) 
(mult #4 (mult #3 (mult #2 (mult #1 (fact #0)))) 
(mult #4 (mult #3 (mult #2 (mult #1 #1)))) 
(mult #4 (mult #3 (mult #2 #1))) 
(mult #4 (mult #3 #2)) 
(mult #4 #6) 
#24 

---

示範在JavaScript

來吧，查看在U組合子的力量與你自己的眼球！

const U = 
 
    f => f (f) 
 
    
 
const fact = 
 
    U (f => n => 
 
    n === 0 ? 1 : n * U (f) (n - 1)) 
 
    
 
console.log (fact (4)) // 24

並再次作爲一個純粹的lambda表達式

console.log (
 
    (f => n => n === 0 ? 1 : n * f (f) (n - 1)) 
 
    (f => n => n === 0 ? 1 : n * f (f) (n - 1)) 
 
     (4) 
 
) // 24

相互遞歸

上面的代碼片段演示了這個遞歸過程的一個非常重要的屬性：它是mutually recursive。如你所見，實際上有兩個（雖然是相同的）驅動遞歸的函數; A呼叫B，B呼叫A - 但是在U組合器的情況下，只有一個函數可以應用於自身，所以它實際上啓用了direct recursion - lambda確實使用它的參數自行調用，而不是它的名字（lambdas沒有一個名字叫）

---

是？

Because I said so

在U組合子是有點麻煩，因爲它希望用戶「反映」的功能，以復發 - 如果我們能夠提供外拉姆達與函數是鏡子本身是什麼？

U := λf. f f 
Y := λg. U (λf. g (U f)) 

我要告訴你的樣子了定義，但在兩行只是讓你可以看到「鏡子」和它們的位置

 /g, user's function 
     /
     // outer reflection 
    // 
Y := λg. U (λf. ... ) 
       g (U f) 
       \ 
        \ call g with inner reflection

所以，現在，只要你申請Y任何拉姆達（克），其參數成爲函數來計算拉姆達本身 - 改變fact到

fact := Y (λf. λn. zero? n one (mult n (f (dec n))))

---

擴大Ÿ

Y := λg. U (λf. g (U f))    // expand inner U 
Y := λg. U (λf. g (f f))    // expand outer U 
Y := λg. (λf. g (f f)) (λf. g (f f))

這是你在維基百科看到有定義;只是字母改名

---

我剛剛有了一個深刻的發現

推導值Y U側，我看到的東西我從來沒有見過的 - 一個隱藏乙

Y := λg. U (λf. g (U f)) 

B := λf. λg. λx. f (g x) 

Y' := λg. U (B g U) 

一我見過的最美麗的東西 - and it works too;不，我們應該有任何理由認爲它不會......

#lang lazy 

(define B (λ (f) 
      (λ (g) 
       (λ (x) 
       (f (g x)))))) 

(define U (λ (f) 
      (f f))) 

(define Y (λ (g) 
      (U ((B g) U)))) 

(define fact (Y (λ (f) 
        (λ (n) 
        (if (= n 0) 
         1 
         (* n (f (sub1 n)))))))) 

(fact 4) ;; 24 

---

Haskellers

你見過Ÿ表示爲？

Y = U . (. U) 
    where U f = f f