超碰av在线|无码精品一区二区三区在线|伊人色色日韩一级片内射视频群批_欧美丰满少妇人妻HD高清在线_亚洲一区二区中文_亚洲无码动漫专区

JavaScript 中匿名函數(shù)的遞歸調(diào)用

2016-9-27    藍(lán)藍(lán)設(shè)計(jì)的小編

如果您想訂閱本博客內(nèi)容,每天自動(dòng)發(fā)到您的郵箱中, 請(qǐng)點(diǎn)這里

不管是什么編程語(yǔ)言,相信稍微寫過(guò)幾行代碼的同學(xué),對(duì)遞歸都不會(huì)陌生。 以一個(gè)簡(jiǎn)單的階乘計(jì)算為例:

function factorial(n) { if (n <= 1) { return 1;
    } else { return n * factorial(n-1);
    }
}

我們可以看出,遞歸就是在函數(shù)內(nèi)部調(diào)用對(duì)自身的調(diào)用。 那么問(wèn)題來(lái)了,我們知道在Javascript中,有一類函數(shù)叫做匿名函數(shù),沒(méi)有名稱,怎么調(diào)用呢?當(dāng)然你可以說(shuō),可以把匿名函數(shù)賦值給一個(gè)常量:

const factorial = function(n){ if (n <= 1) { return 1;
    } else { return n * factorial(n-1);
    }
}

這當(dāng)然是可以的。但是對(duì)于一些像,函數(shù)編寫時(shí)并不知道自己將要賦值給一個(gè)明確的變量的情況時(shí),就會(huì)遇到麻煩了。如:

(function(f){
    f(10);
})(function(n){ if (n <= 1) { return 1;
    } else { return n * factorial(n-1);//太依賴于上下文變量名 }
}) //Uncaught ReferenceError: factorial is not defined(…)

那么存不存在一種完全不需要這種給予準(zhǔn)確函數(shù)名(函數(shù)引用變量名)的方式呢?

arguments.callee

我們知道在任何一個(gè)function內(nèi)部,都可以訪問(wèn)到一個(gè)叫做arguments的變量。

(function(){console.dir(arguments)})(1,2)

1.png

打印出這個(gè)arguments變量的細(xì)節(jié),可以看出他是Arguments的一個(gè)實(shí)例,而且從數(shù)據(jù)結(jié)構(gòu)上來(lái)講,他是一個(gè)類數(shù)組。他除了類數(shù)組的元素成員和length屬性外,還有一個(gè)callee方法。 那么這個(gè)callee方法是做什么的呢?我們來(lái)看下MDN

callee 是 arguments 對(duì)象的屬性。在該函數(shù)的函數(shù)體內(nèi),它可以指向當(dāng)前正在執(zhí)行的函數(shù)。當(dāng)函數(shù)是匿名函數(shù)時(shí),這是很有用的, 比如沒(méi)有名字的函數(shù)表達(dá)式 (也被叫做”匿名函數(shù)”)。

哈哈,很明顯這就是我們想要的。接下來(lái)就是:

(function(f){ console.log(f(10));
})(function(n){ if (n <= 1) { return 1;
    } else { return n * arguments.callee(n-1);
    }
}) //output: 3628800

但是還有一個(gè)問(wèn)題,MDN的文檔里明確指出

警告:在 ECMAScript 第五版 (ES5) 的 嚴(yán)格模式 中禁止使用 arguments.callee()。

哎呀,原來(lái)在ES5的use strict;中不給用啊,那么在ES6中,我們換個(gè)ES6的arrow function寫寫看:

((f) => console.log(f(10)))( (n) => n <= 1? 1: arguments.callee(n-1)) //Uncaught ReferenceError: arguments is not defined(…)

有一定ES6基礎(chǔ)的同學(xué),估計(jì)老早就想說(shuō)了,箭頭函數(shù)就是個(gè)簡(jiǎn)寫形式的函數(shù)表達(dá)式,并且它擁有詞法作用域的this值(即不會(huì)新產(chǎn)生自己作用域下的thisargumentssuper 和 new.target等對(duì)象),且都是匿名的。

那怎么辦呢?嘿嘿,我們需要借助一點(diǎn)FP的思想了。

Y組合子

關(guān)于Y Combinator的文章可謂數(shù)不勝數(shù),這個(gè)由師從希爾伯特的著名邏輯學(xué)家Haskell B.Curry(Haskell語(yǔ)言就是以他命名的,而函數(shù)式編程語(yǔ)言里面的Curry手法也是以他命名)“發(fā)明”出來(lái)的組合算子(Haskell是研究組合邏輯(combinatory logic)的)仿佛有種神奇的魔力,它能夠算出給定lambda表達(dá)式(函數(shù))的不動(dòng)點(diǎn)。從而使得遞歸成為可能。

這里需要告知一個(gè)概念不動(dòng)點(diǎn)組合子

不動(dòng)點(diǎn)組合子(英語(yǔ):Fixed-point combinator,或不動(dòng)點(diǎn)算子)是計(jì)算其他函數(shù)的一個(gè)不動(dòng)點(diǎn)的高階函數(shù)。

函數(shù)f的不動(dòng)點(diǎn)是一個(gè)值x使得f(x) = x。例如,0和1是函數(shù) f(x) = x^2 的不動(dòng)點(diǎn),因?yàn)?0^2 = 0而 1^2 = 1。鑒于一階函數(shù)(在簡(jiǎn)單值比如整數(shù)上的函數(shù))的不動(dòng)點(diǎn)是個(gè)一階值,高階函數(shù)f的不動(dòng)點(diǎn)是另一個(gè)函數(shù)g使得f(g) = g。那么,不動(dòng)點(diǎn)算子是任何函數(shù)fix使得對(duì)于任何函數(shù)f都有

