Recursive, depth first search

Question

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', '<br/>')
document.writeln('test2: ', findDeep([ ['foo'], [['bar']], [ ['baz', ['bat'] ] ] ], i => i === 'bat') === 'bat', '<br/>');
document.writeln('test3: ', findDeep({ foo: 'foo', bar: 'bar', bam: { baz: 'baz' } }, i => i === 'baz') === 'baz', '<br/>');

Answer 1

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.

1. I would rather make the function return an object, similar to ES2015 generators.
2. Separate index argument is excessive if you are ok with mutating keys.
3. I would rename test to pred for "predicate" and item to value to take advantage of ES2015's shorthand properties.
4. 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.