Блог

Главная - Вопросы по программированию - Функциональный способ разбора вложенного словаря на массив элементов каждого уровня

Функциональный способ разбора вложенного словаря на массив элементов каждого уровня

#javascript #recursion #functional-programming

Вопрос:

Я хотел бы решить проблему в функциональном стиле в javascript.

Мой диктант выглядит так:

 [{
    "title": "A",
    "isFinal": false,
    "children": [{
            "title": "AA",
            "isFinal": false,
            "children": [{
                    "title": "AAA",
                    "isFinal": true
                },
                {
                    "title": "AAB",
                    "isFinal": true
                }
            ]
        },
        {
            "title": "AB",
            "isFinal": false,
            "children": [{
                    "title": "ABA",
                    "isFinal": true
                },
                {
                    "title": "ABB",
                    "isFinal": true
                }
            ]
        },
        {
            "title": "AC",
            "isFinal": true
        }
    ]
}]

Итак, это дерево, и оно может иметь до N (6) уровней и еще много листьев в любом узле. В последнем узле isFinal для поля установлено значение true.

Я хотел бы получить следующий результат

 [["A"], ["AA", "AB", "AC"], ["AAA", "AAB", "ABA", "ABB"]]

который является заголовком от каждого узла на одном и том же уровне в одном и том же массиве.

Я думаю, что это как-то связано с рекурсивным спуском алгоритма, но я не могу этого понять.

Пока что я могу получить доступ к первому уровню:

 
function parseData (data) {
    const data = new Array();

    return data.filter((dataLevelChild) => (!dataLevelChild.isFinal)).map((dataLevelChild, index) => (
      dataLevelChild.title
    ))
}

но я действительно не знаю, как передать элементы второго уровня и сохранить все в одном массиве.

