狠狠撸

狠狠撸Share a Scribd company logo
Immutable @ JavaScript
var	
 ?me	
 ?=	
 ?{	
 ?
	
 ?	
 ?name:	
 ?	
 ?	
 ?"Yuta	
 ?Shimakawa",	
 ?
	
 ?	
 ?tw:	
 ?	
 ?	
 ?	
 ?	
 ?"@banana_umai",	
 ?
	
 ?	
 ?qiita:	
 ?	
 ?"bananaumai",	
 ?
	
 ?	
 ?github:	
 ?"bananaumai"	
 ?
};
Livesense tech night   immutable-js at a glance
ではございません
Livesense tech night   immutable-js at a glance
at a glance...
Livesense tech night   immutable-js at a glance
不変データ
Seq
List
Map
OrderedMap
Set
OrderedSet
Record
var	
 ?list1	
 ?=	
 ?Immutable.List.of(1,	
 ?2);	
 ?
var	
 ?list2	
 ?=	
 ?list1.push(3,	
 ?4,	
 ?5);	
 ?
var	
 ?list3	
 ?=	
 ?list2.unshift(0);	
 ?
var	
 ?list4	
 ?=	
 ?list1.concat(list2,	
 ?list3);	
 ?
assert(list1.size	
 ?===	
 ?2);	
 ?
assert(list2.size	
 ?===	
 ?5);	
 ?
assert(list3.size	
 ?===	
 ?6);	
 ?
assert(list4.size	
 ?===	
 ?13);	
 ?
assert(list4.get(0)	
 ?===	
 ?1);	
 ?
https://github.com/facebook/immutable-js/
JSオブジェクトとの
相互変換
var	
 ?map1	
 ?=	
 ?Immutable.Map({a:1,	
 ?b:2,	
 ?c:3,	
 ?d:4});	
 ?
var	
 ?map2	
 ?=	
 ?Immutable.Map({c:10,	
 ?a:20,	
 ?t:30});	
 ?
var	
 ?obj	
 ?=	
 ?{d:100,	
 ?o:200,	
 ?g:300};	
 ?
var	
 ?map3	
 ?=	
 ?map1.merge(map2,	
 ?obj);	
 ?
//	
 ?Map	
 ?{	
 ?a:	
 ?20,	
 ?b:	
 ?2,	
 ?c:	
 ?10,	
 ?d:	
 ?100,	
 ?t:	
 ?30,	
 ?o:	
 ?200,	
 ?g:	
 ?300	
 ?}
https://github.com/facebook/immutable-js/
var	
 ?deep	
 ?=?Immutable.Map(	
 ?
{	
 ?a:	
 ?1,	
 ?b:	
 ?2,	
 ?c:	
 ?Immutable.List.of(3,	
 ?4,	
 ?5)	
 ?});	
 ?
deep.toObject()	
 ?//	
 ?{	
 ?a:	
 ?1,	
 ?b:	
 ?2,	
 ?c:	
 ?List	
 ?[	
 ?3,	
 ?4,	
 ?5	
 ?]	
 ?}	
 ?
deep.toArray()	
 ?//	
 ?[	
 ?1,	
 ?2,	
 ?List	
 ?[	
 ?3,	
 ?4,	
 ?5	
 ?]	
 ?]	
 ?
deep.toJS()	
 ?//	
 ?{	
 ?a:	
 ?1,	
 ?b:	
 ?2,	
 ?c:	
 ?[	
 ?3,	
 ?4,	
 ?5	
 ?]	
 ?}	
 ?
JSON.stringify(deep)	
 ?//	
 ?'{"a":1,"b":2,"c":[3,4,5]}'
入れ子データ
var	
 ?nested	
 ?=	
 ?Immutable.fromJS({a:{b:{c:[3,4,5]}}});	
 ?
//	
 ?Map	
 ?{	
 ?a:	
 ?Map	
 ?{	
 ?b:	
 ?Map	
 ?{	
 ?c:	
 ?List	
 ?[	
 ?3,	
 ?4,	
 ?5	
 ?]	
 ?}	
 ?}	
 ?}	
 ?
var	
 ?nested2	
 ?=	
 ?nested.mergeDeep({a:{b:{d:6}}});	
 ?
//	
 ?Map	
 ?{	
 ?a:	
 ?Map	
 ?{	
 ?b:	
 ?Map	
 ?{	
 ?c:	
 ?List	
 ?[	
 ?3,	
 ?4,	
 ?5	
 ?],	
 ?d:	
 ?6	
 ?}	
 ?}	
 ?}	
 ?
var	
 ?nested3	
 ?=	
 ?
nested2.updateIn(['a',	
 ?'b',	
 ?'d'],	
 ?value	
 ?=>	
 ?value	
 ?+	
 ?1);	
 ?
