第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號安全,請及時(shí)綁定郵箱和手機(jī)立即綁定
已解決430363個(gè)問題,去搜搜看,總會有你想問的

我們可以實(shí)現(xiàn)尾遞歸模的缺點(diǎn)嗎?通過蹦床?

我們可以實(shí)現(xiàn)尾遞歸模的缺點(diǎn)嗎?通過蹦床?

慕妹3146593 2021-05-11 17:53:24
您可以將蹦床視為程序中優(yōu)化的編譯器優(yōu)化。因此,是什么使我們無法以完全相同的方式來適應(yīng)更通用的優(yōu)化技術(shù)。這是尾遞歸模態(tài)缺點(diǎn)的草圖:const loop = f => {  let step = f(); while (step && step[step.length - 1] && step[step.length - 1].type === recur) {    let step_ = step.pop();    step.push(...f(...step_.args));  }  return step;};const recur = (...args) =>  ({type: recur, args});const push = (xs, x) => (xs.push(x), xs);const map = f => xs =>  loop((i = 0) =>    i === xs.length      ? []      : push([f(xs[i])], recur(i + 1)));const xs =   map(x => x * 2) (Array(1e6).fill(0).map((x, i) => i))  .slice(0,5);console.log(xs); // [0, 2, 4, 6, 8]這種優(yōu)化取決于表達(dá)式的關(guān)聯(lián)性。乘法也具有關(guān)聯(lián)性,因此存在尾遞歸模乘。但是,我必須作弊才能在Javascript中實(shí)現(xiàn)它:const loop = f => {  let step = f();  const acc = [];  while (step && step[1] && step[1].type === recur) {    acc.push(step[0]);    step = f(...step[1].args);  }  return acc.reduce((acc, f) => f(acc), step);};const recur = (...args) =>  ({type: recur, args});const mul = x => step => [y => x * y, step];const pow = (x_, n_) =>  loop((x = x_, n = n_) =>    n === 0 ? 1    : n === 1 ? x    : mul(x) (recur(x, n - 1)));    console.log(  pow(2, 1e6)); // Infinity, no stack overflow如您所見,我不能使用mul不是特別令人滿意的Regular 。這與Javascript蜜蜂語言緊密相關(guān)嗎?有沒有更好的方法來實(shí)現(xiàn)JS中的尾遞歸模乘而不必引入笨拙的二進(jìn)制運(yùn)算符?
查看完整描述

1 回答

?
米琪卡哇伊

TA貢獻(xiàn)1998條經(jīng)驗(yàn) 獲得超6個(gè)贊

與其使用loop/ recur(我認(rèn)為這是一種丑陋和不必要的hack),不如考慮使用folds:


const recNat = (zero, succ) => n => {

    let result = zero;


    while (n > 0) {

        result = succ(result);

        n = n - 1;

    }


    return result;

};


const mul = x => y => x * y;


const pow = x => recNat(1, mul(x));


console.log([0,1,2,3,4,5,6,1e6].map(pow(2))); // [1,2,4,8,16,32,64,Infinity]

幾乎每個(gè)遞歸函數(shù)都可以使用折疊來定義(也稱為結(jié)構(gòu)遞歸,又稱為歸納)。例如,甚至可以使用折疊來定義Ackermann函數(shù):


const recNat = (zero, succ) => n => {

    let result = zero;


    while (n > 0) {

        result = succ(result);

        n = n - 1;

    }


    return result;

};


const add = x => y => x + y;


const ack = recNat(add(1),

    ackPredM => recNat(ackPredM(1),

        ackMPredN => ackPredM(ackMPredN)));


console.time("ack(4)(1)");

console.log(ack(4)(1)); // 65533

console.timeEnd("ack(4)(1)");

上面的代碼段大約需要18秒才能在筆記本電腦上計(jì)算出答案。


現(xiàn)在,您可能會問為什么我recNat使用迭代而不是自然遞歸來實(shí)現(xiàn):


const recNat = (zero, succ) => function recNatZS(n) {

    return n <= 0 ? zero : succ(recNatZS(n - 1));

};

我使用迭代的原因與您使用迭代實(shí)現(xiàn)的原因相同loop。踩踏。通過為要折疊的每種數(shù)據(jù)類型實(shí)現(xiàn)不同的蹦床,您可以編寫功能代碼,而不必?fù)?dān)心堆棧溢出。


底線:使用折疊而不是顯式遞歸。它們比您想像的強(qiáng)大得多。


查看完整回答
反對 回復(fù) 2021-05-20
  • 1 回答
  • 0 關(guān)注
  • 152 瀏覽
慕課專欄
更多

添加回答

舉報(bào)

0/150
提交
取消
微信客服

購課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動學(xué)習(xí)伙伴

公眾號

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號