Lazy concat in Immutable.js?
Is there a way to make a lazy concat of two sequences in Immutable.js? Specifically, I have this algorithm, which flattens a tree into a sequence in width:
var Immutable = require('immutable');
var tree = {
value: 'foo',
children: [
{
value: 'bar',
children: [
{ value: 'barOne'},
{ value: 'barTwo'}
]
},
{
value: 'baz',
children: [
{ value: 'baz1'},
{ value: 'baz2'},
{ value: 'baz3'}
]
}
]
};
var flattenTree = function(seq) {
if(!seq.isEmpty()) {
var nextTier = seq.flatMap(function(node){
return node.children;
});
return seq.concat(flattenTree(nextTier));
} else {
return Immutable.Seq();
}
};
var startSeq = Immutable.Seq([tree]);
var seq = flattenTree(startSeq);
var values = seq.map(function(node){ return node.value; });
console.log(values.first());
Unfortunately, the entire tree is evaluated when it starts. I wish I could do
return seq.concat(function(){ return flattenTree(nextTier); });
and do a lazy concat, but it's not supported. The excellent Ruby style stone supports this. What are my alternatives if I want to use Immutable.js? Do other JS libraries support? Is there any other algorithm that achieves the same thing?
+3
source to share
1 answer
A simple lazy pass-through can be achieved using the Iterable API for Immutable.js:
var Immutable = require('immutable'),
Iterable = Immutable.Iterable,
Seq = Immutable.Seq;
var tree = {
value: 'foo',
children: [
{
value: 'bar',
children: [
{
value: 'bar1',
children: [
{ value: 'bar1_a'},
{ value: 'bar1_b'}
]
},
{
value: 'bar2',
children: [
{ value: 'bar2_a'},
{ value: 'bar2_b'}
]
}
]
},
{
value: 'baz',
children: [
{
value: 'baz1',
children: [
{ value: 'baz1_a'},
{ value: 'baz1_b'}
]
},
{
value: 'baz2',
children: [
{ value: 'baz2_a'},
{ value: 'baz2_b'}
]
},
{
value: 'baz3',
children: [
{ value: 'baz3_a'},
{ value: 'baz3_b'}
]
}
]
}
]
};
// Lazy
// -----------------------------------------------------------------------------
console.log("");
console.log("flattenTree_iterBreadthFirst");
console.log("----------------------------");
function flattenTree_iterBreadthFirst(tree) {
var iter = Iterable.isIterable(tree) ? tree : Iterable([tree]);
return iter.isEmpty() ? iter :
iter.map(function (node) {
return {value: node.value};
}).concat(
Iterable(
[
iter.flatMap(function (node) {
return !node.children ?
[] :
node.children;
})
]
).flatMap(function unpack(children) {
console.log("flatMap unpack");
return flattenTree_iterBreadthFirst(children);
})
);
}
var seq = flattenTree_iterBreadthFirst(tree),
values = seq.map(function (node) { return node.value; });
console.log("1st:", values.first());
// ^ requires 0 calls to unpack
console.log("2nd thru 3rd", values.slice(1,3));
// ^ access w/in this range requires 1 call to unpack
console.log("4th thru 8th", values.slice(3,8));
// ^ access w/in this range requires 2 calls to unpack
console.log("9th thru 18th", values.slice(8,18));
// ^ access w/in this range requires 3 calls to unpack
console.log("rest:", values.rest());
// ^ requires a 4th call to unpack, wherein flattenTree_iterBreadthFirst returns
// an empty Iterable
// NOT Lazy : for comparison
// -----------------------------------------------------------------------------
console.log("");
console.log("flattenTree");
console.log("-----------");
function flattenTree(seq) {
if(!seq.isEmpty()) {
var nextTier = seq.flatMap(function unpack(node) {
console.log("flatMap unpack");
return node.children;
});
return seq.concat(flattenTree(nextTier));
} else {
return Seq();
}
};
seq = flattenTree(Seq([tree]));
values = seq.map(function (node) { return node.value; });
console.log("1st:", values.first());
// console.log("2nd:", values.rest().first());
// console.log("3rd:", values.rest().rest().first());
console.log("rest:", values.rest());
+4
source to share