f(fix(f)) = fix(f). 不動(dòng)點(diǎn)組合子允許定義匿名的遞歸函數(shù)。它們可以用非遞歸的lambda抽象來(lái)定義.

在無(wú)類型lambda演算中眾所周知的(可能是最簡(jiǎn)單的)不動(dòng)點(diǎn)組合子叫做Y組合子。

接下來(lái),我們通過(guò)一定的演算推到下這個(gè)Y組合子。

// 首先我們定義這樣一個(gè)可以用作求階乘的遞歸函數(shù) const fact = (n) => n<=1?1:n*fact(n-1)  
console.log(fact(5)) //120 // 既然不讓這個(gè)函數(shù)有名字,我們就先給這個(gè)遞歸方法一個(gè)叫做self的代號(hào) // 首先是一個(gè)接受這個(gè)遞歸函數(shù)作為參數(shù)的一個(gè)高階函數(shù) const fact_gen = (self) => (n) => n<=1?1:n*self(n-1)  
console.log(fact_gen(fact)(5)) //120 // 我們是將遞歸方法和參數(shù)n,都傳入遞歸方法,得到這樣一個(gè)函數(shù) const fact1 = (self, n) => n<=1?1:n*self(self, n-1)  
console.log(fact1(fact1, 5)) //120 // 我們將fact1 柯理化,得到fact2 const fact2 = (self) => (n) => n<=1?1:n*self(self)(n-1)  
console.log(fact2(fact2)(5)) //120 // 驚喜的事發(fā)生了,如果我們將self(self)看做一個(gè)整體 // 作為參數(shù)傳入一個(gè)新的函數(shù): (g)=> n<= 1? 1: n*g(n-1) const fact3 = (self) => (n) => ((g)=>n <= 1?1:n*g(n-1))(self(self))  
console.log(fact3(fact3)(5)) //120 // fact3 還有一個(gè)問(wèn)題是這個(gè)新抽離出來(lái)的函數(shù),是上下文有關(guān)的 // 他依賴于上文的n, 所以我們將n作為新的參數(shù) // 重新構(gòu)造出這么一個(gè)函數(shù): (g) => (m) => m<=1?1:m*g(m-1) const fact4 = (self) => (n) => ((g) => (m) => m<=1?1:m*g(m-1))(self(self))(n)  
console.log(fact4(fact4)(5)) // 很明顯fact4中的(g) => (m) => m<=1?1:m*g(m-1) 就是 fact_gen // 這就很有意思啦,這個(gè)fact_gen上下文無(wú)關(guān)了, 可以作為參數(shù)傳入了 const weirdFunc = (func_gen) => (self) => (n) => func_gen(self(self))(n)  
console.log(weirdFunc(fact_gen)(weirdFunc(fact_gen))(5)) //120 // 此時(shí)我們就得到了一種Y組合子的形式了 const Y_ = (gen) => (f) => (n)=> gen(f(f))(n) // 構(gòu)造一個(gè)階乘遞歸也很easy了 const factorial = Y_(fact_gen)  
console.log(factorial(factorial)(5)) //120 // 但上面這個(gè)factorial并不是我們想要的 // 只是一種fact2,fact3,fact4的形式 // 我們肯定希望這個(gè)函數(shù)的調(diào)用是factorial(5) // 沒(méi)問(wèn)題,我們只需要把定義一個(gè) f' = f(f) = (f)=>f(f) // eg. const factorial = fact2(fact2) const Y = gen => n => (f=>f(f))(gen)(n)  
console.log(Y(fact2)(5)) //120  console.log(Y(fact3)(5)) //120  console.log(Y(fact4)(5)) //120

