Рекурсия с функциями высшего порядка - PullRequest
Новая
       8

Рекурсия с функциями высшего порядка

7 голосов
/ 07 октября 2019

Я хотел бы понять следующий пример, чтобы он был кристально чистым для меня. К сожалению, моя голова висит на строке: .forEach (c => (node ​​[c.id] = makeTree (Categories, c.id))). кто-нибудь может дать мне подсказку? 

let categories = [
  { id: 'animals', parent: null },
  { id: 'mammals', parent: 'animals' },
  { id: 'cats', parent: 'mammals' },
  { id: 'dogs', parent: 'mammals' },
  { id: 'chihuahua', parent: 'dogs' },
  { id: 'labrador', parent: 'dogs' },
  { id: 'persian', parent: 'cats' },
  { id: 'siamese', parent: 'cats' }
];

let makeTree = (categories, parent) => {
  let node = {};
  categories
    .filter(c => c.parent == parent)
    .forEach(c => (node[c.id] = makeTree(categories, c.id)));
  return node;
};

console.log(makeTree(categories, null));

expected:

{
  animals: {
    mammals: {
      dogs: {
        chihuahua: null
        labrador: null
      },
      cats: {
        persian: null
        siamese: null
      }
    }
  }
}

Ответы [ 3 ]

4 голосов
/ 07 октября 2019

Код можно эквивалентно (и, imho, более чистый) записать с помощью обычного цикла и условного выражения вместо filter и forEach: 

function makeTree(categories, parent) {
  let node = {};
  for (const c of categories)
    if (c.parent == parent)
      node[c.id] = makeTree(categories, c.id);
  return node;
}

Теперь это просто обычная рекурсивная функция, ничего более высокого порядка не осталось.

Кроме того, особенно в отношении обратного вызова forEach, который использует совершенно ненужную групповую скобку в сокращенный синтаксис функции стрелки вместо правильной записи его с телом блока (поскольку из обратного вызова forEach ничего не нужно возвращать): 

.forEach(c => {
  node[c.id] = makeTree(categories, c.id);
});
1 голос
/ 07 октября 2019

Рекурсия - это просто причудливый цикл.

Что делает рекурсию трудной для понимания, так это то, что часть цикла скрыта от вас.

Скрытая часть называется стеком вызовов. Поймите стек вызовов, и вы поймете рекурсию. 

function makeTree(categories, parent) {
  let node = {};
  const stack = [{ parent, node }];
  while (stack.length) {
    const { parent, node } = stack.pop();
    for (const category of categories) {
      if (category.parent === parent) {
        const subnode = {};
        node[category.id] = subnode;
        stack.push({
          parent: category.id,
          node: subnode
        });
      }
    }
  }
  return node;
}

let categories = [
  { id: 'animals', parent: null },
  { id: 'mammals', parent: 'animals' },
  { id: 'cats', parent: 'mammals' },
  { id: 'dogs', parent: 'mammals' },
  { id: 'chihuahua', parent: 'dogs' },
  { id: 'labrador', parent: 'dogs' },
  { id: 'persian', parent: 'cats' },
  { id: 'siamese', parent: 'cats' }
];

document.body.innerHTML = `${JSON.stringify(makeTree(categories, null), null, 2)}
`

Немного длиннее, но именно так работает рекурсия: 

function makeTree(categories, parent) {
  const stack = [{ parent }];
  let subnode; // the return value
  call: while (stack.length) {
    let { parent, node, i, c } = stack.pop();
    if (!node) {
      node = {};
      i = 0;
    } else {
      node[c.id] = subnode;
    }
    for (; i < categories.length; i++) {
      const category = categories[i];
      if (category.parent === parent) {
        stack.push({
          parent,
          node,
          i: i+1,
          c: category
        });
        stack.push({
          parent: category.id
        });
        continue call;
      }
    }
    subnode = node;
  }
  return subnode;
}
1 голос
/ 07 октября 2019

Имеет ли это смысл?

Подтверждение скрипки: https://jsfiddle.net/gz6uyodw/2/

function makeTree(categories, parent) {
  let node = {};
  const filteredArr = categories.filter(c => c.parent === parent);
  console.log('level arr', filteredArr)
  for (let obj of filteredArr) {
    const nodeToAppend = makeTree(categories, obj.id);
    console.log('node to append:', nodeToAppend)
    node[obj.id] = nodeToAppend;
  }
  return node;
}

console.log(makeTree(categories, null));

По сути, вы готовите отфильтрованный массив, для которого вы готовите уровень, для первого уровняу вас есть животные, у которых есть второй уровень FilterArr, которые являются мамалами, у мам есть группы, которые являются собаками, и в массиве будет 2 объекта (добавлен дополнительный, чтобы иметь разные фильтрованные объекты для кошек и собак) и т. д.

...