Добрый день, всем! Разбирая одну задачу с помощью дебагера, я столкнулся с непониманием работы return и filter! Очень прошу вас помочь разобраться!
Имеется код, который выполняет обход по всему дереву, и в случае обнаружения узла name в нижнем регистре - записываем его в отдельный массив, после чего, мы обрабатываем полученный массив с помощью встроенной функции filter, чтобы избавиться от null
const filter = (fn, tree) => {
if (!fn(tree)) {
return null;
}
const [name, children] = tree;
console.log(name);
if (!children) {
return tree;
}
const newChildren = children
.map((child) => filter(fn, child))
.filter((v) => v)
return [name, newChildren];
};
const tree = ['a', [
['B', [['e'], ['F']]],
['C'],
['d', [['G'], ['j']]],
]];
const result = filter(([name]) => name === name.toLowerCase(), tree);
// => a
// => d
// => j
JSON.stringify(result);
// '["a", [["d", [["j"]]]]]'
Вопросы возникают к этой части кода:
const newChildren = children
.map((child) => filter(fn, child))
.filter((v) => v)
return [name, newChildren];
};
Насколько я правильно понял, интрепретатор спускается к строчке .filter((v) => v тогда, когда map свою работу выполнил. Грубо говоря, filter начинает работать с этим массивом: ‘[“a”, [null, null, [“d”, [null, [“j”]]]]]’
const newChildren = ["a", [null, null, ["d", [null, ["j"]]]].filter((v) => v)
return [name, newChildren];
};
С этого момента становиться не понятно, что происходит, а именно. После попадание на строчку filter((v) => v) интрепретатор идёт вниз к return и после, возвращается обратно к filter. Почему так происходит? Ведь return, в данном случае, должен был прекратить работу функции? … И почему, функция filter отрабатывает всего 2 раза, а не по количеству элементов, как это и нужно было. Спасибо!
P.S. На всякий случай, я оставлю вам здесь ещё и ТЕОРИЮ, в которой эта задача присутствует:
Filter
В отличие от map
, filter
для деревьев, в том виде, в котором он используется для коллекций, практически непригоден. Посудите сами. Предположим, мы хотим выполнить поиск по файловой системе файлов, подходящих под шаблон *.log
. Задача сразу разбивается на две подзадачи. Фильтрация, оставляющая листовые узлы, и последующая фильтрация по шаблону. Очевидно, что после первого фильтра мы уже хотим работать со списком, но никак не с деревом. Более того, как будет выглядеть дерево в котором только одни файлы, и какой в нём практический смысл? Как ни крути, большинство фильтров древовидных структур, должны на выходе давать плоские списки.
Но всё же иногда filter
может использоваться, к тому же, для полноты картины, стоит пройти все шаги. Для начала необходимо определиться с тем, что нужно вернуть в ситуации, если нода не удовлетворяет предикату. Логично использовать null
.
const filter = (fn, tree) => {
if (!fn(tree)) {
return null;
}
const [name, children] = tree;
console.log(name);
if (!children) {
return tree;
}
const newChildren = children
.map((child) => filter(fn, child))
.filter((v) => v)
return [name, newChildren];
};
const tree = ['a', [
['B', [['e'], ['F']]],
['C'],
['d', [['G'], ['j']]],
]];
const result = filter(([name]) => name === name.toLowerCase(), tree);
// => a
// => d
// => j
JSON.stringify(result);
// '["a", [["d", [["j"]]]]]'
// a *
// /|\
// B * C * d
// /| |\
// e F G j
Глядя на реализацию фильтра, видно, что если нода не удовлетворяет предикату, то её дети не рассматриваются вообще. В примере выше это нода B . Соответственно её дети e и F даже не анализируются и отфильтровываются вместе с B .
Интересно выглядит и вот эта запись children.map((child) => filter(fn, child)).filter((v) => v)
. Дело в том, что наш фильтр не работает со списком, а работает с конкретным корневым узлом. Соответственно, если мы обрабатываем детей, то в результате фильтрации количество детей не уменьшается. На их месте появляется null
. Поэтому обход детей совершается, используя map
на массиве children
с последующим filter
. Тогда все null
элементы отфильтруются.
Посмотрите, какой результат получился бы, если не использовать фильтрацию на значение null
:
const filter = (f, tree) => {
if (!f(tree)) {
return null;
}
const [name, children] = tree;
console.log(name)
if (!children) {
return tree;
}
return [name, children.map(c => filter(f, c))];
};
const tree = ['a', [
['B', [['e'], ['F']]],
['C'],
['d', [['G'], ['j']]],
]];
const result = filter(([name]) => name === name.toLowerCase(), tree);
// => a
// => d
// => j
JSON.stringify(result);
// '["a", [null, null, ["d", [null, ["j"]]]]]'
Сравните с результатом из прошлого примера.
Элементы null
отфильтрованы:
=> '["a", [["d", [["j"]]]]]'
Элементы null
НЕ отфильтрованы:
=> '["a", [null, null, ["d", [null, ["j"]]]]]'