推導(dǎo)到這里,是不是已經(jīng)感覺(jué)到脊背嗖涼了一下,反正筆者我第一次接觸在康托爾、哥德?tīng)?、圖靈——永恒的金色對(duì)角線這篇文章里接觸到的時(shí)候,整個(gè)人瞬間被這種以數(shù)學(xué)語(yǔ)言去表示程序的方式所折服。

來(lái),我們回憶下,我們最終是不是得到了一個(gè)不定點(diǎn)算子,這個(gè)算子可以找出一個(gè)高階函數(shù)的不動(dòng)點(diǎn)f(Y(f)) = Y(f)。 將一個(gè)函數(shù)傳入一個(gè)算子(函數(shù)),得到一個(gè)跟自己功能一樣,但又并不是自己的函數(shù),這個(gè)說(shuō)法有些拗口,但又味道十足。

好了,我們回到最初的問(wèn)題,怎么完成匿名函數(shù)的遞歸呢?有了Y組合子就很簡(jiǎn)單了:

/*求不動(dòng)點(diǎn)*/ (f => f(f)) /*以不動(dòng)點(diǎn)為參數(shù)的遞歸函數(shù)*/ (fact => n => n <= 1 ? 1 : n * fact(fact)(n - 1)) /*遞歸函數(shù)參數(shù)*/ (5) // 120

曾經(jīng)看到過(guò)一些說(shuō)法是”最讓人沮喪是,當(dāng)你推導(dǎo)出它(Y組合子)后,完全沒(méi)法兒通過(guò)只看它一眼就說(shuō)出它到底是想干嘛”,而我恰恰認(rèn)為這就是函數(shù)式編程的魅力,也是數(shù)學(xué)的魅力所在,精簡(jiǎn)優(yōu)雅的公式,背后隱藏著復(fù)雜有趣的推導(dǎo)過(guò)程。

2.jpg

總結(jié)

務(wù)實(shí)點(diǎn)兒講,匿名函數(shù)的遞歸調(diào)用,在日常的js開(kāi)發(fā)中,用到的真的很少。把這個(gè)問(wèn)題拿出來(lái)講,主要是想引出對(duì)arguments的一些講解和對(duì)Y組合子這個(gè)概念的一個(gè)普及。

但既然講都講了,我們真的用到的話,該怎么選擇呢?來(lái),我們喜聞樂(lè)見(jiàn)的benchmark下: 分別測(cè)試:

// fact  fact(10) // Y (f => f(f))(fact => n => n <= 1 ? 1 : n * fact(fact)(n - 1))(10) // Y' const fix = (f) => f(f) const ygen = fix(fact2)  
ygen(10) // callee (function(n) {n<=1?1:n*arguments.callee(n-1)})(10)

環(huán)境:Macbook pro(2.5 GHz Intel Core i7), node-5.0.0(V8:4.6.85.28) 結(jié)果:

fact x 18,604,101 ops/sec ±2.22% (88 runs sampled)

Y x 2,799,791 ops/sec ±1.03% (87 runs sampled)

Y’ x 3,678,654 ops/sec ±1.57% (77 runs sampled)

callee x 2,632,864 ops/sec ±0.99% (81 runs sampled)

可見(jiàn)Y和callee的性能相差不多,因?yàn)樾枰R時(shí)構(gòu)建函數(shù),所以跟直接的fact遞歸調(diào)用有差不多一個(gè)數(shù)量級(jí)的差異,將不定點(diǎn)函數(shù)算出后保存下來(lái),大概會(huì)有一倍左右的性能提升。

 

藍(lán)藍(lán)設(shè)計(jì)m.miumiuwan.com )是一家專注而深入的界面設(shè)計(jì)公司,為期望卓越的國(guó)內(nèi)外企業(yè)提供卓越的UI界面設(shè)計(jì)、BS界面設(shè)計(jì) 、 cs界面設(shè)計(jì) 、 ipad界面設(shè)計(jì) 、 包裝設(shè)計(jì) 、 圖標(biāo)定制 、 用戶體驗(yàn) 、交互設(shè)計(jì)、 網(wǎng)站建設(shè) 平面設(shè)計(jì)服務(wù) 

 

分享本文至:

日歷

鏈接

個(gè)人資料

存檔