//	
 ?Map	
 ?{	
 ?a:	
 ?Map	
 ?{	
 ?b:	
 ?Map	
 ?{	
 ?c:	
 ?List	
 ?[	
 ?3,	
 ?4,	
 ?5	
 ?],	
 ?d:	
 ?7	
 ?}	
 ?}	
 ?}	
 ?
var	
 ?nested4	
 ?	
 ?
=	
 ?nested3.updateIn(['a',	
 ?'b',	
 ?'c'],	
 ?list	
 ?=>	
 ?list.push(6));	
 ?
//	
 ?Map	
 ?{	
 ?a:	
 ?Map	
 ?{	
 ?b:	
 ?Map	
 ?{	
 ?c:	
 ?List	
 ?[	
 ?3,	
 ?4,	
 ?5,	
 ?6	
 ?],	
 ?d:	
 ?7	
 ?}	
 ?}	
 ?}
https://github.com/facebook/immutable-js/
遅延评価(厂别辩)
var	
 ?oddSquares	
 ?=	
 ?Immutable.Seq.of(1,2,3,4,5,6,7,8)	
 ?
	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?.filter(x	
 ?=>	
 ?x	
 ?%	
 ?2)	
 ?
	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?.map(x	
 ?=>	
 ?x	
 ?*	
 ?x);	
 ?//	
 ?not	
 ?computed	
 ?here!	
 ?
	
 ?	
 ?
oddSquares.get(1);	
 ?//	
 ?9
https://github.com/facebook/immutable-js/
同等性
var	
 ?map1	
 ?=	
 ?Immutable.Map({a:1,	
 ?b:1,	
 ?c:1});	
 ?
var	
 ?map2	
 ?=	
 ?Immutable.Map({a:1,	
 ?b:1,	
 ?c:1});	
 ?
assert(map1	
 ?!==	
 ?map2);	
 ?
assert(Immutable.is(map1,	
 ?map2)	
 ?===	
 ?true);
https://github.com/facebook/immutable-js/
闯厂で不変データ
Immutableなリストを
素朴に実装してみた
肠濒辞苍别による実装
var	
 ?_	
 ?=	
 ?require('lodash');	
 ?
	
 ?	
 ?
function	
 ?iPush(arr,	
 ?val)	
 ?{	
 ?
	
 ?	
 ?var	
 ?arr2	
 ?=	
 ?_.clone(arr);	
 ?
	
 ?	
 ?arr2.push(val);	
 ?
	
 ?	
 ?return	
 ?arr2;	
 ?
}	
 ?
	
 ?	
 ?
var	
 ?arr	
 ?=	
 ?[];	
 ?
for	
 ?(var	
 ?i	
 ?=	
 ?0;	
 ?i	
 ?<	
 ?100000;	
 ?i++)	
 ?{	
 ?
	
 ?	
 ?arr	
 ?=	
 ?iPush(arr,	
 ?i);	
 ?
}
https://gist.github.com/bananaumai/cc2f4d90662aa823ce9e
…は
cloneのコストが膨大
Linked Listを実装
var	
 ?LinkedList	
 ?=	
 ?{};	
 ?
LinkedList.prototype	
 ?=	
 ?{	
 ?
	
 ?	
 ?head:	
 ?function()	
 ?{	
 ?
	
 ?	
 ?	
 ?	
 ?return	
 ?this._head;	
 ?
	
 ?	
 ?},	
 ?
	
 ?	
 ?
	
 ?	
 ?tail:	
 ?function()	
 ?{	
 ?
	
 ?	
 ?	
 ?	
 ?return	
 ?this._tail;	
 ?
	
 ?	
 ?},	
 ?
	
 ?	
 ?
	
 ?	
 ?push:	
 ?function(val)	
 ?{	
 ?
	
 ?	
 ?	
 ?	
 ?return	
 ?new	
 ?NonEmptyList(val,	
 ?this);	
 ?
	
 ?	
 ?},	
 ?
	
 ?	
 ?
	
 ?	
 ?forEach:	
 ?function(fnc)	
 ?{	
 ?
	
 ?	
 ?	
 ?	
 ?fnc(this._head);	
 ?
	
 ?	
 ?	
 ?	
 ?if	
 ?(this._tail	
 ?instanceof	
 ?NonEmptyList)	
 ?{	
 ?
	
 ?	
 ?	
 ?	
 ?	
 ?	
 ?this._tail.forEach(fnc);	
 ?
	
 ?	
 ?	
 ?	
 ?}	
 ?
	
 ?	
 ?}	
 ?
};	
 ?
var	
 ?EmptyList	
 ?=	
 ?function()	
 ?{	
 ?
	
 ?	
 ?this._head	
 ?=	
 ?null;	
 ?
	
 ?	
 ?this._tail	
 ?=	
 ?null;	
 ?
};	
 ?
