时间戳

首页 > 解决方案 > Recursive array enumeration in JS

javascript - Recursive array enumeration in JS

问题描述

Please tell me how to iterate over an array with unknown nesting? The situation is this, I practice js and reactjs at the initial level, I make an app with Pokemon and I want to derive a component with evolution :). The API returns an object of the following form:

{
  baby_trigger_item: null,
  chain: {
    evolution_details: [],
    evolves_to: [
      {
        evolves_to: [
          {
            evolves_to: [],
            is_baby: false,
            species: {
              name: "poliwrath",
              url: "https://pokeapi.co/api/v2/pokemon-species/62/"
            }
          },
          {
            evolves_to: [],
            is_baby: false,
            species: {
              name: "politoed",
              url: "https://pokeapi.co/api/v2/pokemon-species/186/"
            }
          }
        ],
        is_baby: false,
        species: {
          name: "poliwhirl",
          url: "https://pokeapi.co/api/v2/pokemon-species/61/"
        }
      }
    ],
    is_baby: false,
    species: {
      name: "poliwag",
      url: "https://pokeapi.co/api/v2/pokemon-species/60/"
    }
  },
  id: 26
};

The number of nested evolves_to arrays can be many.and inside "evolves_to" there can be several objects, that is, the development of one level in several types. It should turn out (I think such a structure will be convenient in future work): 

[
    [
      {
        name: "",
        url: ""
      }
    ],
    [
      {
        name: "",
        url: ""
      },
      {
        name: "",
        url: ""
      }
    ][
      {
        name: "",
        url: ""
      }
    ]
  ]

That is, the first array with the first level of evolution, the second array, the second level of the array with two types, the third array, respectively, the third level, etc. If the nesting is not known, then me need to somehow operate with recursion? I tried to use map, reduce ... I tried to inject recursion into them ... but unfortunately I haven’t thought of it yet. If it doesn’t make it difficult - help. Thank you in advance )

UPD: Here is the code that evolves_to collects.species to a single object and adds to the array. but it doesn't take into account if there are several species in evolves_to. if they are on the same level, they should be in the same array:

data={
  baby_trigger_item: null,
  chain: {
    evolution_details: [],
    evolves_to: [
      {
        evolves_to: [
          {
            evolves_to: [],
            is_baby: false,
            species: {
              name: "poliwrath",
              url: "https://pokeapi.co/api/v2/pokemon-species/62/"
            }
          },
          {
            evolves_to: [],
            is_baby: false,
            species: {
              name: "politoed",
              url: "https://pokeapi.co/api/v2/pokemon-species/186/"
            }
          }
        ],
        is_baby: false,
        species: {
          name: "poliwhirl",
          url: "https://pokeapi.co/api/v2/pokemon-species/61/"
        }
      }
    ],
    is_baby: false,
    species: {
      name: "poliwag",
      url: "https://pokeapi.co/api/v2/pokemon-species/60/"
    }
  },
  id: 26
};

let resultUPD = [];
resultUPD.push([data.chain.species]);
const getEvolves = object => {
  if (Array.isArray(object.evolves_to) && !object.evolves_to.length) {
    return object.evolves_to;
  }
  const resultNew = object.evolves_to.map(evolves =>
    getEvolves(evolves)
  );
  return [...object.evolves_to, ...resultNew].flat();
};
getEvolves(data.chain).map(elem =>
  resultUPD.push([elem.species])
);
console.log("result", resultUPD);

标签： javascriptarraysobjectrecursion

解决方案

I really did try to tease out the underlying requirements in the comments. Unfortunately, we didn't seem to be able to communicate properly. Either the OP did not understand what I was asking about, or I couldn't follow the OP's responses.

So there are a number of different answer that might meet the needs, and it's not clear to me which one of them -- if any -- is closest.

But first, let's talk about data structures.

Trees

Trees are one of the most common data structures. The data in this problem is a tree. Trees can be coded in many different ways, but the basic idea is that there is one root node, and it has some number of descendants. Each of those descendants, in turn, may have descendants of their own, and so forth.

This is a representation of a tree, perhaps a maternal family tree with Betty at the root:

                           Betty
                        _____|_____
                       /           \
                    Kathy          Grace
                   ___|___           |
                  /   |   \          |
             Alice  Carrie Helen   Faith
                    __|__          __|__
                   /     \        /     \
                Denise  Julie  Irene   Ellie
                                 |
                                 |
                              Louisa

Betty has two daughters, Kathy and Grace. Kathy has three daughters; Grace has one, etc.

