javascript实现惰性序列之思路

惰性序列在后文简称lazy-seq

什么是lazy-seq?

lazy-seq是一个序列（你可以把它想象成一个数组或者链表）只有在你使用时才会去计算出使用的值并且会把值缓存起来下次再次使用时直接取缓存中的值

lazy-seq有什么用？

优化函数性能

如果你的函数返回的数据是lazy-seq而不是处理好的数据处理数据的过程只会在你使用它的时候进行而且精确到某个数据而你的函数不需要做出什么大的改变

无穷序列（可以想象成无穷大的数组)

拿典型斐波那契数列举例

function fibfn(n){    if(n==0)return 0;    if(n==1)return 1;    return fibfn(n-2)+fibfn(n-1);}

这个能达取斐波那契数列的功能但是换个角度思考下为什么fibfn不能是一个"数组"呢 fibfn是一个无穷大的数组里面是[0,1,1,2,3,5....]这样更直接更直观

实现思路

简单的序列实现

万事开头难，无头绪。参考链表的数据结构首先先要有能存两个元素的东西有了能存俩的我们就能延伸出无数个了然后再有能取出这两个元素的东西,开始敲代码

function cons(a,b){    return function(flg){        return {head:a,tail:b}[flg];    }}function head(seq){    return seq('head');}function tail(seq){    return seq('tail');}var b=cons(1,2);head(b)// ->1tail(b) //->2var c=cons(1,cons(2,cons(3,null)));head(c) //->1head(tail(c)) //->2head(tail(tail(c))) //->3

完美完美哈哈

lazy-seq实现

我要实现的是lazy-seq是在使用的时候才会求值而这里的是在cons的时候值就出来了不符合要求当需要的时候取值初始化的时候第二个参数可以使用函数当取值的时候调用下而且还要把值给缓存起来

function cons(a,b){		if(typeof b !=="function")throw "arg 2 must is function";		function r(flg){						return {head:a,tail:b}[flg];		}		r.toString=function(){			return "lazy-seq:"+formatCacheValue(r,200);		}		return r;	}	function head(lis){		return lis("head");	}	function tail(lis){		if(lis.cacheValue)return lis.cacheValue;		lis.cacheValue=lis("tail")(lis);		return lis.cacheValue;	}  function isEmptyLs(ls){		return ls===null;	}	function formatCacheValue(ls,deep){		if(isEmptyLs(ls))return "";		if(ls.cacheValue===undefined)return head(ls)+"->wating...";		if(deep==0)return "..."		return head(ls)+"->"+formatCacheValue(ls.cacheValue,deep-1);	}

创建1-10的数列使用head只能一个一个的取太麻烦了所以还需要个take函数取多个数据

take函数实现

function take(n,ls){		if(n<0) throw "arg 1 must >0";		if(n==0)return [];		if(isEmptyLs(ls))return [];		if(n==1)return [head(ls)];		return [head(ls)].concat(take(n-1,tail(ls)));}function create10seq(seq){		if(head(seq)==10)return null;		return cons(head(seq)+1,create10seq);}	//1 2 3 4 5 6 7 8 9 10var l10=cons(1,create10seq);

l10->lazy-seq:1->wating...

head(l10)->1

l10->lazy-seq:1->wating...

take(11,l10)->[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

l10->lazy-seq:1->2->3->4->5->6->7->8->9->10->nil

=完美= =完美=

无穷大lazy-seq,map函数实现

接下来实现一个自然数列 1,2,3,4....无穷大这个我们需要一些操作lazy-seq的函数为了简单起见都写成curry的函数

function map(fn){		return function(ls){			return cons(fn(head(ls)),map(fn));		}}function add(a){		return function(b){			return a+b;		}}var l2=cons(1,map(add(1)));

take(10,l2)->[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

take(20,l2)->[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

l2->lazy-seq:1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->wating...

=完美= =完美=

斐波那契lazy-seq实现

下面实现一个复杂点的数列斐波那契

function map2(fn){		return function(ls1){			return function(ls2){				return cons(fn(head(ls1))(head(ls2)),map2(fn)(ls2));			}		}}//0,1,1,2,3,5,8.....	var fib=cons(0,function(seq){		return cons(1,map2(add)(seq));	})

take(10,fib)->[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

take(20,fib)->[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

=一如既往的完美=

filter函数实现

再加个需求我们取出10个大于100的斐波那契数列

function filter(fn){		return function(ls){			if(isEmptyLs(ls))return null;			var val=head(ls);			if(fn(val))return cons(val,function(){				return filter(fn)(tail(ls));			});			return filter(fn)(tail(ls));		}}

take(10,filter(function(a){return a>100})(fib))->[144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946]

两种实现斐波那契数列性能对比

为了方便我们做一个nth函数

function nth(idx,ls){		if(idx==0)return head(ls);		return nth(idx-1,tail(ls));}  console.time("fibfn");	console.log(fibfn(40));	console.timeEnd("fibfn");	console.time("lazy-seq-fib");	console.log(nth(40,fib));	console.timeEnd("lazy-seq-fib");/*out*>102334155*>fibfn: 1390.397ms*>102334155*>lazy-seq-fib: 0.426ms*/

性能相差好远 =fibfn= 50是它的极限（在我的浏览器中)

看看fib的极限 nth(1471,fib) ->1.1785114478791467e+307

nth(l480,fib) ->Infinity 毫无压力

=完美=