Работа filter на примере одной задаче?

Добрый день, всем! Разбирая одну задачу с помощью дебагера, я столкнулся с непониманием работы 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"]]]]]'

Насколько я правильно понял, интрепретатор спускается к строчке .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];
};

Всё правильно вы поняли и данный массив состоит из двух компонентов

[“a”, [null, null, [“d”, [null, [“j”]]]]]

Где первый элемент массива это строка “a”, второй элемент массива - это массив значений [null, null, [“d”, [null, [“j”]]]]

Из этого следует элементов в массиве 2 и ответ на ваш вопрос:

… И почему, функция filter отрабатывает всего 2 раза, а не по количеству элементов, как это и нужно было.

Теперь вернёмся к вопросу:

С этого момента становиться не понятно, что происходит, а именно. После попадание на строчку filter((v) => v) интрепретатор идёт вниз к return и после, возвращается обратно к filter. Почему так происходит? Ведь return, в данном случае, должен был прекратить работу функции?

Как Вы верно заметили с этого момента выполниться следующий код

['a', [null, null, ['d', [null, ['j']]]]].filter((v) => v)

Следуя спецификации метод filter
выполнит данный callback (в нашем случаи callback-ом является функция (v) => v )) для каждого элемента массива (как помним их 2) и в случаи вызов callback-а вернёт значение true , элемент на котором сработал callback будет добавлен в новый массив который возвращает данный метод.
Также следует отметить, что callback, первый аргументом принимает элемент иттерируемого массива.

Рассмотрим вызов callbackа на каждом элементе данного массива:

[
'a',                               // Первый элемент массива
[null, null, ['d', [null, ['j']]]] // Второй элемент массива
].filter((v) => {
  // Первый вызов v в данном случаи это 'a' и функция возвращает логическое true, так как в JS не пустая строка это true
// Второй вызов v - массива, что тоже в JS является логическим true
  return v
})
// Поэтому результатом вызова filter будет новый массив, который в точности такой же как и обрабатываемый до вызова filter:
[
'a',                            
[null, null, ['d', [null, ['j']]]]
]

2 симпатии

Я вас от всей души благодарю, за столь подробный ответ! Вы прирождённый учитель! Единственное, я хочу вас немного поправить. В моём примере ответ: ‘[“a”, [[“d”, [[“j”]]]]]’, то есть, без null. Для этого и нужна функция filter((v)=>v)
И ещё… Я правильно понимаю, что то, дебагер мне ошибочно показал, что он спускается после первого вызова filter((v)=>v) вниз… Что на самом деле, он никуда не спускается…?