# lazy-seq.js

**Repository Path**: diqye/lazy-seq.js

## Basic Information

- **Project Name**: lazy-seq.js
- **Description**: javascript惰性序列实现思路 讲解
- **Primary Language**: JavaScript
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 5
- **Forks**: 2
- **Created**: 2015-12-23
- **Last Updated**: 2020-12-18

## Categories & Tags

**Categories**: javascript-toolkits

**Tags**: None

## README

* javascript实现惰性序列之思路
惰性序列在后文简称lazy-seq
* 什么是lazy-seq?
lazy-seq是一个序列（你可以把它想象成一个数组或者链表）
只有在你使用时才会去计算出使用的值并且会把值缓存起来下次再次使用时直接取
缓存中的值
* lazy-seq有什么用？
** 优化函数性能
如果你的函数返回的数据是lazy-seq而不是处理好的数据  处理数据的过程只会在你使用它的时候进行而且精确到某个数据
而你的函数不需要做出什么大的改变
** 无穷序列（可以想象成无穷大的数组) 
拿典型斐波那契数列举例
#+BEGIN_SRC javascript
function fibfn(n){
    if(n==0)return 0;
    if(n==1)return 1;
    return fibfn(n-2)+fibfn(n-1);
}
#+END_SRC
这个能达取斐波那契数列的功能但是换个角度思考下为什么fibfn不能是一个"数组"呢
fibfn是一个无穷大的数组 里面是[0,1,1,2,3,5....]这样更直接更直观,fibfn性能是很差的 传入50浏览器就卡死了 后面有性能对比
* 实现思路
** 简单的序列实现
万事开头难，无头绪。参考链表的数据结构首先先要有能存两个元素的东西有了能存俩的我们就能延伸出无数个了
然后再有能取出这两个元素的东西,开始敲代码
#+BEGIN_SRC javascript
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
#+END_SRC
完美 完美 哈哈
** lazy-seq实现
我要实现的是lazy-seq是在使用的时候才会求值 而这里的是在cons的时候值就出来了不符合要求
当需要的时候取值初始化的时候第二个参数可以使用函数 当取值的时候调用下而且还要把值给缓存起来
#+BEGIN_SRC javascript
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);
	}
#+END_SRC
创建1-10的数列
使用head只能一个一个的取太麻烦了 所以还需要个take函数 取多个数据
** take函数实现
#+BEGIN_SRC javascript
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);
#+END_SRC
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的函数
#+BEGIN_SRC javascript
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)));
#+END_SRC
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实现
下面实现一个复杂点的数列 斐波那契
#+BEGIN_SRC javascript
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));
	})
#+END_SRC
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的斐波那契数列
#+BEGIN_SRC javascript
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));
		}
}
#+END_SRC
take(10,filter(function(a){return a>100})(fib))->[144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946]

=完美=
* 两种实现斐波那契数列性能对比
为了方便我们做一个nth函数
#+BEGIN_SRC javascript
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
*/
#+END_SRC
性能相差好远 =fibfn= 50是它的极限（在我的浏览器中)

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

nth(l480,fib) ->Infinity

毫无压力
* 以上代码都在lazy-seq.html中


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

#+BEGIN_SRC javascript
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))
#+END_SRC