Recursive, depth first search

I wanted to write a function findDeep that would perform a recursive, depth-first search on plain objects and arrays.

Comments and criticism welcome.



function findDeep(dict, test, index = 0, keys = Object.keys(dict)) {
var item = dict[keys[index]];

if(index > keys.length) {
return null; // End of siblings. No match.
}

if(test(item)) {
return item; // Match.
}

if(item !== null && typeof item === 'object') { // null is an object.
var result = findDeep(item, test); // Children.
if(result) {
return result; // Short circuit, when item found.
}
}

return findDeep(dict, test, ++index); // Siblings.
}

document.writeln('test1: ', findDeep(['foo', 'bar', 'bam'], i => i === 'bar') === 'bar', '
')
document.writeln('test2: ', findDeep([ ['foo'], [['bar']], [ ['baz', ['bat'] ] ] ], i => i === 'bat') === 'bat', '
');
document.writeln('test3: ', findDeep({ foo: 'foo', bar: 'bar', bam: { baz: 'baz' } }, i => i === 'baz') === 'baz', '
');

The main issue with your function is that it can't correctly search for null or undefined.

findDeep(['foo', 'bar', 'bam'], i => i === null); // (1)
findDeep(['foo', 'bar', null], i => i === null);  // (2)
findDeep(['foo', , 'bam'], i => i === undefined); // (3)

(1) and (2) both return null and (3) returns undefined even though there is no such value.

• I would rather make the function return an object, similar to ES2015

generators.

• Separate index argument is excessive if you are

ok with mutating keys.

• I would rename test to

pred for
"predicate"
and item to value to take advantage of ES2015's shorthand properties.

• let is the new var.

function findDeep(dict, pred, keys = Object.keys(dict)) {
if (keys.length === 0) {
return { match: false };
}

let value = dict[keys.pop()];

if (pred(value)) {
return { match: true, value };
}

if (value !== null && typeof item === 'object') {
let result = findDeep(value, pred);

if (result.match) {
return result;
}
}

return findDeep(dict, pred, keys);
}


Last, please keep the coding style consistent: note the space (or no space) after if and the indentation.

StackExchange Code Review Q#111592, answer score: 2