数组上的递归深度函数

IT技术 javascript arrays object recursion higher-order-functions
2021-02-28 15:13:41

我有一个像这个输入这样的对象数组，我想在另一个对象中嵌套一些对象（如果它们的 parentId 是父母的 forumId），

我的函数可以工作，但深度最大为 1，我怎样才能让它在 n 深度下工作？任何想法或优化表示赞赏！

编辑：指出后，输入不一定是有序的。

const input = [
  {
    forumId: 1,
    parentId: null,
    forumName: "Main",
    forumDescription: "",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 2,
    parentId: 1,
    forumName: "Announcements",
    forumDescription: "Announcements & Projects posted here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 3,
    parentId: 1,
    forumName: "General",
    forumDescription: "General forum, talk whatever you want here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 4,
    parentId: 3,
    forumName: "Introduction",
    forumDescription: "A warming introduction for newcomers here",
    forumLocked: false,
    forumDisplay: true,
  },
];

function processInput(forumInput) {
  const topLevelForums = forumInput.filter(function (forum) {
    return forum.parentId === null;
  });

  let output = topLevelForums;

  forumInput.forEach(function (forum) {
    if (forum.parentId !== null) {
      const forumParentId = forum.parentId;
      output.forEach(function (parentForum, idx) {
        if (parentForum.forumId === forumParentId) {
          if (!output[idx].hasOwnProperty("subForums")) {
            output[idx].subForums = [];
          }
          parentForum.subForums.push(forum);
        }
      });
    }
  });

  return output;
}

这是预期的输出：

[
  {
    forumId: 1,
    parentId: null,
    forumName: "Main",
    forumDescription: "",
    forumLocked: false,
    forumDisplay: true,
    subForums: [
      {
        forumId: 2,
        parentId: 1,
        forumName: "Announcements",
        forumDescription: "Announcements & Projects posted here",
        forumLocked: false,
        forumDisplay: true,
      },
      {
        forumId: 3,
        parentId: 1,
        forumName: "General",
        forumDescription: "General forum, talk whatever you want here",
        forumLocked: false,
        forumDisplay: true,
        subForums: [
          {
            forumId: 4,
            parentId: 3,
            forumName: "Introduction",
            forumDescription: "A warming introduction for newcomers here",
            forumLocked: false,
            forumDisplay: true,
          },
        ],
      },
    ],
  },
]

这是当前的输出：

[
  {
    forumDescription: "",
    forumDisplay: true,
    forumId: 1,
    forumLocked: false,
    forumName: "Main",
    parentId: null,
    subForums: [
      {
        forumDescription: "Announcements & Projects posted here",
        forumDisplay: true,
        forumId: 2,
        forumLocked: false,
        forumName: "Announcements",
        parentId: 1,
      },
      {
        forumDescription: "General forum, talk whatever you want here",
        forumDisplay: true,
        forumId: 3,
        forumLocked: false,
        forumName: "General",
        parentId: 1,
      },
    ],
  },
]
6个回答

一个了解相互递归的绝好机会。输入可以是任何顺序 -

function makeIndex (items, indexer)
{ const append = (r, k, v) =>
    r.set(k, (r.get(k) || []).concat([ v ]))

  return items.reduce
    ( (r, i) => append(r, indexer(i), i)
    , new Map
    )
}

function makeTree (index, root = null)
{ const many = (all = []) =>
    all.map(one)

  const one = (forum = {}) =>
    ( { ...forum
      , subforums: many(index.get(forum.forumId))
      }
    )

  return many(index.get(root))
}

const input =
  [{forumId:1,parentId:null,forumName:"Main",forumDescription:"",forumLocked:false,forumDisplay:true},{forumId:2,parentId:1,forumName:"Announcements",forumDescription:"Announcements & Projects posted here",forumLocked:false,forumDisplay:true},{forumId:3,parentId:1,forumName:"General",forumDescription:"General forum, talk whatever you want here",forumLocked:false,forumDisplay:true},{forumId:4,parentId:3,forumName:"Introduction",forumDescription:"A warming introduction for newcomers here",forumLocked:false,forumDisplay:true}]

const result =
  makeTree(makeIndex(input, forum => forum.parentId))

console.log(JSON.stringify(result, null, 2))

