嵌套 Reduce 函数/递归/函数式编程/树遍历 [英] Nested Reduce Functions / Recursion / Functional Programming / Tree Traversal
问题描述
我经常遇到这样的情况,我最终嵌套了很多 reduce
函数来深入到一个对象中.很难拉出逻辑,因为在底部我需要访问沿途遍历的各种键.本质上,我正在寻找一种更好的方法来实现以下目标:
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)
})
})
我想编写一个函数 reduceNested
来实现相同的结果,但没有所有嵌套的 reduce 函数.我在 lodash/fp
或类似地址中没有看到任何东西,所以我的想法是创建一个新函数 reduceNested
并为回调中的每个键添加变量树.我试过实现实际的逻辑,但不幸的是暂时卡住了.我知道 reduceNested
将需要使用 fn.length
来确定要深入到源的深度,但除此之外,我只是被卡住了.
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)
})
推荐答案
功能风格
您的答案是正确的,但是根据用户提供的过程的长度重复出现是一个失误.相反,变长路径应该作为单个变长值传递——一个数组
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 ])
现在我们有了一个通用的reduceTree
函数——
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'
// }
我们测试的 input
应该证明 reduceTree
适用于各种级别的嵌套 –
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 }
…在一些朋友的帮助下
命令式生成器可以轻松完成此类任务,同时提供一种直观的语言来描述预期的过程.下面我们添加 traverse
,它为嵌套的 tree
(对象)生成 [ path, value ]
对 –
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 ]
}
使用Array.from
,我们可以将生成器直接插入我们现有的功能reduce
;reduceTree
现在只是一个特化 –
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))
)
调用地点是一样的——
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 }
这篇关于嵌套 Reduce 函数/递归/函数式编程/树遍历的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!