龙空技术网

JavaScript杂谈——懒执行和尾递归

du1dume 558

前言:

目前各位老铁们对“js尾递归”大致比较着重,大家都想要剖析一些“js尾递归”的相关内容。那么小编同时在网摘上搜集了一些对于“js尾递归””的相关内容,希望我们能喜欢,兄弟们一起来了解一下吧!

一说到函数式编程,无论是在理论上还是实践上,Haskell 肯定首先映入眼帘,F# 和 Scala 紧跟其后。如果你真想函数式编程,踏踏实实去学习上述三门语言吧。但是,函数式编程的思想,有一些是我们在 JavaScript 编程中可以借鉴的。

Lazy evaluation

暂且把它翻译为懒执行或者懒运行吧。懒执行的意思就是程序在它需要运行的时候才运行。在 JavaScript 中恰巧有这个概念,那就是 generator。

Generator 是个函数,当我们调用 next 方法时它才会运行。举个例子:

constthisIsAGenerator=function*(){leta=0;for(;;){yielda;a++;}}constg=thisIsAGenerator();for(leti=0;i<5;i++){console.log(g.next().value);//0,1,2,3,4}g.return();console.log(g.next());//{value:undefined,done:true}

定义一个 generator 函数的标志就是 function 旁边有个 *。运行这个 generator 函数并不会立即运行函数体里的内容,而是返回给调用者一个 iterator 对象。当调用者调用这个 iterator 的 next 函数时,generator 函数体才会开始运行,并在第一个 yield 关键字处停止运行,并返回 yield 语句中的变量值给调用者。当调用者调用 iterator 对象的 return 函数时,generator 函数就结束了。

next 函数的返回值是一个对象,它有两个属性,value 和 done。其中 done 标识了这个 generator 函数是否已经结束。

我们都知道可以用 console.time 和 timeEnd 来计算一段程序的运行时间,假如某些情况下我们不能使用 console,或者想把测试结果保存起来,这时我们就可以利用 generator 来实现一个这个功能。

consttiming=function*(time){yieldDate.now()-time;}consttime=timing(Date.now());//开始letsum=0;for(leti=0;i<1000000;i++){sum=sum+i;}//结束console.log(time.next().value)//这里输出被开始和结束包裹起来的程序的运行时间

我们知道 Stream api 在 Node.js 中存在很长时间了。但是在浏览器中却迟迟没有被推行开来。利用 generator,我们可以实现类似 Stream api 的东西。

constnums=function*(f=null){leti=0;for(;;){yieldi;if(f){i+=f(i);}else{i+=1;}}}constdata=[];constnums_gen=nums(x=>x+1);for(letiofnums_gen){console.log(i);//0,1,3,7,15,31,63,127,...if(i>10000){break;}data.push(i);}

nums 是个产生数字的 generator,它接收一个参数,这个参数是个函数,默认值是 null。它的内部逻辑很简单,从 0 开始,如果没有传递函数参数,每次返回值加 1,如果传递了函数,每次返回值加上函数作用后的结果,是不是有点儿像 map 函数的作用?然后我们利用这个数字产生器生成了一些数据 data,很简单,大家可以实际运行下代码看下结果。

有了数据我们就可以实现一个 Stream 了。

consttestStream=function*(data){constchunkSize=5;constdataLen=data.length;leti=0;while(i<dataLen){constresultData=[];for(letj=0;j<chunkSize;j++){if(data[i]){resultData.push(data[i]);}i+=1;}yieldresultData;}}for(letioftestStream(data)){console.log(i);//[1,3,7,15][31,63,127,255,511][1023,2047,4095,8191]}

注意,此代码传入的 data 是上一段代码生成的。testStream(data) 类似于 fs.createReadStream(data),后面的 for of 操作类似于 readerStream.on('data', function(chunk){})。

尾递归优化

这是另一个函数式语言中的概念,但是 JavaScript 引擎没有提供此功能(Webkit除外)。尾递归优化就是让递归的运行方式像运行普通循环一样。在纯函数式编程语言中,比如 Haskell,是没有循环语句的,所以只能通过递归来实现循环。下面我们来验证下 JavaScript 引擎确实没有尾递归优化,也就是正确书写尾递归也一样爆栈。

//生成数据constd=newArray(100000);for(leti=0;i<d.length;i++){d[i]=i;}//尾递归函数constsumFn=function(data,sum=0){if(!data.length){returnsum;}returnsumFn(data.slice(1),sum+data[0]);}console.log(sumFn(d));//JavaScriptheapoutofmemory

sumFn 就是我们的尾递归函数,用来计算一个 10 万个数据的加和。一些编译器看到该函数的最后一句是调用自己,那么就会对该程序作出优化,不会出现堆栈溢出的情况。然而大多数 JavaScript 引擎并没有对此作出优化。但并不是没有办法,那就是 trampolining 函数。实现如下:

consttrampoline=(fn)=>{return(...args)=>{letresult=fn(...args);while(typeofresult==='function'){result=result();}returnresult;}}//生成数据constd=newArray(100000);for(leti=0;i<d.length;i++){d[i]=i;}//尾递归函数改造constsumFn=function(data,sum=0){if(!data.length){returnsum;}//这里把尾递归调用变成了返回一个函数return()=>sumFn(data.slice(1),sum+data[0]);}//使用trampoliningconstfinalSumFn=trampoline(sumFn)console.log(finalSumFn(d));//4999950000

trampoline 函数接收一个函数作为参数,这个函数就是尾递归函数;然后它返回一个函数,这个函数相当于把尾递归函数又包装了一层,可以和 react 的高阶组件类比一下。在这个包装后的函数里,我们调用了尾递归函数,并对尾递归函数的返回值进行判断,如果返回结果还是函数,就继续运行它,直到返回结果不是函数为止。我们对尾递归函数的返回值做了修改,从之前的返回一个值变成了返回一个函数,这样就和 trampoline 函数的 while 循环对上了。说白了,trampoline 把经过改造的尾递归调用变成了 while 循环。

让我们不用循环重写下 filter 函数:

const_myFilter=function(data,fn,result=[]){if(!data.length){returnresult}return()=>_myFilter(data.slice(1),fn,fn(data[0])?(result.length?newArray(...result,data[0]):[data[0]]):result);}constmyFilter=trampoline(_myFilter);console.log(myFilter(d,x=>x%2===0));

其实和之前的加和函数差不多,唯一绕一点儿的就是那个嵌套三元表达式,其实也不没什么难的。外层的三元表达式的真值结果又是一个三元表达式而已,如果你把它写成 if 语句可能会更好理解写,但就不那么函数式了。

虽然解决了问题了,但付出的代价也不小,如果你测试一下的话,会发现 trampoline 函数会比普通 for 循环慢得多,array 内建的 filter 函数也比 trampoline 版的快得多。

如果有问题,请添加公众号“读一读我”。

标签: #js尾递归 #js实现中断正在执行的方法