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….]这样更直接更直观,fibfn性能是很差的 传入50浏览器就卡死了 后面有性能对比

实现思路

简单的序列实现

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

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)// ->1
tail(b) //->2
var c=cons(1,cons(2,cons(3,null)));
head(c) //->1
head(tail(c)) //->2
head(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 10
var 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

毫无压力

以上代码都在lazy-seq.html中

==================新的设计========

function empty(){
  return {
    type:'MyList',
    cos:'empty'
  }
}
function isEmpty(list){
  return list.cos == 'empty'
}
function cos(a,b){
  return {
    type:'MyList',
    cos:'cos',
    head:a,
    tail:b
  }
}
function tail(list){
  if(isEmpty(list)){
    return empty()
  }else{
    return list.tail(list)
  }
}
// （a->b）-> MyList a -> MyList b
let map = fn => list => {
  if(isEmpty(list)){
    return list
  }else{
    let h = head(list)
    return cos(fn(h),_=>map(fn)(tail(list)))
  }
}
// (a,b->c)->MyList a->MyList b -> MyList c
let zipWith = fn => list => list2 =>{
  if(isEmpty(list)){
    return empty()
  }else if(isEmpty(list2)){
    return empty()
  }else{
    return cos(fn(head(list),head(list2)),
               _=>zipWith(fn)(tail(list))(tail(list2))
              )
  }
}
let take = n => list => {
  if(n == 0) return empty()
  else if(isEmpty(list)) return empty()
  else return cos(head(list),_=>take(n-1)(tail(list)))
}
function head(list){
  return list.head
}

function printList(list){
  if(isEmpty(list)){
    return []
  }else{
    return [head(list)].concat(printList(tail(list)))
  }
}

let nat = cos(0,map(a=>a+1))

let fib = cos(1,()=>cos(1,
                        ()=>(zipWith((a,b)=>a+b)(fib)(tail(fib))
                        )))
printList(take(10)(fib))