Find path to object in object nested array

I have an object, of which parameters contain and array of object. I receive 1 object id and I need to find its position in that whole mess. With procedural programming I got it working with:

const opportunitiesById =  {
  1: [
    { id: 1, name: 'offer 1' },
    { id: 2, name: 'offer 1' }
  ],
  2: [
    { id: 3, name: 'offer 1' },
    { id: 4, name: 'offer 1' }
  ],
  3: [
    { id: 5, name: 'offer 1' },
    { id: 6, name: 'offer 1' }
  ]
};

const findObjectIdByOfferId = (offerId) => {
  let opportunityId;
  let offerPosition;
  const opportunities = Object.keys(opportunitiesById);

  opportunities.forEach(opportunity => {
    const offers = opportunitiesById[opportunity];

    offers.forEach((offer, index) => {
      if (offer.id === offerId) {
        opportunityId = Number(opportunity);
        offerPosition = index;
      }
    })
  });

return { offerPosition, opportunityId };
}

console.log(findObjectIdByOfferId(6)); // returns { offerPosition: 1, opportunityId: 3 }

However this is not pretty and I want to do that in a functional way. I've looked into Ramda, and I can find an offer when I'm looking into a single array of offers, but I can't find a way to look through the entire object => each array to find the path to my offer.

R.findIndex(R.propEq('id', offerId))(opportunitiesById[1]);

The reason I need to know the path is because I then need tho modify that offer with new data and update it back where it is.

Thanks for any help

标签： functional-programming ramda.js

3条回答

姐就是有狂的资本

2楼-- · 2020-02-07 06:37

I would transform your object into pairs.

So for example transforming this:

{ 1: [{id:10}, {id:20}],
  2: [{id:11}, {id:21}] }

into that:

[ [1, [{id:10}, {id:20}]],
  [2, [{id:11}, {id:21}]] ]

Then you can iterate over that array and reduce each array of offers to the index of the offer you're looking for. Say you're looking for offer #21, the above array would become:

[ [1, -1],
  [2,  1] ]

Then you return the first tuple which second element isn't equal to -1:

[2, 1]

Here's how I'd suggest doing this:

const opportunitiesById =  {
  1: [ { id: 10, name: 'offer 1' },
       { id: 20, name: 'offer 2' } ],
  2: [ { id: 11, name: 'offer 3' },
       { id: 21, name: 'offer 4' } ],
  3: [ { id: 12, name: 'offer 5' },
       { id: 22, name: 'offer 6' } ]
};

const findOfferPath = (id, offers) =>
  pipe(
    toPairs,
    transduce(
      compose(
        map(over(lensIndex(1), findIndex(propEq('id', id)))),
        reject(pathEq([1], -1)),
        take(1)),
      concat,
      []))
    (offers);


console.log(findOfferPath(21, opportunitiesById));

<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.26.1/ramda.min.js"></script>
<script>const {pipe, transduce, compose, map, over, lensIndex, findIndex, propEq, reject, pathEq, take, concat, toPairs} = R;</script>

Then you can take that path to modify your offer as you see fit:

const opportunitiesById =  {
  1: [ { id: 10, name: 'offer 1' },
       { id: 20, name: 'offer 2' } ],
  2: [ { id: 11, name: 'offer 3' },
       { id: 21, name: 'offer 4' } ],
  3: [ { id: 12, name: 'offer 5' },
       { id: 22, name: 'offer 6' } ]
};

const updateOffer = (path, update, offers) =>
  over(lensPath(path), assoc('name', update), offers);

