Подробно разбираем задачу Обхода по дереву с применением reduce

Добрый вечер! Столкнулся с задачей, связанной с обходом по дереву. Прошу помочь разобраться!!! Ниже, я постараюсь изложить максимально подробно свой вопрос. Он состоит из нескольких под вопросов, потому, прошу вас отнестись к этому с пониманием. Уже давно меня это задача беспокоит) Сразу скажу, что-то решение, которое я представлю здесь - учительское!

ЗАДАНИЕ

findFilesByName.js
Реализуйте и экспортируйте по умолчанию функцию, которая принимает на вход файловое дерево и подстроку, а возвращает список файлов, имена которых содержат эту подстроку.

const tree = mkdir('/', [
  mkdir('etc', [
    mkdir('apache'),
    mkdir('nginx', [
      mkfile('nginx.conf', { size: 800 }),
    ]),
    mkdir('consul', [
      mkfile('config.json', { size: 1200 }),
      mkfile('data', { size: 8200 }),
      mkfile('raft', { size: 80 }),
    ]),
  ]),
  mkfile('hosts', { size: 3500 }),
  mkfile('resolve', { size: 1000 }),
]);
 
findFilesByName(tree, 'co');
// => ['/etc/nginx/nginx.conf', '/etc/consul/config.json']

Обратите внимание на то, что возвращается не просто имя файла, а полный путь до файла, начиная от корня.

Подсказки
Для построения путей используйте функцию path.join.
Проверку вхождения строк можно делать с помощью функции str.includes(substr).

РЕШЕНИЕ УЧИТЕЛЯ

const path = require('path');
 
const findFilesByName = (root, substr) => {
const { type, children} = root;
 
    const iter = (n, ancestry, acc) => {
      const newAncestry = path.join(ancestry, n.name);
      if (type == 'file') {
        return n.name.includes(substr) ? [...acc, newAncestry] : acc;
      }
      
            return n.children.reduce((cAcc, nn) => iter(nn, newAncestry, cAcc), acc);
      
      
    };
  
    return iter(root, '', []);
  };
 
  findFilesByName(tree, 'co');
// => ['/etc/nginx/nginx.conf', '/etc/consul/config.json']

Вопрос № 1

Что происходит в этой строчке, при каждом обращение к reduce? Как меняются его параметры cAcc, nn?

return n.children.reduce((cAcc, nn) => iter(nn, newAncestry, cAcc), acc);

Вопрос № 2

Первый снимок

Второй снимок

Вопрос № 3

Дерево, по которому работает js код:

let tree = {
    "name": "/",
    "children": [
    {
        "name": "etc",
        "children": [
        {
            "name": "apache",
            "children": [],
            "meta":
            {},
            "type": "directory"
        },
        {
            "name": "nginx",
            "children": [
            {
                "name": "nginx.conf",
                "meta":
                {},
                "type": "file"
            }],
            "meta":
            {},
            "type": "directory"
        },
        {
            "name": "consul",
            "children": [
            {
                "name": "config.json",
                "meta":
                {},
                "type": "file"
            },
            {
                "name": "data",
                "children": [],
                "meta":
                {},
                "type": "directory"
            }],
            "meta":
            {},
            "type": "directory"
        }],
        "meta":
        {},
        "type": "directory"
    },
    {
        "name": "hosts",
        "meta":
        {},
        "type": "file"
    },
    {
        "name": "resolve",
        "meta":
        {},
        "type": "file"
    }],
    "meta":
    {},
    "type": "directory"
}

Код примера не работает. Его нужно чуток поправить, поправленный код - по ссылке что я добавлю ниже.

Чтобы ответить на этот вопрос нужно описать весь алгоритм подхода.

История следующая: iter принимает на вход узел дерева n, строку пути ancestry, и массив путей с файлами которые подошли под критерий поиска - acc. При каждом вызове iter происходит 2 параллельных процесса (не как в программировании параллельные, а как в жизни). ** (запомни это место) В строку ancestry добавляется имя текущего узла через разделитель / или \. Тут нюанс в том что имя может быть именем файла а может быть именем папки. Это их кода нифига не очевидно, но если подумать-погонять код, то становится понятнее. Далее если узел - это файл с соответствующим (заматченым) именем, но имя добавляется в acc массив. Так как узел - это файл, у него нет детей, их не нужно обходить, значит возвращается результат аккумулирования путей.

А теперь ответ на твой вопрос. Если узел - это папка, то для всех детей папки вызывается iter с нааккумулированным путем ancestry и нааккумулированными путями соответсвующих (заматченных) файлов acc. Результат вызова каждой итерации reduce - это массив саккумулированных соответсвующих (заматченных) файлов. Каждая итерация вызова reduce начинает шаги с запомненного места**.

Это проще понять, если стратегически расставить консоль логи: https://repl.it/repls/EthicalUnwelcomeClient


Думаю вопрос 2 отпадет как и вопрос 3. Код некорректный. Нужно проверять тип узла который передался в iter чтобы правильно аккумулировать пути. В коде что ты кинул это происходит только не в том месте. Поправленный код по ссылке выше.


Мое оценочное суждение - автор этого решения не ставил целью написать понятный код для учеников. Код писался “максимально лаконично” в ущерб понимаемости. Если этот код не понятен сразу - не думай что дело в твоих способностях. Я, пися код годами, сидел разбирался с этой балалайкой минут 20-30, и еще минут 25 писал ответ.