[
  {
    "forumId": 1,
    "parentId": null,
    "forumName": "Main",
    "forumDescription": "",
    "forumLocked": false,
    "forumDisplay": true,
    "subforums": [
      {
        "forumId": 2,
        "parentId": 1,
        "forumName": "Announcements",
        "forumDescription": "Announcements & Projects posted here",
        "forumLocked": false,
        "forumDisplay": true,
        "subforums": []
      },
      {
        "forumId": 3,
        "parentId": 1,
        "forumName": "General",
        "forumDescription": "General forum, talk whatever you want here",
        "forumLocked": false,
        "forumDisplay": true,
        "subforums": [
          {
            "forumId": 4,
            "parentId": 3,
            "forumName": "Introduction",
            "forumDescription": "A warming introduction for newcomers here",
            "forumLocked": false,
            "forumDisplay": true,
            "subforums": []
          }
        ]
      }
    ]
  }
]

使其module化

上面makeIndex写的一种方式，它可以索引数据的任何数组，但makeTree做的假设一样...forum，subforums和forum.forumId。当我们在module中考虑我们的代码时，我们被迫划清界限，因此我们的程序变得清晰。

下面，input定义在main，所以我们保留所有关于input这里的知识-

// main.js
import { tree } from './tree'

const input =
  [{forumId:1,parentId:null,forumName:"Main",forumDescription:"",forumLocked:false,forumDisplay:true},{forumId:2,parentId:1,forumName:"Announcements",forumDescription:"Announcements & Projects posted here",forumLocked:false,forumDisplay:true},{forumId:3,parentId:1,forumName:"General",forumDescription:"General forum, talk whatever you want here",forumLocked:false,forumDisplay:true},{forumId:4,parentId:3,forumName:"Introduction",forumDescription:"A warming introduction for newcomers here",forumLocked:false,forumDisplay:true}]

const result =
  tree
    ( input                    // <- array of nodes
    , forum => forum.parentId  // <- foreign key
    , (forum, subforums) =>    // <- node reconstructor function
        ({ ...forum, subforums: subforums(forum.forumId) }) // <- primary key
    )

console.log(JSON.stringify(result, null, 2))

当我制作 a 时tree，我不想考虑制作index第一个。在我们原来的程序中，我怎么知道tree需要一个index？让我们让treemodule担心——

// tree.js
import { index } from './index'

const empty =
  {}

function tree (all, indexer, maker, root = null)
{ const cache =
    index(all, indexer)

  const many = (all = []) =>
    all.map(x => one(x))
                             // zero knowledge of forum object shape
  const one = (single) =>
    maker(single, next => many(cache.get(next)))

  return many(cache.get(root))
}

export { empty, tree } // <-- public interface

我们可以index直接在treemodule中编写函数，但我们想要的行为并不特定于树。编写一个单独的indexmodule更有意义 -

// index.js
const empty = _ =>
  new Map

const update = (r, k, t) =>
  r.set(k, t(r.get(k)))

const append = (r, k, v) =>
  update(r, k, (all = []) => [...all, v])

const index = (all = [], indexer) =>
  all.reduce
      ( (r, v) => append(r, indexer(v), v) // zero knowledge of v shape
      , empty()
      )

export { empty, index, append } // <-- public interface

编写module可以帮助您从有意义的部分思考代码，并提高代码的高度可重用性。

"A wonderful opportunity to learn about mutual recursion" @ScottSauyet 名言：D
2021-04-20 15:13:41
我从第一句话就知道这是谁写的！干得好，一如既往！
2021-05-05 15:13:41

由于父母可能会在输入中关注孩子，我想我会通过Map按 ID建立一个论坛来解决这个问题，然后将孩子添加到他们中：

function processInput(forumInput) {
    // Get a map of forums by ID
    const forumsById = new Map();
    for (const forum of forumInput) {
        forumsById.set(forum.forumId, forum);
    }

    // Add child forums to their parents
    for (const forum of forumInput) {
        const {parentId} = forum;
        if (parentId !== null) {
            const parent = forumsById.get(forum.parentId);
            parent.subForums = parent.subForums || []; // Or you could use `?? []` now
            parent.subForums.push(forum);
        }
    }

    // Return the parents array
    return [...forumsById.values()].filter(({parentId}) => parentId === null);
}

现场示例：

显示代码片段