EmptyList.prototype	
 ?=	
 ?Object.create(LinkedList.prototype);	
 ?
EmptyList.prototype.constructor	
 ?=	
 ?EmptyList;
https://gist.github.com/bananaumai/164b24b264e0f917007c
var	
 ?NonEmptyList	
 ?=	
 ?function(head,	
 ?tail)	
 ?{	
 ?
	
 ?	
 ?this._head	
 ?=	
 ?head;	
 ?
	
 ?	
 ?this._tail	
 ?=	
 ?tail;	
 ?
};	
 ?
NonEmptyList.prototype	
 ?=	
 ?
Object.create(LinkedList.prototype);	
 ?
NonEmptyList.prototype.constructor	
 ?=	
 ?NonEmptyList;	
 ?	
 ?
LinkedList.of	
 ?=	
 ?function()	
 ?{	
 ?
	
 ?	
 ?var	
 ?_create	
 ?=	
 ?function(vals,	
 ?list)	
 ?{	
 ?
	
 ?	
 ?	
 ?	
 ?if	
 ?(vals.length	
 ?===	
 ?0)	
 ?return	
 ?list;	
 ?
	
 ?	
 ?	
 ?	
 ?var	
 ?head	
 ?=	
 ?vals.shift();	
 ?
	
 ?	
 ?	
 ?	
 ?return	
 ?_create(vals,	
 ?new	
 ?NonEmptyList(head,	
 ?list))	
 ?
	
 ?	
 ?};	
 ?
	
 ?	
 ?
	
 ?	
 ?return	
 ?_create(	
 ?
	
 ?	
 ?	
 ?	
 ?Array.prototype.slice.call(arguments).reverse(),	
 ?
	
 ?	
 ?	
 ?	
 ?new	
 ?EmptyList()	
 ?
	
 ?	
 ?);	
 ?
};
var	
 ?list	
 ?=	
 ?LinkedList.of();	
 ?
for	
 ?(var	
 ?i	
 ?=	
 ?0;	
 ?i	
 ?<	
 ?100000;	
 ?i++)	
 ?{	
 ?
	
 ?	
 ?list	
 ?=	
 ?list.push(i);	
 ?
}	
 ?
https://gist.github.com/bananaumai/164b24b264e0f917007c
…は
(&pushはそれなりに速いけど???)
末尾再帰最適化
されないので難しい
(&Object.ArrayのAPIの実現しようとすると???)
颈尘尘耻迟补产濒别-箩蝉のアプローチ
Trie
http://ja.wikipedia.org/wiki/%E3%83%88%E3%83%A9%E3%82%A4%E6%9C%A8
(def	
 ?list	
 ?[0	
 ?1	
 ?2	
 ?3	
 ?4	
 ?5])
ClojureやScalaが採用
しているアプローチ
Livesense tech night   immutable-js at a glance
滨尘尘耻迟补产濒别.尝颈蝉迟の実装
文字列のキーの代わりに
添字の数値をbitに変換、
パーティショニング
var	
 ?list	
 ?=	
 ?Immutable.List.of(1,…,1000);	
 ?
list.get(887);
http://hypirion.com/musings/understanding-persistent-vector-pt-2#f1n
実際は5bitずつ分割するので
↓
O(Log32N)
実際は32通り
http://hypirion.com/musings/understanding-persistent-vector-pt-1
var	
 ?list1	
 ?=	
 ?Immutable.List.of(1,2,3,4,5,6,7,8);	
 ?
var	
 ?list2	
 ?=	
 ?list1.set(5,	
 ?"beef");
list1 list2
http://hypirion.com/musings/understanding-persistent-vector-pt-1
要素のpush
var	
 ?list1	
 ?=	
 ?Immutable.List.of(…);	
 ?
var	
 ?list2	
 ?=	
 ?list.push(…);
最右のリーフノードに空きがある場合
http://hypirion.com/musings/understanding-persistent-vector-pt-1
最右のリーフノードに空きがない場合
http://hypirion.com/musings/understanding-persistent-vector-pt-1
rootから伸びるすべてのリーフが埋まっている場合
http://hypirion.com/musings/understanding-persistent-vector-pt-1
要素のpop
var	
 ?list1	
 ?=	
 ?Immutable.List.of(…);	
 ?
var	
 ?list2	
 ?=	
 ?list.pop();
最右のリーフノードが2つ以上の要素を持つ場合
http://hypirion.com/musings/understanding-persistent-vector-pt-1
最右のリーフノードが1つの要素を持つ場合
http://hypirion.com/musings/understanding-persistent-vector-pt-1
削除後rootノードが1つの要素だけをもつ場合
http://hypirion.com/musings/understanding-persistent-vector-pt-1
简単なまとめ
Trieによるリストの表現
O(Log32N)のアクセス
最小限のコピー

More Related Content

Livesense tech night immutable-js at a glance