How to construct a tree in immutable data structure?

1 
@genType
type rawActivity = {
  id: string,
  parentId: option<string>,
  iid: int,
  name: string,
  nickname: string,
  planStartDate: option<string>,
  planFinishDate: option<string>,
  realStartDate: option<string>,
  realFinishDate: option<string>,
}

@genType
type rec activity = {
  id: string,
  parent: option<activity>,
  children: array<activity>,
  iid: int,
  name: string,
  nickname: string,
  planDatenRange: option<(Js.Date.t, Js.Date.t)>,
  realDateRange: option<(option<Js.Date.t>, option<Js.Date.t>)>,
}

the rawActivity → activity is simple in javascript. But I don’t know how to implementation in rescript

2

Maybe show what you’d like to do (even in js) and where’s the difficulty.

3

in javascript i can do it in multi step initialization:

let dict = Object.fromEntries(rawActivities.map(raw => [raw.id, transformActivityWithoutParentAndChildren(raw)]))

Object.values(dict).forEach(activity => {
    let parent = dict[activity.parentId]
    activity.parent = parent
    if (parent) {
       parent.children.push(activity)
   }
})
4

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?

[I miss you, “traverse”]

1 Like
5

Have you tried using Js.Dict | ReScript API to do the equivalent of this in ReScript?

1 Like
6

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.

3 Likes