Excuse me for arguing a different line but is the index dereference of parentId really a significant cost?
The nested reference is also still indirect in javascript so bound to be about the same?
You can write this same JavaScript function in ReScript. Here’s a minimal example:
type rec activity = {
id: string,
parentId: string,
mutable parent: option<activity>,
children: array<activity>,
}
let transformActivityWithoutParentAndChildren = x => x // No-op for the example
let make = rawActivities => {
let dict = Js.Dict.fromArray(
Js.Array2.map(rawActivities, raw => (
raw.id,
transformActivityWithoutParentAndChildren(raw),
)),
)
Js.Dict.values(dict)->Js.Array2.forEach(activity => {
let parent = Js.Dict.get(dict, activity.parentId)
activity.parent = parent
switch parent {
| Some(parent) => Js.Array2.push(parent.children, activity)->ignore
| None => ()
}
})
dict
}
While immutable tree structures are common in ReScript, I don’t think that this particular graph is practical in an immutable style. This graph contains cycles (the parent and child nodes reference each other). Constructing recursive graphs with immutable types is generally not feasible. Using mutable types in an imperative style is far simpler.
If you need immutable types, then you’ll probably need to rethink the design. For example, if the parents only linked to the children (and children did not link to the parents) then that would be more feasible. Alternatively, you can keep the values mutable but use an interface to control how the graph can be updated.