@Scott has paid you a tremendous favour to explain the issues with your proposed data shape and program. He is correct that recursion is not a particular great fit for this problem. His answer did spark an idea though and I will share it below.
Here we have collapse which allows you to collapse an object of arbitrary shape using a variable-length sequence of named keys -
- if
name is empty, the base case has been reached. Combine intermediate result, r, and input, t
- (inductive)
name is not empty. Collapse input t and recur with smaller sub-problem
const collapse = ([ name, ...more ], t = {}, r = {}) =>
name === undefined
? [ { ...r, ...t } ] // 1
: Object // 2
.entries(t)
.flatMap
( ([ k, v ]) =>
collapse(more, v, { ...r, [name]: k }) // <- recursion
)
const result =
collapse(["month", "day", "event", "_"], shows)
console.log(JSON.stringify(result, null, 2))
[ { "month": "1", "day": "29", "event": "0", "_": "0", "id": "0001", "title": "title a" }
, { "month": "1", "day": "29", "event": "1", "_": "1", "id": "0002", "title": "title b" }
, { "month": "1", "day": "30", "event": "0", "_": "0", "id": "0003", "title": "title c" }
, { "month": "1", "day": "30", "event": "1", "_": "1", "id": "0004", "title": "title a" }
, { "month": "6", "day": "29", "event": "0", "_": "0", "id": "0005", "title": "title d" }
, { "month": "6", "day": "29", "event": "1", "_": "1", "id": "0006", "title": "title b" }
, { "month": "6", "day": "30", "event": "0", "_": "0", "id": "0007", "title": "title a" }
, { "month": "6", "day": "30", "event": "1", "_": "1", "id": "0008", "title": "title c" }
]
Writing getSimilarShows is easier now thanks to collapse -
const getSimilarShows = (shows = [], query = "") =>
collapse(["month", "day", "event", "_"], shows) // <-
.filter(v => v.title === query)
const result =
getSimilarShows(shows, "title b")
console.log(JSON.stringify(result, null, 2))
[ { "month": "1", "day": "29", "event": "1", "_": "1", "id": "0002", "title": "title b" }
, { "month": "6", "day": "29", "event": "1", "_": "1", "id": "0006", "title": "title b" }
]
caution
NB collapse is somewhat reckless and does not protect you from trying to collapse an object more than is possible. For example, if you provide four (4) named keys but the object is only nested two (2) levels deep, an empty result, [], will be returned. This is likely unexpected and it would be better to throw a runtime error in this case.
One obvious improvement would be the ability to "skip" a level using a known name, such as "_" above -
const collapse = ([ name, ...more ], t = {}, r = {}) =>
name === undefined
? [ { ...r, ...t } ]
: Object
.entries(t)
.flatMap
( ([ k, v ]) =>
name === "_" // <- skip this level?
? collapse(more, v, r) // <- new behaviour
: collapse(more, v, { ...r, [name]: k }) // <- original
)
const result =
collapse(["month", "day", "event", "_"], shows)
console.log(JSON.stringify(result, null, 2))
With this update "_" keys do not appear in the output below -
[ { "month": "1", "day": "29", "event": "0", "id": "0001", "title": "title a" }
, { "month": "1", "day": "29", "event": "1", "id": "0002", "title": "title b" }
, { "month": "1", "day": "30", "event": "0", "id": "0003", "title": "title c" }
, { "month": "1", "day": "30", "event": "1", "id": "0004", "title": "title a" }
, { "month": "6", "day": "29", "event": "0", "id": "0005", "title": "title d" }
, { "month": "6", "day": "29", "event": "1", "id": "0006", "title": "title b" }
, { "month": "6", "day": "30", "event": "0", "id": "0007", "title": "title a" }
, { "month": "6", "day": "30", "event": "1", "id": "0008", "title": "title c" }
]
@Scott offers an excellent suggestion to use a native Symbol instead or a string-based key. Eyes on collapse.skip below -
const collapse = (...) =>
name === undefined
? //...
: Object
.entries(t)
.flatMap
( ([ k, v ]) =>
name === collapse.skip // <- known symbol
? //...
: //...
)
collapse.skip = // <- define symbol
Symbol("skip")
Now instead of giving special behaviour to "_", we use collapse.skip. To keep examples consistent, we only skip one level of nesting, but we could effectively skip any number of levels we wish -
const result =
collapse(["month", "day", "event", collapse.skip], shows) // <-
console.log(JSON.stringify(result, null, 2))
// ...
alternative implementation
I've been spending some time thinking about collapse a little bit and I wonder how modifying the call site can increase its utility -
function collapse (t = {}, ...f)
{ function loop (t, c, r)
{ if (c >= f.length)
return [ { ...r, ...t } ]
else
return Object
.entries(t)
.flatMap(([ k, v ]) => loop(v, c + 1, { ...r, ...f[c](k) }))
}
return loop(t, 0, {})
}
const shows =
{1:{29:[{0:{id:'0001',title:'title a'}},{1:{id:'0002',title:'title b'}}],30:[{0:{id:'0003',title:'title c'}},{1:{id:'0004',title:'title a'}}]},6:{29:[{0:{id:'0005',title:'title d'}},{1:{id:'0006',title:'title b'}}],30:[{0:{id:'0007',title:'title a'}},{1:{id:'0008',title:'title c'}}]}}
const result =
collapse
( shows
, v => ({ month: v })
, v => ({ day: v })
, v => ({ event: v })
, v => ({}) // <- "skip"
)
console.log(JSON.stringify(result, null, 2))
list-like array destructuring
Thinking about array indexes is painful though, I agree with @Scott's comment below. But destructuring with rest arguments can create a lot of intermediate values. Here's one technique, likeList, I've been toying around with that seems to have good ergonomics and memory footprint -
const likeList = (t = [], c = 0) =>
({ [Symbol.iterator]: function* () { yield t[c]; yield likeList(t, c + 1) } })
function collapse (t = {}, ...f)
{ function loop (t, [f, fs], r) // <- destructure without rest
{ if (f === undefined) // <- base case: no f
return [ { ...r, ...t } ]
else
return Object
.entries(t)
.flatMap(([ k, v ]) => loop(v, fs, { ...r, ...f(k) })) // <- f
}
return loop(t, likeList(f), {}) // <- likeList
}
Or possibly -
const likeList = (t = [], c = 0) =>
({ [Symbol.iterator]: _ => [ t[c], likeList(t, c + 1) ].values() })
hold onto performance
I'm a big advocate for functional style because it unlocks our ability to think about problems in a fundamentally different way. JavaScript is very friendly to functional programmers, but it comes with caveats. Use of certain features in particular ways can slow our programs down, sometimes causing us to think functional style itself is to blame.
It's my own personal hobby to explore new ways to express functional style programs that don't take big performance hits. Above likeList offers a solution. Below we will put it to the test as we compare four (4) programs that copy an array. Each program is identical except for the way it iterates through the input array.
Here is copy by destructuring with rest argument. An elegant form enabled by JavaScript's native destructuring syntax. However it is costly, as we will see later -
const copyDestructure = (arr) =>
loop
( ( [ x, ...xs ] = arr // <- rest argument
, r = []
) =>
x === undefined
? r
: recur(xs, push(r, x))
)
Here is copy using a numeric index. This trades destructuring syntax for a cheap index. But now the programmer is burdened thinking about array boundaries, intermediate state, and off-by-one errors -
const copyIndex = (arr) =>
loop
( ( i = 0 // <- index
, r = []
) =>
i >= arr.length // <- off-by-one?
? r
: recur(i + 1, push(r, arr[i])) // <- increment i
)
Here is copy using likeList. This uses destructuring syntax but without an expensive rest argument. We removed all of the negative concerns of using an index, but can we maintain a good performance? -
const copyLikeList = (arr) =>
loop
( ( [ x, xs ] = likeList(arr) // <- likeList
, r = []
) =>
x === undefined
? r
: recur(xs, push(r, x)) // <- plainly use x and xs
)
And copy by listList, using the alternative implementation -
const copyLikeList2 = (arr) =>
loop
( ( [ x, xs ] = likeList2(arr) // <- implementation 2
, r = []
) =>
x === undefined
? r
: recur(xs, push(r, x)) // <- same
)
Run time in milliseconds, lower is better -
Array size 100 1,000 10,000 100,000
-----------------------------------------------------
copyDestructure 3.30 19.23 482.3 97,233.5
copyIndex 0.47 5.92 20.9 165.1 <-
copyLikeList 1.18 9.31 55.6 479.2
copyLikeList2 0.79 7.90 33.6 172.4 <-
Memory used in KB, lower is better -
Array size 1,000 100,000
-----------------------------------------------------
copyDestructure 613.43 38,790.34
copyIndex 247.60 4,133.72 <-
copyLikeList 960.44 26,885.91
copyLikeList2 233.63 2,941.98 <-
Implementation -
// Arr.js
const likeList = (t = [], c = 0) =>
({ [Symbol.iterator]: function* () { yield t[c]; yield likeList(t, c + 1) } })
const likeList2 = (t = [], c = 0) =>
({ [Symbol.iterator]: _ => [ t[c], likeList2(t, c + 1) ].values() })
const push = (t = [], x) =>
( t.push(x)
, t
)
const range = (start = 0, end = 0) =>
Array.from(Array(end - start), (_, n) => n + start)
export { likeList, likeList2, push, range }
// TailRec.js
function loop (f, ...init)
{ let r = f(...init)
while (r && r.recur === recur)
r = f(...r)
return r
}
const recur = (...v) =>
({ recur, [Symbol.iterator]: _ => v.values() })
export { loop, recur }
remarks
copyLikeList2 above using the second implementation of likeList is really onto something. The performance characteristics are comparable to using an index, even on large inputs. copyDestructure is substantially slower even on arrays as small as 1,000 elements.