Другой способ-использовать forEach

 function parseData (data) {
    const parsedData = new Array();

    const parse = (e) => {
      parsedData.push({
          id: e.title,
      });

      e.children amp;amp; e.children.forEach(parse);
  }

  return data.forEach(parse);

что неверно, но, по крайней мере, у меня есть доступ к каждому элементу. Но функциональна ли она? На мой взгляд, это не похоже, потому что обычно вы не используете .нажмите так в функциональном стиле

Комментарии:

1. Вам нужна рекурсивная функция для работы с произвольной вложенностью. Сделать это с помощью функционального программирования будет непросто.

2. @Бармар: почему ты так говоришь? Рекурсия-чрезвычайно распространенный метод в FP. Мой ответ, например, — это решение FP.

3. @ScottSauyet Я знаю, что рекурсия распространена в FP, но мне показалось, что было бы сложно поместить все результаты определенного уровня рекурсии в соответствующий элемент массива в конечном результате.

4. @Barmar: это было единственное, что меня вообще замедлило, создав это поверх моего обычного кода обхода в ширину. Мне нужно было немного подумать о том, куда пойдут эти дополнительные [ ] скобки. Но код в итоге получается довольно чистым.

Ответ №1:

Вы можете собрать все вложенные уровни и назначить заголовки следующего уровня массиву сбора.

 const
    getTitles = data => data.reduce((r, { title, children }) => {
        (r[0] ??= []).push(title);
        if (children) getTitles(children)
            .forEach((a, i) => (r[i   1] ??= []).push(...a));
        return r;
    }, []),
    data = [{ title: "A", isFinal: false, children: [{ title: "AA", children: [{ title: "AAA", isFinal: true }, { title: "AAB", isFinal: true }] }, { title: "AB", children: [{ title: "ABA", isFinal: true }, { title: "ABB", isFinal: true }] }, { title: "AC", isFinal: true }] }],
    result = getTitles(data);

console.log(result); 
 .as-console-wrapper { max-height: 100% !important; top: 0; }

Другой подход заключается в сборе заголовков и дочерних элементов отдельно и получении дочерних элементов в другом вызове функции.

 const
    getTitles = data => {
        const [titles, children] = getPairs(data);
        return children.length
            ? [titles, ...getTitles(children)]
            : [titles];
    },
    getPairs = data => data.reduce(
        ([t, c], { title, children = [] }) => [[...t, title], [...c, ...children]],
        [[], []]
    ),
    data = [{ title: "A", isFinal: false, children: [{ title: "AA", children: [{ title: "AAA", isFinal: true }, { title: "AAB", isFinal: true }] }, { title: "AB", children: [{ title: "ABA", isFinal: true }, { title: "ABB", isFinal: true }] }, { title: "AC", isFinal: true }] }],
    result = getTitles(data);

console.log(result); 
 .as-console-wrapper { max-height: 100% !important; top: 0; }

Комментарии:

1. Хотя этот код, как всегда, элегантен, OP специально попросил функциональное программное решение. Между звонками push и тем forEach , я не думаю, что это подходит.

2. @ScottSauyet, пожалуйста, взгляните на второй фрагмент кода.

3. Да, это гораздо более функциональный подход!

Ответ №2:

Вы можете просто использовать рекурсию:

 function myFunc(arr = []){
  let toRet = [];
  function recursion(obj = {}, depth){
    toRet[depth] = [...(toRet[depth]|| []), obj.title];
    if(!obj.isFinal){
      obj.children.forEach(el => recursion(el, depth   1))
    }
  }
  arr.forEach(el => recursion(el, 0))
  return toRet;
}

let input = [{
    "title": "A",
    "isFinal": false,
    "children": [{
            "title": "AA",
            "isFinal": false,
            "children": [{
                    "title": "AAA",
                    "isFinal": true
                },
                {
                    "title": "AAB",
                    "isFinal": true
                }
            ]
        },
        {
            "title": "AB",
            "isFinal": false,
            "children": [{
                    "title": "ABA",
                    "isFinal": true
                },
                {
                    "title": "ABB",
                    "isFinal": true
                }
            ]
        },
        {
            "title": "AC",
            "isFinal": true
        }
    ]
}]
console.log(myFunc(input))

Ответ №3:

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

Здесь levelMap функция отображает все вложенные элементы, группируя их по уровням.

И getTitle частично применяется к вышеупомянутой функции, которая извлекает заголовки из узлов.

 const levelMap = (fn) => (xs = []) => 
  xs .length == 0 
    ? [] 
    : [xs .flatMap (x => [fn (x)])]
          .concat (levelMap (fn) (xs .flatMap (({children = []}) => children)))

const getTitles = levelMap (x => x.title)

const input = [{title: "A", isFinal: false, children: [{title: "AA", isFinal: false, children: [{title: "AAA", isFinal: true}, {title: "AAB", isFinal: true}]}, {title: "AB", isFinal: false, children: [{title: "ABA", isFinal: true}, {title: "ABB", isFinal: true}]}, {title: "AC", isFinal: true}]}]

console .log (getTitles (input)) 
 .as-console-wrapper {max-height: 100% !important; top: 0}

Если вы не хотели группироваться по уровням (я обычно этого не делаю), вы можете просто заменить

     : [xs .flatMap (x => [fn (x)])]

с

     : xs .flatMap (x => [fn (x)])

(в этот момент я бы, вероятно, переименовал это во что-то вроде breadthFirstMap .)

Этот подход является чисто функциональным. Нигде нет мутации, и функции чисты.

Очевидно, что вы могли бы написать единственную функцию, которая делает это, и при этом избавиться от fn параметра. Но levelMap он универсален, и на него достаточно легко наложить нашу функцию поверх него.

Ответ №4:

Рекурсия, как показано в других ответах, является хорошим инструментом для работы с древовидными структурами.

Решение проблем с этим кодом с помощью как краткого, так и читаемого кода действительно очень сложно… Я уверен, что мое решение может быть значительно улучшено.

 const deepPluck = (prop, tree = []) => {
  const res = [];

  const drilldown = (prop, list, depth) => {    
    for (const item of list) {
      const { children = [], [prop]: plucked } = item;

      res[depth] = (res[depth] ?? []).concat(plucked);
      drilldown(prop, children, depth   1);
    }
  }

  drilldown(prop, tree, 0);
  return res;
}

// =
const data = [{ title: "A", isFinal: false, children: [{ title: "AA", children: [{ title: "AAA", isFinal: true }, { title: "AAB", isFinal: true }] }, { title: "AB", children: [{ title: "ABA", isFinal: true }, { title: "ABB", isFinal: true }] }, { title: "AC", isFinal: true }] }];

console.log(
  JSON.stringify(deepPluck('title', data)),
);
Метки: