2017-10-13 145 views
2

你如何製作一個匿名遞歸函數(例如階乘n的簡單事情?)我聽說過它是可能的,但不知道如何使它在OCaml中工作。OCaml中的匿名遞歸函數

let a = 
    fun x -> .... 

我只是不知道如何繼續下去......

回答

4

這裏是只使用匿名函數階乘的定義:

let fact = 
    (fun f -> (fun x a -> f (x x) a) (fun x a -> f (x x) a)) 
    (fun f n -> if n < 2 then 1 else n * f (n - 1)) 

它需要使用-rectypes的旗。

這裏顯示出它的工作原理會話:

$ rlwrap ocaml -rectypes 
     OCaml version 4.03.0 

let fact = 
    (fun f -> (fun x a -> f (x x) a) (fun x a -> f (x x) a)) 
    (fun f n -> if n < 2 then 1 else n * f (n - 1));; 
val fact : int -> int = <fun> 
# fact 8;; 
- : int = 40320 

我通過這裏查找在Y Combinator的有點被騙:Rosetta Code: Y Combinator

更新

免責聲明:您會做更好的閱讀使用lambda微積分,固定點和Y Combinator,而不是從我那裏獲取信息。我不是理論家,只是一個不起眼的修煉者。

以下的實際計算幾乎是不可能的(但絕對值得我確信)。但高層次的想法就是這樣。

定義的第一行是Y Combinator,它通常計算函數的固定點。恰巧遞歸函數是從函數到函數的函數的固定點。

因此,第一個目標是找到其固定點是階乘函數的函數。這是定義的第二行。如果你給它一個類型爲int -> int的函數,它會讓你回到int -> int類型的另一個函數。如果你給它的階乘函數,它會讓你回到階乘函數。這意味着階乘函數是它的固定點。

那麼,當你將Y Combinator應用到這個函數時,你確實得到了階乘函數。

+0

你能解釋一下它的工作原理嗎?我真的很困惑,閱讀它... – GraphLearner

+0

我修改了我的答案,但這是一個很大的話題。而我只知道一小部分。 –

+0

@JeffreyScofield你可以通過定義類型t = t的t - > t'來避免需要'-ypeypes'。愛你的答案。 – PatJ

3

讓我試着擴大Jeffrey Scofield的答案。階乘函數的非匿名的遞歸定義可能是

let rec fact n = 
    if n < 2 then 1 else n * fact (n - 1) 

你遇到的第一個問題,當你試圖定義一個匿名遞歸函數是怎麼做的實際遞歸調用(在我們的例子fact (n - 1))。對於一個電話,我們需要一個名字,而我們沒有匿名功能的名字。解決方案是使用臨時名稱。隨着臨時名稱f,定義身體只是

fun n -> if n < 2 then 1 else n * f (n - 1) 

這個術語沒有一個類型,因爲「臨時名稱」 f綁定。但是我們也可以將它轉化爲一個值,它也包含f。讓我們把結果g

let g = fun f n -> if n < 2 then 1 else n * f (n - 1) 

g尚未此刻匿名的,但只是因爲我想再次引用它。 注意到g的類型爲(int -> int) -> (int -> int)。我們想要的(階乘函數)將具有類型(int -> int)。因此g需要我們想要的類型(在這種情況下是函數類型)併產生相同類型的東西。直覺是g採用階乘函數的近似值,即一個函數f,該函數適用於所有的n直到某個極限值N,並返回一個更好的近似值,即一個適用於所有n直到N + 1的函數。

最後,我們需要一些將g變成實際遞歸定義的東西。 這樣做是非常通用的任務。回想一下g提高了逼近質量。最終階乘函數fact是一個不能進一步改進的函數。因此,將g應用於fact應與fact相同。 (實際上,從價值的角度來看,這只是真的,g fact n對於某些n的實際計算與fact n的實際計算不同,但返回的值是相同的)。換句話說,fact是一個固定點g 。所以我們需要的是計算固定點的東西。

幸運的是,有一個函數可以這樣做:Y組合器。從值的角度來看,Y組合器(讓我們在OCaml中使用y,因爲大寫字母保留給構造函數)由y g = g (y g)對於所有g這個事實定義:給定某個函數g,組合器返回其固定點之一。 因此,

y : (`a -> `a) -> `a 

在我們的情況下,類型變量由(int -> int)實例化。 一種可能的方式來定義y

let y = fun g -> (fun x -> g (x x)) (fun x -> g (x x)) 

,但這僅適用於懶散評估(如,我相信,Haskell有)。由於OCaml急於評估,因此在使用時會產生堆棧溢出。其原因是,OCaml中試圖扭轉像y g 8

g (y g) 8 
g (g (y g)) 8 
g (g (g (y g))) 8 
... 

而沒有得到調用g。 的解決方案是使用的y內遞延計算:

let y = fun g -> (fun x a -> g (x x) a) (fun x a -> g (x x) a) 

一個缺點是y不任意類型的工作了。它只適用於函數類型。

​​

但是你問函數的遞歸定義,而不是其他值的遞歸定義。因此,我們對階乘函數的定義是y g,其中yg定義如上。無論y也不g是匿名的,但是這並可以很容易地糾正:

(fun g -> (fun x a -> g (x x) a) (fun x a -> g (x x) a)) 
    (fun f n -> if n < 2 then 1 else n * f (n - 1)) 

UPDATE:

定義y只與-rectypes選項的作用。原因是我們自己申請了x