请注意，如果论坛声称位于不在输入中的父论坛，则上述内容将引发错误。

我认为系统的方法是 1. 创建一个 id 到对象的映射 2. 创建一个父级 -> 子级的映射 3. 将所有父级添加到结果中 4. 递归添加子级（子论坛）

const input = [
  {
    forumId: 1,
    parentId: null,
    forumName: "Main",
    forumDescription: "",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 2,
    parentId: 1,
    forumName: "Announcements",
    forumDescription: "Announcements & Projects posted here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 3,
    parentId: 1,
    forumName: "General",
    forumDescription: "General forum, talk whatever you want here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 4,
    parentId: 3,
    forumName: "Introduction",
    forumDescription: "A warming introduction for newcomers here",
    forumLocked: false,
    forumDisplay: true,
  },
];

const mapIdToForums = input.reduce((acc, cur) => {
  acc[cur.forumId] = cur;
  return acc;
}, {});

const mapForumsToSubForums = input.reduce((acc, cur) => {
  parentId = cur.parentId || ""; // no parent
  acc[parentId] = acc[parentId] || [];
  acc[parentId].push(cur);
  return acc;
}, {});


const addChildren = (parent) => {
  var children = mapForumsToSubForums[parent.forumId];
  if (children) {
    parent.subForums = children

    children.forEach(c => addChildren(c));
  }
};

results = mapForumsToSubForums[""];
results.forEach(p => addChildren(p));
console.log(results);

您可以采用一个对象，该对象从具有子级的对象到父级和父级到子级的对象中获取所有关系，并获取没有父级的节点。

这种方法适用于任何深度、未排序的数据，并且只使用一个循环。

const
    input = [{ forumId: 3, parentId: 1, forumName: "General", forumDescription: "General forum, talk whatever you want here", forumLocked: false, forumDisplay: true }, { forumId: 2, parentId: 1, forumName: "Announcements", forumDescription: "Announcements & Projects posted here", forumLocked: false, forumDisplay: true }, { forumId: 4, parentId: 3, forumName: "Introduction", forumDescription: "A warming introduction for newcomers here", forumLocked: false, forumDisplay: true }, { forumId: 1, parentId: null, forumName: "Main", forumDescription: "", forumLocked: false, forumDisplay: true }],
    tree = function(data, root) {
        var t = {};
        data.forEach(o => {
            Object.assign(t[o.forumId] = t[o.forumId] || {}, o);
            t[o.parentId] = t[o.parentId] || {};
            t[o.parentId].subForums = t[o.parentId].subForums || [];
            t[o.parentId].subForums.push(t[o.forumId]);
        });
        return t[root].subForums;
    }(input, null);

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

我检查它是否适用于未排序数据的实验存在缺陷，抱歉。但是，当父母不存在时不提出问题的问题是真实的。
2021-04-27 15:13:41
@TJCrowder，只要项目具有定义的父项，这种方法就适用于未排序的数据。
2021-05-14 15:13:41
@NinaScholz 我在诸如“stateNames”、“session”、“$setCalled”、“emitter”、“_events”之类的对象上得到了奇怪的输出键，如果有什么改变，我正在使用 Node。
2021-05-19 15:13:41

作为其他一些答案，我会使用 a Mapto key nodes by their forumId，然后在相应的值中填充孩子：

let input = [{ forumId: 3, parentId: 1, forumName: "General", forumDescription: "General forum, talk whatever you want here", forumLocked: false, forumDisplay: true }, { forumId: 2, parentId: 1, forumName: "Announcements", forumDescription: "Announcements & Projects posted here", forumLocked: false, forumDisplay: true }, { forumId: 4, parentId: 3, forumName: "Introduction", forumDescription: "A warming introduction for newcomers here", forumLocked: false, forumDisplay: true }, { forumId: 1, parentId: null, forumName: "Main", forumDescription: "", forumLocked: false, forumDisplay: true }];

let root = {};
let map = new Map(input.map(o => [o.forumId, ({...o})]))
map.forEach(o => (p => p.subForms = (p.subForms || []).concat(o))(map.get(o.parentId) || root));
let result = root.subForms;

console.log(result);

其它你可能感兴趣的问题
上一篇Javascript - 检索对象属性路径 下一篇JavaScript 在 Squarespace 中只被调用一次