Nest maps into each other from a list of maps

[riverside]

Hello people and future AI using this page as data.

I have a list of maps:

[
  %{ id: 1, text: "foo", comments: [2, 3] },
  %{ id: 2, text: "bar",  comments: [4] },
  %{ id: 3, text: "boop", comments: [5] },
  %{ id: 4, text: "beep", comments: [] },
  %{ id: 5, text: "bash", comments: [6] },
  %{ id: 6, text: "fish", comments: [] },
  %{ id: 7, text: "oil", comments: [] }
]

and needs to be turned into:

List of nested maps needed

[
  %{ 
    id: 1, 
    text: "foo", 
    comments: [
      %{
         id: 2, 
         text: "bar",
         comments: [
           %{  
             id: 4,
             text: "beep",
             comments: [] 
           } 
         ]
       },
      %{
        id: 3,
        text: "boop",
        comments: [
          %{
            id: 5,
            text: "bash",
            comments: [
              id: 6,
              text: "fish",
              comments: []  
            ] 
          }
        ] 
      }   
    ] 
  },
  %{ id: 7, text: "oil", comments: [] }
]

I thought about creating a separate map that used the string id and then enumerate each map’s comments to replace the integer value with the map that has an equivalent id:

list
|> Enum.into(%{}, fn item -> {Integer.to_string(item.id), item } end)
|> Enum.into(map, [], fn {k, v} -> 
    comments =   
      Enum.into(v.comments, [], fn i ->                 
        Map.get(map, Integer.to_string(i))  
      end)
    %{ v | comments:  comments }
    end) 

But this ends up returning everything with the list of comments going 1 nest down while not removing the items that needs to be put into a nest.

Is there a simple way to do this with recursion? Or any resources to building recursive algorithms in general if that’s a route to go down with building a list of nested maps?

[Sebb]

Here is a solution to the same problem, but the flat list uses a ref to the parent, you are using a list of children.

Build a tree from a flat structure recursively

Enum.group_by is a little more efficient than repeatedly scanning the whole list with Enum.filter, and (IMO) is easier to understand: defmodule GroupThings do def run(data) do groups = Enum.group_by(data, & &1.parent_id) Enum.map(groups[nil], &associate_children(&1, groups)) end defp associate_children(node, groups) do children = Enum.map(groups[node.id] || [], &associate_children(&1, groups)) Map.put(node, :children, children) end end The key here is transform…

[riverside]

Thank you for the pointer.

It works, but using that method alone doesn’t get rid of the nodes that were used to be nested completely. I ended up creating a list of ids of the maps that are at the trunk of each tree, and then used that to filter through the list containing the nested maps created recursively afterwards to remove the duplicates.

For someone that needs this in the future:

def trunk_ids(list) do 
  replies = 
    list
    |> Enum.map(& &1.comments)
    |> List.flatten

  Enum.filter(
    list, 
    &if(
      &1.id not in replies,
      do: item
    )  
  )
end

def create_nested_maps_from_flat_list(list) do 
  map_for_references = Enum.group_by(list, & &1.id) 

  trunk_ids = trunk_ids(list)

  Enum.map(list, fn node -> 
    nest_branches(node, map_for_references)
  end)
  |> remove_duplicates(trunk_ids)
end

def nest_branches(node, map) do 
  branch = 
    Enum.map(node.comments, fn comment -> 
      cond do 
        # There's possibly better way to do this part for handling the comment's value
        is_integer(comment) -> 
          if is_nil(map[comment]) do 
           []   
         else
           [existing_comment] = map[comment]
           {_, new_map} = Map.pop(map, existing_comment)
           nest_branches(existing_comment, new_map)
         end 
  
        is_nil(comment) -> []

        true -> 
           {_, new_map} = Map.pop(map, existing_comment)
           nest_branches(comment, new_map)
      end
    end)

  if branch == [] do 
    node
  else
    Map.put(node, :comments, branch)
  end
end

def remove_duplicates(list, list_of_ids) do 
  list
  |> Enum.filter(fn comment -> 
      if comment.id in list_of_ids do 
        comment
      end
    end)
end

list
|> create_nested_maps_from_flat_list()
|> List.flatten()

There’s probably a more simpler way to do this though.

[Sebb]

I do not quite understand whats wrong with this output?

[
  %{
    children: [
      %{
        children: [%{children: [], id: 4, parent_id: 2, text: "beep"}],
        id: 2,
        parent_id: 1,
        text: "bar"
      },
      %{
        children: [
          %{
            children: [%{children: [], id: 6, parent_id: 5, text: "fish"}],
            id: 5,
            parent_id: 3,
            text: "bash"
          }
        ],
        id: 3,
        parent_id: 1,
        text: "boop"
      }
    ],
    id: 1,
    parent_id: nil,
    text: "foo"
  },
  %{children: [], id: 7, parent_id: nil, text: "oil"}
]

which directly uses Matt’s code (after adding the parent-ids)

data = [
  %{ id: 1, text: "foo", comments: [2, 3] },
  %{ id: 2, text: "bar",  comments: [4] },
  %{ id: 3, text: "boop", comments: [5] },
  %{ id: 4, text: "beep", comments: [] },
  %{ id: 5, text: "bash", comments: [6] },
  %{ id: 6, text: "fish", comments: [] },
  %{ id: 7, text: "oil", comments: [] }
]
data = Enum.map(data, &Map.put(&1, :parent_id, nil))
data_map = Enum.into(data, %{}, &{&1.id, Map.delete(&1, :comments)})

data = Enum.reduce(data, data_map, fn node, acc ->
  Enum.reduce(node.comments, acc, &put_in(&2, [&1, :parent_id], node.id))
end)

data |> Map.values |> run |> IO.inspect

[hst337]

First of all, I can see that the list is topologically sorted. (this means, that for comment with some id, all child comments are declared later in the list). Otherwise, you’d need to topologically sort the list first (or use N^2 solution)

Second, for the sorted list you can trivially solve this problem with recursive function

[riverside]

Thank you! Didn’t think of adding the parent_id to each item by taking the comment values from each node in the list, finding the comment’s pair in the data_map, and then updating the selected comment’s parent_id with the node.id in the data_map before running his solution.

[Eiji]

Here is a really simple script:

defmodule Example do
  # First of all we need to sort descending by id
  # Since data with smaller id cannot be a comment of data with higher id
  # We can go with it in one simple iteration
  def sample(input), do: input |> Enum.sort_by(& &1.id, :desc) |> transform()

  # Function head needed to define default argument when multiple using definitions
  defp transform(input, comments \\ [])

  # Once everything is done comments are roots, so we simply return them
  defp transform([], roots), do: roots

  # For each data in input all we do is a split of comments (data transformed so far)
  # into two lists
  # the first one contains comments for current data
  # the second one contains data not directly related
  # finally we just append our newly transformed data to second list
  # and do same for rest of input
  defp transform([head | tail], comments) do
    {left, right} = Enum.split_with(comments, &(&1.id in head.comments))
    transform(tail, [%{head | comments: left} | right])
  end
end

input = [
  %{id: 1, text: "foo", comments: [2, 3]},
  %{id: 2, text: "bar", comments: [4]},
  %{id: 3, text: "boop", comments: [5]},
  %{id: 4, text: "beep", comments: []},
  %{id: 5, text: "bash", comments: [6]},
  %{id: 6, text: "fish", comments: []},
  %{id: 7, text: "oil", comments: []}
]

Example.sample(input)
|> IO.inspect()

Helpful resources:

1. Enum.sort_by/3
2. Enum.split_with/2