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 优秀的仓鼠 gem 支持这个。如果我想使用 Immutable.js，我有什么选择？是否有任何其他 JS 库支持它？是否有另一种算法可以达到同样的效果？

Answer 1

惰性广度优先遍历可以通过 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());

Immutable.js 中的延迟连接？

Lazy concat in Immutable.js?

javascript

functional-programming

immutable.js