Recursively walking a tree to build up a new one

Could this be better factored as a reduce?

/**
 * recursively build a nested Backbone.Model or Backbone.Collection
 * from a deep JSON structure.
 *
 * undefined for regex values
 */
exports.modelify = function modelify (data) {

    if (_.isArray(data)) {
        return new Backbone.Collection(_.map(data, modelify));
    }

    else if (_.isObject(data) && !_.isDate(data)) {

        var m = util.mapo(data, function(val, key) {
            return [key, modelify(val)];
        });

        return new Backbone.Model(m);
    }
    else {
        // data is a primitive or a date
        return data;
    }
}

var mapo = exports.mapo = _.compose(_.object, _.map);

It can indeed be factored as a reduce, but I don't know if the result is "better".

So, to anyone who still has this problem so long after the question was asked, and god knows I hated Backbone for the lack of data tree-spanning Model and Collection classes, here is the treeReduce function, analogous to Array.prototype.reduceRight but for trees, first written in a simple fashion:

Assuming that each tree object has a value property (of type a which may be anything) and a children property which is an array of child tree objects,

Assuming that f :: a -> [b] -> b in Haskell notation (i.e. to an element of type a and an array of elements of type b, f associates another b-typed element),

Assuming that ini has type [b],

function treeReduce(tree, f, ini)
{
    // If we're at a leaf, use 'ini'
    if (tree.children.length === 0) {
        return f(tree.value, ini);
    }

    // Else, recursion!
    return f(tree.value, children.map(function (child) {
        return treeReduce(child, f, ini);
    }));
}

For your problem, we have to adapt treeReduce to use _.map and to not assume that the tree has the value and children properties, etc:

// Using this, we can customize the way to get the value and children of a tree
// in our treeReduce function
function treeReduceFactory(getValue, getChildren)
{
    return function customTreeReduce(tree, f, ini)
    {
        var children = getChildren(tree);
        if (children.length === 0) {
            return f(getRoot(tree), ini);
        }

        return f(getValue(tree), _.map(children, function (child) {
            return customTreeReduce(child, f, ini);
        }));
    };
}

// Our treeReduce is defined like this:
var treeReduceForBackbone = treeReduceFactory(
    // There really is no such thing as getting the 'value' of the current node
    // in our case
    function (data) {
        return data;
    },

    // How to get the "children" of something that can be an array or an object?
    function (data) {
        // If data is an array then it is itself its own children (??!)
        if (_.isArray(data)) {
            return data;
        }
        // If it's an object then its children are in the values
        if (_.isObject(data) && !_.isDate(data)) {
            return _.map(data, function (val, key) { return [key, val]; });
        }
        // If it's neither of those, it doesn't have children
        return [];
    }
);

// Finally, we define 'modelify', and indeed it looks somewhat more elegant
exports.modelify = function (data) {
    return treeReduceForBackbone(
        data,

        function (data, modelifiedDataArray) {
            if (_.isArray(data)) {
                return new Backbone.Collection(modelifiedDataArray);
            }
            if (_.isObject(data) && !_.isDate(data)) {
                return new Backbone.Model(_.object(modelifiedDataArray));
            }
            return data;
        },

        []
    );
};

And this is where we realize that because our data tree does not have a coherent interface throughout (different ways to get the children depending on the type of the node in the tree, object or array), we end up repeating checks in the node children getter and in the f function. This could obviously be fixed with yet another modification to treeReduce, but sincerely at this point I like your initial solution better.

To note, though: an iterative version of your function, as opposed to recursive, would certainly be faster, and may counterbalance the lack of readability factor in your choice of implementation.

StackExchange Code Review Q#25175, answer score: 3