If we need do do something with the nodes of a tree, there are several ways we could proceed. If we need to keep the tree structure, but transform the nodes, we might map over the tree, perhaps with a function that takes the first letter of the name, turning the above into this:

                             B
                        _____|_____
                       /           \
                      K             G
                   ___|___          |
                  /   |   \         |
                 A    C    H        F
                    __|__         __|__
                   /     \       /     \
                  D       J     I       E
                                |
                                |
                                L

If we don't need to maintain the shape of the tree, but just need to visit each node, then there are two usual ways we might proceed. We can go breadth-first or depth-first. Breadth-first is the equivalent of scanning row-by-row, so that we would visit this tree in the order Betty, Kathy, Grace, Alice, Carrie, Helen, Faith, Denise, Julie, Irene, Ellie, and Louisa.

Depth-first has several variants, pre-order and post-order. (For binary trees, there is another variant, called in-order, but that's not relevant here.) In either of them we explore one branch of the tree thoroughly before moving on to another. In pre-order, we visit a node before visiting its children, which gives us a traversal order for that tree of Betty, Kathy, Alice, Carrie, Denise, Julie, Helen, Grace, Faith, Irene, Louisa, and Ellie. In post-order, we visit the children before we visit the node, which yields a traversal order of Alice, Denise, Julie, Carrie, Helen, Louisa, Irene, Ellie, Faith, Grace, and Betty.

(All of these traversal types also have a reversed version, which I rarely use and won't mention again here.)

Your Pokemon Tree

The data you get back from your service call forms a tree, with the evolves_to property pointing to the children of your node. The question is about traversing the nodes of this tree. It's not entirely clear to me what the goal of that traversal is, whether you need to modify the nodes of tree in place, to simply get certain content from each in some particular order or any order at all, to visit the nodes in a given fixed order to build a new structure, or something else. Here we discuss variations that do some of these things.

In all of them, we pass a function to describe our parent-child relationship. The idea is that the basics of traversal remain the same for many different structures. If we have a node and a function that allows us to list its children, then we can reuse our traversals across this and many other structures. I find that it's worth keeping these, even if you're not going to reuse the code elsewhere now. It makes it easier to think abstractly about the problem, and leave the details elsewhere. So each main function discussed takes a parameter, getChildren, which must be a function from a node to an array of children. In all these examples, we simply pass it node => node.evolves_to. But in another structure, it might be node => node.children or something more sophisticated.

Depth-first, pre-order traversal

One way to traverse the nodes and map them to nodes more useful to us is to iterate them in a depth-first manner. This version chooses to do pre-order, in which the parent node is iterated before its children, but changing it to post-order is trivial.

const depthFirst = (getChildren) => (node) => 
  [
    node, 
    ... (getChildren (node) || []) .flatMap (depthFirst (getChildren)),
  ]

const makePokeList = (pokes) =>
  depthFirst (node => node.evolves_to) (pokes .chain) 
    .map (({species}) => species)


const pokes = {baby_trigger_item: null, chain: {evolution_details: [], evolves_to: [{evolves_to: [{evolves_to: [], is_baby: false, species: {name: "poliwrath", url: "https://pokeapi.co/api/v2/pokemon-species/62/"}}, {evolves_to: [], is_baby: false, species: {name: "politoed", url: "https://pokeapi.co/api/v2/pokemon-species/186/"}}], is_baby: false, species: {name: "poliwhirl", url: "https://pokeapi.co/api/v2/pokemon-species/61/"}}], is_baby: false, species: {name: "poliwag", url: "https://pokeapi.co/api/v2/pokemon-species/60/"}}, id: 26};

console .log (
  makePokeList (pokes)
)
.as-console-wrapper {min-height: 100% !important; top: 0}

  • depthFirst converts our tree into an array in a pre-order, depth-first manner. This is generic, and can be adapted to many different tree structures by passing the proper getChildren function. (If you want post-order instead, it's trivial: simply swap the two lines in the returned array, returning the node line after the ... getChildren ( ... ) one.) Note that all this function does is to flatten that tree into a list in the proper order.

  • makePokeList is more specific to this problem. It converts a tree using our common node => node.evolvesTo function into a list, removing the child nodes from each element, and then extracting the species node from our elements. It also starts by grabbing the tree node (poke .chan) out of the larger input structure. This gives us an output like the following:

[
    {name: "poliwag", url: "https://pokeapi.co/api/v2/pokemon-species/60/"},
    {name: "poliwhirl", url: "https://pokeapi.co/api/v2/pokemon-species/61/"},
    {name: "poliwrath", url: "https://pokeapi.co/api/v2/pokemon-species/62/"},
    {name: "politoed", url: "https://pokeapi.co/api/v2/pokemon-species/186/"}
]

The depthFirst function can be used in other ways. If you don't want to map over the results, you could also filter them, reduce them to a single value, or even simply visit each one with the visitor pattern:

const depthFirst = (getChildren) => (tree) => 
  [
    tree, 
    ... (getChildren (tree) || []) .flatMap (depthFirst (getChildren)),
  ]

const visitPokes = (visitor) => (pokes) => 
  depthFirst (node => node.evolves_to) (pokes .chain) 
    .forEach (({evolves_to, ...rest}) => visitor (rest))

const pokes = {baby_trigger_item: null, chain: {evolution_details: [], evolves_to: [{evolves_to: [{evolves_to: [], is_baby: false, species: {name: "poliwrath", url: "https://pokeapi.co/api/v2/pokemon-species/62/"}}, {evolves_to: [], is_baby: false, species: {name: "politoed", url: "https://pokeapi.co/api/v2/pokemon-species/186/"}}], is_baby: false, species: {name: "poliwhirl", url: "https://pokeapi.co/api/v2/pokemon-species/61/"}}], is_baby: false, species: {name: "poliwag", url: "https://pokeapi.co/api/v2/pokemon-species/60/"}}, id: 26};

visitPokes (console .log) (pokes)

  • visitPokes accepts a function which takes a node and does something with it. It does not do anything with those results, so this is mostly good for generating side-effects (such as console.logging the node, or storing it in the DOM.) Here we test it by simply logging each node.

Breadth-first traversal

Alternately, we could traverse this in a breadth-first manner. This, recall, visits all the descendants on one level before moving to the next. Thus it visits the root, then all the root's children, then all of their children, and so on. This version breaks down much like the earlier one:

const breadthFirst = (getChildren) => (nodes) => {
  const children = nodes .flatMap (node => getChildren (node) || [])
  return [ 
    ... nodes, 
    ... (children.length ? breadthFirst (getChildren) (children) : [])
  ]
}

const makePokesList = (pokes) => 
  breadthFirst (node => node .evolves_to) ([pokes .chain])
    .map ((({species}) => species) )

const pokes = {baby_trigger_item: null, chain: {evolution_details: [], evolves_to: [{evolves_to: [{evolves_to: [], is_baby: false, species: {name: "poliwrath", url: "https://pokeapi.co/api/v2/pokemon-species/62/"}}, {evolves_to: [], is_baby: false, species: {name: "politoed", url: "https://pokeapi.co/api/v2/pokemon-species/186/"}}], is_baby: false, species: {name: "poliwhirl", url: "https://pokeapi.co/api/v2/pokemon-species/61/"}}], is_baby: false, species: {name: "poliwag", url: "https://pokeapi.co/api/v2/pokemon-species/60/"}}, id: 26};

console .log (
  makePokesList (pokes)
)

You will notice that the results look just like the depth-first one above. That's only because your tree is so simple. For anything more complex, these will likely be different.

The breadthFirst function recursively takes an array of nodes. But to start it off, we have a single root node. Here we dealt with that by wrapping the root node in an array before calling, inside makePokeList. Often, it would be better to make that an internal helper function and writing a wrapper function which does nothing more than doing that array-wrapping, something like this:

const _breadthFirst = (getChildren) => (nodes) => {
  const children = nodes .flatMap (node => getChildren (node) || [])
  return [ 
    ... nodes, 
    ... (children.length ? _breadthFirst (getChildren) (children) : [])
  ]
}

const breadthFirst = (getChildren) => (node) => _breadthFirst (getChildren) ([node])

Then of course makePokesList would call it using (poke .chain) rather than ([poke .chain]).

But that's mostly a minor point. Overall, this feels very similar to the our depth-first solution, changing only the order of iteration. The following one, though, is substantially different:

Mapping our tree

I can't tell this actually fits your requirements, but another transformation does not involve an iteration of the nodes, only a mapping of the current nodes into new ones, keeping the tree structure intact. This was demonstrated on the initial example of a tree, when we created a new tree from the old by taking the first letter of each node.

(This transformation of a structure to another of the same shape but with different data is captured by the typeclass Functor. This is very much worth learning about, but would take us far afield here.)

Here's one implementation, again using a getChildren function, and:

const mapTree = (getChildren, setChildren) => (fn) => (node) =>
  setChildren ((getChildren (node) || []) .map (mapTree (getChildren, setChildren) (fn)), fn (node))

const makePokeList = pokes => mapTree 
  (node => node .evolves_to, (children, node) => ({...node, evolves_to: children}))
  (node => node .species)
  (pokes.chain)

const pokes = {baby_trigger_item: null, chain: {evolution_details: [], evolves_to: [{evolves_to: [{evolves_to: [], is_baby: false, species: {name: "poliwrath", url: "https://pokeapi.co/api/v2/pokemon-species/62/"}}, {evolves_to: [], is_baby: false, species: {name: "politoed", url: "https://pokeapi.co/api/v2/pokemon-species/186/"}}], is_baby: false, species: {name: "poliwhirl", url: "https://pokeapi.co/api/v2/pokemon-species/61/"}}], is_baby: false, species: {name: "poliwag", url: "https://pokeapi.co/api/v2/pokemon-species/60/"}}, id: 26};

console .log (
  makePokeList (pokes)
)

The first parameter to mapTree is our common getChildren. The second one is a function that transforms a node. It accepts a node and a list of its children, and can return whatever you want, but presumably it's a new node with the children properly included. There is probably a somewhat more robust version of this that includes a placeChildren function similar to our getChildren that would leave the main function

This yields an output like this:

{
  "name": "poliwag",
  "url": "https://pokeapi.co/api/v2/pokemon-species/60/",
  "evolves_to": [
    {
      "name": "poliwhirl",
      "url": "https://pokeapi.co/api/v2/pokemon-species/61/",
      "evolves_to": [
        {
          "name": "poliwrath",
          "url": "https://pokeapi.co/api/v2/pokemon-species/62/",
          "evolves_to": []
        },
        {
          "name": "politoed",
          "url": "https://pokeapi.co/api/v2/pokemon-species/186/",
          "evolves_to": []
        }
      ]
    }
  ]
}

If you don't want the empty children nodes, you can replace (children, node) => ({...node, evolves_to: children}) with (children, node) => ({...node, ...(children.length ? {evolves_to: children} : {})}). Or if you want a different name for the children nodes, you could write (children, node) => ({...node, kids: children}), or simply (children, node) => ({...node, children}).

This, of course, does not give you any particular iteration order; it simply creates a new tree. But that may be what you need.

Level-based nested array

The closest I can come to what it seems like what you ask for is a technique that groups things by level. In our initial tree that would mean a nested array like 

[
  ['Betty'],
  ['Kathy', 'Grace'],
  ['Alice', 'Carrie', 'Helen', 'Faith'],
  ['Denise', 'Julie', 'Irene', 'Ellie'],
  ['Louisa'] 
]

I personally find this a fairly odd structure. It would not, for instance, let you distinguish between these two trees:

                 B                               B            
            _____|_____                     _____|_____       
           /           \                   /           \      
          K             G                 K             G     
       ___|___          |              ___|___        __|__     
      /   |   \         |             /       \      /     \
     A    C    H        F            A         C    H       F     
        __|__         __|__          |         |    |       |
       /     \       /     \         |         |    |       |  
      D       J     I       E        D         J    I       E 
                    |                |                
                    |                |                      
                    L                L

But if it's what you want, we can create something like this out of an extension to our depth-first search. The trick is to capture some additional information to our nodes. If we track the ancestry of our node from the root, as well as its content, then it's easy to build this by grouping on the length of the ancestors array. That would also let us do more sophisticated things such as building out nodes like poliwag > poliwhirl > poliwrath and poliwag > poliwhirl > politoed out of your input, which might be useful.

So in this version, depthFirst carries an extra parameter around alongside the node, called path:

const depthFirst = (getChildren) => (tree, path) => 
  [
    {node: tree, path}, 
    ... (getChildren (tree) || []) .flatMap (node => depthFirst (getChildren) (node, [... path, tree]))
  ]

const makePokes = pokes => 
  Object .values (depthFirst (node => node .evolves_to) (pokes .chain, []) 
    .map (({node, path}) => ({node, depth: path .length})) 
    .reduce ((a, {node, depth}) => ({...a, [depth]: [...(a [depth] || []), node .species]}), {}))

const pokes = {baby_trigger_item: null, chain: {evolution_details: [], evolves_to: [{evolves_to: [{evolves_to: [], is_baby: false, species: {name: "poliwrath", url: "https://pokeapi.co/api/v2/pokemon-species/62/"}}, {evolves_to: [], is_baby: false, species: {name: "politoed", url: "https://pokeapi.co/api/v2/pokemon-species/186/"}}], is_baby: false, species: {name: "poliwhirl", url: "https://pokeapi.co/api/v2/pokemon-species/61/"}}], is_baby: false, species: {name: "poliwag", url: "https://pokeapi.co/api/v2/pokemon-species/60/"}}, id: 26};

console .log (
  makePokes (pokes)
)

This is overkill for our current problem, and we could just pass around a depth parameter. But functions like this are meant to be fairly generic, and since we have the whole path, it seems better to supply it, letting our problem-specifi code, makePokes, deal with only using the relevant bit, the length of the paths array.

makePokes is more complex here. We use this version of depthFirst to collect an array of {node, path} objects, and then group the species properties of the nodes into arrays according to the length of the path, then we call Object.values to take only these arrays.

Conclusions

No, never mind, I'm too tired. I hope one of those techniques works for you.

推荐阅读