在Immutable.js中偷懒？

Question

有办法在Immutable.js中做两个序列的延迟连接吗？具体来说，我有这样一个算法，它将一棵树平平成一个宽度第一的序列：

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());

不幸的是，在运行时会对整个树进行评估。我真希望我能做到

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

让它执行一个惰性的连接，但是不支持它。Ruby的优秀仓鼠宝石支持这一点。如果我想使用Immutable.js，我的选择是什么？还有其他JS库支持它吗？还有另一种算法可以实现同样的目标吗？

Answer 1

可以使用Immutable.js的Iterable实现懒惰的宽度优先遍历：

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());