你如何製作一個匿名遞歸函數(例如階乘n的簡單事情?)我聽說過它是可能的,但不知道如何使它在OCaml中工作。OCaml中的匿名遞歸函數
let a =
fun x -> ....
我只是不知道如何繼續下去......
你如何製作一個匿名遞歸函數(例如階乘n的簡單事情?)我聽說過它是可能的,但不知道如何使它在OCaml中工作。OCaml中的匿名遞歸函數
let a =
fun x -> ....
我只是不知道如何繼續下去......
這裏是只使用匿名函數階乘的定義:
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應用到這個函數時,你確實得到了階乘函數。
讓我試着擴大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
,其中y
和g
定義如上。無論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
。
你能解釋一下它的工作原理嗎?我真的很困惑,閱讀它... – GraphLearner
我修改了我的答案,但這是一個很大的話題。而我只知道一小部分。 –
@JeffreyScofield你可以通過定義類型t = t的t - > t'來避免需要'-ypeypes'。愛你的答案。 – PatJ