I keep running into situations where I end up nesting very many reduce
functions to drill down into an object. It's hard to pull out the logic because at the bottom I need access to the various keys traversed along the way. Essentially, I'm looking for a better way to achieve the following:
import { curry } from 'lodash/fp'
import { fromJS } from 'immutable'
const reduce = curry((fn, acc, it) => it.reduce(fn, acc))
describe('reduceNested', () => {
const input = fromJS({
a1: {
b1: {
c1: {
d1: {
e1: 'one',
e2: 'two',
e3: 'three'
},
d2: {
e1: 'one',
e2: 'two',
e3: 'three'
}
},
c2: {
d1: {
e1: 'one',
e2: 'two'
}
}
}
},
a2: {
b1: {
c1: {
d1: {
e1: 'one'
},
d2: {
e1: 'one'
}
}
},
b2: {
c1: {
d1: {
e1: 'one'
},
d2: {
e1: 'one'
}
}
}
},
a3: {
b1: {
c1: {}
}
}
})
const expected = fromJS({
one: [
'a1.b1.c1.d1.e1',
'a1.b1.c1.d2.e1',
'a1.b1.c2.d1.e1',
'a2.b1.c1.d1.e1',
'a2.b1.c1.d2.e1',
'a2.b2.c1.d1.e1',
'a2.b2.c1.d2.e1'
],
two: ['a1.b1.c1.d1.e2', 'a1.b1.c1.d2.e2', 'a1.b1.c2.d1.e2'],
three: ['a1.b1.c1.d1.e3', 'a1.b1.c1.d2.e3']
})
const init = fromJS({ one: [], two: [], three: [] })
test('madness', () => {
const result = reduce(
(acc2, val, key) =>
reduce(
(acc3, val2, key2) =>
reduce(
(acc4, val3, key3) =>
reduce(
(acc5, val4, key4) =>
reduce(
(acc6, val5, key5) =>
acc6.update(val5, i =>
i.push(`${key}.${key2}.${key3}.${key4}.${key5}`)
),
acc5,
val4
),
acc4,
val3
),
acc3,
val2
),
acc2,
val
),
init,
input
)
expect(result).toEqual(expected)
})
test('better', () => {
const result = reduceNested(
(acc, curr, a, b, c, d, e) =>
acc.update(curr, i => i.push(`${a}.${b}.${c}.${d}.${e}`)),
init,
input
)
expect(result).toEqual(expected)
})
})
I would like to write a function reduceNested
that achieves the same result but without all of the nested reduce functions. I don't see something in lodash/fp
or similar to address so my thought was to create a new function reduceNested
and to add variables to the callback for each key in the tree. I've tried implementing the actual logic but am unfortunately stuck for the time being. I know reduceNested
will need to use fn.length
to determine how far down into the source to drill, but other than that I'm just stuck.
const reduceNested = curry((fn, acc, iter) => {
// TODO --> use (fn.length - 2)
})
functional style
You were on the right track with your answer, however recurring based on the user-supplied procedure's length is a misstep. Instead, the variable-length path should be passed as a single, variable-length value – an array
const reduceTree = (proc, state, tree, path = []) =>
reduce // call reduce with:
( (acc, [ key, value ]) => // reducer
isObject (value) // value is an object (another tree):
? reduceTree // recur with:
( proc // the proc
, acc // the acc
, value // this value (the tree)
, append (path, key) // add this key to the path
) // value is NOT an object (non-tree):
: proc // call the proc with:
( acc // the acc
, value // this value (non-tree, plain value)
, append (path, key) // add this key to the path
)
, state // initial input state
, Object.entries (tree) // [ key, value ] pairs of input tree
)
Free values above are defined to use prefix notation, which is more familiar in functional style –
const isObject = x =>
Object (x) === x
const reduce = (proc, state, arr) =>
arr .reduce (proc, state)
const append = (xs, x) =>
xs .concat ([ x ])
Now we have a generic reduceTree
function –
const result =
reduceTree
( (acc, value, path) => // reducer
[ ...acc, { path, value } ]
, [] // initial state
, input // input tree
)
console.log (result)
// [ { path: [ 'a1', 'b1', 'c1', 'd1', 'e1' ], value: 'one' }
// , { path: [ 'a1', 'b1', 'c1', 'd1', 'e2' ], value: 'two' }
// , { path: [ 'a1', 'b1', 'c1', 'd1', 'e3' ], value: 'three' }
// , { path: [ 'a1', 'b1', 'c1', 'd2', 'e1' ], value: 'one' }
// , { path: [ 'a1', 'b1', 'c1', 'd2', 'e2' ], value: 'two' }
// , { path: [ 'a1', 'b1', 'c1', 'd2', 'e3' ], value: 'three' }
// , { path: [ 'a1', 'b1', 'c2', 'd1', 'e1' ], value: 'one' }
// , { path: [ 'a1', 'b1', 'c2', 'd1', 'e2' ], value: 'two' }
// , { path: [ 'a2', 'b1', 'c1', 'd1', 'e1' ], value: 'one' }
// , { path: [ 'a2', 'b1', 'c1', 'd2', 'e1' ], value: 'one' }
// , { path: [ 'a2', 'b2', 'c1', 'd1', 'e1' ], value: 'one' }
// , { path: [ 'a2', 'b2', 'c1', 'd2', 'e1' ], value: 'one' }
// ]
We can shape the output of the result however we like –
const result =
reduceTree
( (acc, value, path) => // reducer
({ ...acc, [ path .join ('.') ]: value })
, {} // initial state
, input // input tree
)
console.log (result)
// { 'a1.b1.c1.d1.e1': 'one'
// , 'a1.b1.c1.d1.e2': 'two'
// , 'a1.b1.c1.d1.e3': 'three'
// , 'a1.b1.c1.d2.e1': 'one'
// , 'a1.b1.c1.d2.e2': 'two'
// , 'a1.b1.c1.d2.e3': 'three'
// , 'a1.b1.c2.d1.e1': 'one'
// , 'a1.b1.c2.d1.e2': 'two'
// , 'a2.b1.c1.d1.e1': 'one'
// , 'a2.b1.c1.d2.e1': 'one'
// , 'a2.b2.c1.d1.e1': 'one'
// , 'a2.b2.c1.d2.e1': 'one'
// }
The input
for our test should demonstrate that reduceTree
works for various levels of nesting –
test ('better', () => {
const input =
{ a: { b: { c: 1, d: 2 } }, e: 3 }
const expected =
{ 'a.b.c': 1, 'a.b.d': 2, e: 3 }
const result =
reduceTree
( (acc, value, path) =>
({ ...acc, [ path .join ('.') ]: value })
, {}
, input
)
expect(result).toEqual(expected)
})
Lastly, verify the program works in your browser below –
const isObject = x =>
Object (x) === x
const reduce = (proc, state, arr) =>
arr .reduce (proc, state)
const append = (xs, x) =>
xs .concat ([ x ])
const reduceTree = (proc, state, tree, path = []) =>
reduce
( (acc, [ key, value ]) =>
isObject (value)
? reduceTree
( proc
, acc
, value
, append (path, key)
)
: proc
( acc
, value
, append (path, key)
)
, state
, Object.entries (tree)
)
const input =
{ a: { b: { c: 1, d: 2 } }, e: 3 }
const result =
reduceTree
( (acc, value, path) =>
[ ...acc, { path, value } ]
, []
, input
)
console.log (result)
// { 'a.b.c': 1, 'a.b.d': 2, e: 3 }
… with the help of some friends
Imperative-style generators make light work of this kind of task while offering an intuitive language to describe the intended process. Below we add traverse
which generates [ path, value ]
pairs for a nested tree
(object) –
const traverse = function* (tree = {}, path = [])
{ for (const [ key, value ] of Object.entries (tree))
if (isObject (value))
yield* traverse (value, append (path, key))
else
yield [ append (path, key), value ]
}
Using Array.from
we can plug the generator directly into our existing functional reduce
; reduceTree
is now just a specialization –
const reduceTree = (proc, state, tree) =>
reduce
( (acc, [ path, value ]) =>
proc (acc, value, path)
, state
, Array.from (traverse (tree))
)
The call site is the same –
const input =
{ a: { b: { c: 1, d: 2 } }, e: 3 }
const result =
reduceTree
( (acc, value, path) =>
({ ...acc, [ path .join ('.') ]: value })
, {}
, input
)
console.log (result)
// { 'a.b.c': 1, 'a.b.d': 2, e: 3 }
Verify the result in your browser below –
const isObject = x =>
Object (x) === x
const reduce = (proc, state, arr) =>
arr .reduce (proc, state)
const append = (xs, x) =>
xs .concat ([ x ])
const traverse = function* (tree = {}, path = [])
{ for (const [ key, value ] of Object.entries (tree))
if (isObject (value))
yield* traverse (value, append (path, key))
else
yield [ append (path, key), value ]
}
const reduceTree = (proc, state, tree) =>
reduce
( (acc, [ path, value ]) =>
proc (acc, value, path)
, state
, Array.from (traverse (tree))
)
const input =
{ a: { b: { c: 1, d: 2 } }, e: 3 }
const result =
reduceTree
( (acc, value, path) =>
({ ...acc, [ path .join ('.') ]: value })
, {}
, input
)
console.log (result)
// { 'a.b.c': 1, 'a.b.d': 2, e: 3 }
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With