Lazy concat in Immutable.js?

Question

Is there a way to do a lazy concat of two sequences in Immutable.js? Specifically, I have this algorithm that flattens a tree into a breadth-first sequence:

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 whole tree is evaluated when this is run. I wish I could do

return seq.concat(function(){ return flattenTree(nextTier); });

and have it perform a lazy concat, but it's not supported. Ruby's excellent Hamster gem supports this. What are my alternatives if I want to use Immutable.js? Do any other JS libraries support it? Is there another algorithm that achieves the same thing?

Answer 1

A lazy breadth-first traversal can be achieved with 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());