console.log(updateOffer(["2", 1], '


             
            
                                  
            
            
            
            
            
            beautiful°                          
            
             
             3楼-- · 2020-02-07 06:44
             
             
             
                          
             
                                                                          
        You could piece it together using lots of little functions but I want to show you how to encode your intentions in a more straightforward way. This program has an added benefit that it will return immediately. Ie, it will not continue to search thru additional key/value pairs after a match is found.

Here's a way you can do it using mutual recursion. First we write findPath - 

const identity = x =>
  x

const findPath =
  ( f = identity
  , o = {}
  , path = []
  ) =>
    Object (o) === o
      ? f (o) === true
        ? path
        : findPath1 (f, Object .entries (o), path)
      : undefined


If the input is an object, we pass it to the user's search function f. If the user's search function returns true, a match has been found and we return the path. If there is not match, we search each key/value pair of the object using a helper function. Otherwise, if the input is not an object, there is no match and nothing left to search, so return undefined. We write the helper, findPath1 -

const None =
  Symbol ()

const findPath1 =
  ( f = identity
  , [ [ k, v ] = [ None, None ], ...more ]
  , path = []
  ) =>
    k === None
      ? undefined
      : findPath (f, v, [ ...path, k ])
        || findPath1 (f, more, path)


If the key/value pairs have been exhausted, there is nothing left to search so return undefined. Otherwise we have a key k and a value v; append k to the path and recursively search v for a match. If there is not a match, recursively search the remaining key/values, more, using the same path.

Note the simplicity of each function. There's nothing happening except for the absolute minimum number of steps to assemble a path to the matched object. You can use it like this -

const opportunitiesById = 
  { 1:
      [ { id: 1, name: 'offer 1' }
      , { id: 2, name: 'offer 1' }
      ]
  , 2:
      [ { id: 3, name: 'offer 1' }
      , { id: 4, name: 'offer 1' }
      ]
  , 3:
      [ { id: 5, name: 'offer 1' }
      , { id: 6, name: 'offer 1' }
      ]
  }

findPath (offer => offer.id === 6, opportunitiesById)
// [ '3', '1' ]


The path returned leads us to the object we wanted to find -

opportunitiesById['3']['1']
// { id: 6, name: 'offer 1' }


We can specialize findPath to make an intuitive findByOfferId function -

const findByOfferId = (q = 0, data = {}) =>
  findPath (o => o.id === q, data)

findByOfferId (3, opportunitiesById)
// [ '2', '0' ]

opportunitiesById['2']['0']
// { id: 3, name: 'offer 1' }


Like Array.prototype.find, it returns undefined if a match is never found -

findByOfferId (99, opportunitiesById)
// undefined


Expand the snippet below to verify the results in your own browser -



const identity = x =>
  x

const None =
  Symbol ()

const findPath1 =
  ( f = identity
  , [ [ k, v ] = [ None, None ], ...more ]
  , path = []
  ) =>
    k === None
      ? undefined
      : findPath (f, v, [ ...path, k ])
        || findPath1 (f, more, path)

const findPath =
  ( f = identity
  , o = {}
  , path = []
  ) =>
    Object (o) === o
      ? f (o) === true
        ? path
        : findPath1 (f, Object .entries (o), path)
      : undefined

const findByOfferId = (q = 0, data = {}) =>
  findPath (o => o.id === q, data)

const opportunitiesById = 
  { 1:
      [ { id: 1, name: 'offer 1' }
      , { id: 2, name: 'offer 1' }
      ]
  , 2:
      [ { id: 3, name: 'offer 1' }
      , { id: 4, name: 'offer 1' }
      ]
  , 3:
      [ { id: 5, name: 'offer 1' }
      , { id: 6, name: 'offer 1' }
      ]
  }

console .log (findByOfferId (3, opportunitiesById))
// [ '2', '0' ]

console .log (opportunitiesById['2']['0'])
// { id: 3, name: 'offer 1' }

console .log (findByOfferId (99, opportunitiesById))
// undefined






In this related Q&A, I demonstrate a recursive search function that returns the matched object, rather than the path to the match. There's other useful tidbits to go along with it so I'll recommend you to give it a look.



Scott's answer inspired me to attempt an implementation using generators. We start with findPathGen -

const identity = x =>
  x

const findPathGen = function*
( f = identity
, o = {}
, path = []
)
{ if (Object (o) === o)
    if (f (o) === true)
      yield path
    else
      yield* findPathGen1 (f, Object .entries (o), path)
}


And using mutual recursion like we did last time, we call on helper findPathGen1 -

const findPathGen1 = function*
( f = identity
, entries = []
, path = []
)
{ for (const [ k, v ] of entries)
    yield* findPathGen (f, v, [ ...path, k ])
}


Finally, we can implement findPath and the specialization findByOfferId -

const first = ([ a ] = []) =>
  a

const findPath = (f = identity, o = {}) =>
  first (findPathGen (f, o))

const findByOfferId = (q = 0, data = {}) =>
  findPath (o => o.id === q, data)


It works the same -

findPath (offer => offer.id === 3, opportunitiesById)
// [ '2', '0' ]

findPath (offer => offer.id === 99, opportunitiesById)
// undefined

findByOfferId (3, opportunitiesById)
// [ '2', '0' ]

findByOfferId (99, opportunitiesById)
// undefined


And as a bonus, we can implement findAllPaths easily using Array.from -

const findAllPaths = (f = identity, o = {}) =>
  Array .from (findPathGen (f, o))

findAllPaths (o => o.id === 3 || o.id === 6, opportunitiesById)
// [ [ '2', '0' ], [ '3', '1' ] ]


Verify the results by expanding the snippet below



const identity = x =>
  x

const findPathGen = function*
( f = identity
, o = {}
, path = []
)
{ if (Object (o) === o)
    if (f (o) === true)
      yield path
    else
      yield* findPathGen1 (f, Object .entries (o), path)
}

const findPathGen1 = function*
( f = identity
, entries = []
, path = []
)
{ for (const [ k, v ] of entries)
    yield* findPathGen (f, v, [ ...path, k ])
}

const first = ([ a ] = []) =>
  a

const findPath = (f = identity, o = {}) =>
  first (findPathGen (f, o))


const findByOfferId = (q = 0, data = {}) =>
  findPath (o => o.id === q, data)

const opportunitiesById = 
  { 1:
      [ { id: 1, name: 'offer 1' }
      , { id: 2, name: 'offer 1' }
      ]
  , 2:
      [ { id: 3, name: 'offer 1' }
      , { id: 4, name: 'offer 1' }
      ]
  , 3:
      [ { id: 5, name: 'offer 1' }
      , { id: 6, name: 'offer 1' }
      ]
  }

console .log (findByOfferId (3, opportunitiesById))
// [ '2', '0' ]

console .log (findByOfferId (99, opportunitiesById))
// undefined

// --------------------------------------------------
const findAllPaths = (f = identity, o = {}) =>
  Array .from (findPathGen (f, o))

console .log (findAllPaths (o => o.id === 3 || o.id === 6, opportunitiesById))
// [ [ '2', '0' ], [ '3', '1' ] ]



    
                                                                    
                                                        
            
              
                查看更多
                
             
              0人赞

                                                     添加讨论(0)

                                                                                                            
                               举报
                
                
                
                  
                


                        
                            

                               
             
                        
               
            

                            
                            
                                 加载中...
                            
                        

                
             
            
                                  
            
            
            
            
            
            Root（大扎）                          
            
             
             4楼-- · 2020-02-07 06:49
             
             
             
                          
             
                                                                          
        Here's another approach:

We start with this generator function:

function * getPaths(o, p = []) {
  yield p 
  if (Object(o) === o)
    for (let k of Object .keys (o))
      yield * getPaths (o[k], [...p, k])
} 


which can be used to find all the paths in an object:

const obj = {a: {x: 1, y: 3}, b: {c: 2, d: {x: 3}, e: {f: {x: 5, g: {x: 3}}}}}

;[...getPaths(obj)]
//~> [[], ["a"], ["a", "x"], ["a", "y"], ["b"], ["b", "c"], ["b", "d"], 
//    ["b", "d", "x"], ["b", "e"], ["b", "e", "f"], ["b", "e", "f", "x"], 
//    ["b", "e", "f", "g"], ["b", "e", "f", "g", "x"]]


and then, with this little helper function:

const path = (ps, o) => ps.reduce((o, p) => o[p] || {}, o)


we can write

const findPath = (predicate, o) =>
  [...getPaths(o)] .find (p => predicate (path (p, o) ) )


which we can call like

console.log(
  findPath (a => a.x == 3, obj)
) //~> ["b","d"]


We can then use these functions to write a simple version of your function:

const findByOfferId = (id, data) =>
  findPath (o => o.id === id, data)

const opportunitiesById =  {
  1: [ { id: 10, name: 'offer 1' }, { id: 20, name: 'offer 2' } ],
  2: [ { id: 11, name: 'offer 3' }, { id: 21, name: 'offer 4' } ],
  3: [ { id: 12, name: 'offer 5' }, { id: 22, name: 'offer 6' } ]
}

console.log(
  findByOfferId (22, opportunitiesById)
) //~> ["3", "1"]

console.log(
  findByOfferId (42, opportunitiesById)
) //~> undefined




It is trivial to extend this to get all paths for which the value satisfies the predicate, simply replacing find with filter:

const findAllPaths = (predicate, o) =>
  [...getPaths(o)] .filter (p => predicate (path(p, o) ) )

console.log(
  findAllPaths (a => a.x == 3, obj)
) //=> [["b","d"],["b","e","f","g"]]




There is a concern with all this, though.  Even though findPath only needs to find the first match, and even though getPaths is a generator and hence lazy, we force the full run of it with [...getPaths(o)].  So it might be worth using this uglier, more imperative version:

const findPath = (predicate, o) => {
  let it = getPaths(o)
  let res = it.next()
  while (!res.done) {
    if (predicate (path (res.value, o) ) )
      return res.value
    res = it.next()
  }
}




This is what it looks like all together:



function * getPaths(o, p = []) {
  yield p 
  if (Object(o) === o)
    for (let k of Object .keys (o))
      yield * getPaths (o[k], [...p, k])
}

const path = (ps, o) => ps.reduce ((o, p) => o[p] || {}, o)

   
// const findPath = (pred, o) =>
//   [...getPaths(o)] .find (p => pred (path (p, o) ) )


const findPath = (predicate, o) => {
  let it = getPaths(o)
  let res = it.next()
  while (!res.done) {
    if (predicate (path (res.value, o) ) )
      return res.value
    res = it.next()
  }
}

const obj = {a: {x: 1, y: 3}, b: {c: 2, d: {x: 3}, e: {f: {x: 5, g: {x: 3}}}}}

console.log(
  findPath (a => a.x == 3, obj)
) //~> ["b","d"]

const findAllPaths = (pred, o) =>
  [...getPaths(o)] .filter (p => pred (path(p, o) ) )

console.log(
  findAllPaths (a => a.x == 3, obj)
) //~> [["b","d"],["b","e","f","g"]]


const findByOfferId = (id, data) =>
  findPath (o => o.id === id, data)

const opportunitiesById =  {
  1: [ { id: 10, name: 'offer 1' }, { id: 20, name: 'offer 2' } ],
  2: [ { id: 11, name: 'offer 3' }, { id: 21, name: 'offer 4' } ],
  3: [ { id: 12, name: 'offer 5' }, { id: 22, name: 'offer 6' } ]
}

console.log(
  findByOfferId (22, opportunitiesById)
) //~> ["3", "1"]

console.log(
  findByOfferId (42, opportunitiesById)
) //~> undefined






Another brief note: the order in which the paths are generated is only one possibility.  If you want to change from pre-order to post-order, you can move the yield p line in getPaths from the first line to the last one.



Finally, you asked about doing this with functional techniques, and mentioned Ramda.  As the solution from customcommander shows, you can do this with Ramda.  And the (excellent as always) answer from user633183 demonstrates, it's possible to do this with mainly functional techniques.

I still find this a somewhat simpler approach.  Kudos to customcommander for finding a Ramda version, because Ramda is not particularly well-suited for recursive tasks, but still the obvious approach to something that has to visit the nodes of a recursive structure like a JS object is to use a recursive algorithm.  I'm one of the authors of Ramda, and I haven't even tried to understand how that solution works.

Update

user633183 pointed out that this would be simpler, and still lazy:

const findPath = (predicate, o) => {
  for (const p of getPaths(o)) 
    if (predicate (path (p, o)) ) 
      return p
}

    
                                                                    
                                                        
            
              
                查看更多
                
             
              0人赞

                                                     添加讨论(0)

                                                                                                            
                               举报
                
                
                
                  
                


                        
                            

                               
             
                        
               
            

                            
                            
                                 加载中...


     
                      登录 后发表回答



   
   
   
  
   相关问题
      
    
    
   
   

     


   
   Relation between Function1 and Reader Monad   

   



     


   
   scala passing function with underscore produces a   

   



     


   
   How to use Ramda Pipe function with a mix of promi   

   



     


   
   Combining n vectors into one vector of n-tuples   

   



     


   
   Improve this code by eliminating nested for cycles   

   



        
      
    查看全部
   
   
  
   相关文章
 
   
   

     


   
   Is there something like the threading macro from C   

     


   
   Learning F#: What books using other programming la   

     


   
   Creating a list of functions using a loop in R   

     


   
   When to use interfaces, and when to use higher ord   

     


   
   Functors in Ocaml   

     


   
   Java Lambda Referencing Enclosing Object: Replace    

     


   
   Are 'currying' and 'composition' t   

     


   
   Control.Parallel compile issue in Haskell   

        
        
    查看全部
                 收藏的人(5)





  
    
      
      采纳回答
    
    

     
        
        
        
            
                向帮助了您的知道网友说句感谢的话吧!
            
            
                
                    
                        非常感谢!

Find path to object in object nested array

Update

采纳回答

编辑标签

举报内容

检举类型

检举原因

检举说明(必填)

打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮

付费偷看金额在0.1-10元之间