Recursively scanning a list of nested maps

egeersoz

I’m looking for some help in implementing a “deep search” or “deep find” function.

I have a list of maps that represent people and their dependents. Each dependent can also have dependents, who in turn can have their own dependents, etc. ad infinitum. Example below:

[
%{"Name" => "Bobby Drake", "Age" => 50},
%{"Name" => "Jack Nicholson", "Age" => 25},
%{"Name" => "Peter Nelson", "Age" => 70, "Dependents" => [
    %{"Name" => "Amber Nauta", "Age" => 30},
    %{"Name" => "Joseph Nauta", "Age" => 26}
  ]
},
%{"Name" => "Craig Brown", "Age" => 66, "Dependents" => [
    %{"Name" => "Trevor Brown", "Age" => 33, "Dependents" => [
       %{"Name" => "Allison Brown", "Age" => 10}
     ]
  ]
}

]

Given a name, I need to scan this entire list and find that person’s age. There can theoretically be hundreds of items, and dozens of levels of nesting. However, we can assume that names are unique — meaning, there will only be a single match, and once that match is found, the search function can stop, return the result and exit. I mention that because performance is important.

5 comments

#learning-elixir

0 953 5

2021-02-22 07:39:15 UTC

Showing Posts 1 to 5

Show Best Posts
Show All (oldest first)
Show All (newest first)

kip

ex_cldr Core Team

Here’s one solution that leans on Enum.reduce_while/2 since it allows early exit from a reduction.

defmodule Name do
  @list_of_maps [
    %{"Name" => "Bobby Drake", "Age" => 50},
    %{"Name" => "Jack Nicholson", "Age" => 25},
    %{
      "Name" => "Peter Nelson",
      "Age" => 70,
      "Dependents" => [
        %{"Name" => "Amber Nauta", "Age" => 30},
        %{"Name" => "Joseph Nauta", "Age" => 26}
      ]
    },
    %{
      "Name" => "Craig Brown",
      "Age" => 66,
      "Dependents" => [
        %{
          "Name" => "Trevor Brown",
          "Age" => 33,
          "Dependents" => [
            %{"Name" => "Allison Brown", "Age" => 10}
          ]
        }
      ]
    }
  ]

  def deep_find(list_of_maps \\ @list_of_maps, name) do
    Enum.reduce_while(list_of_maps, {:halt, nil}, fn
      %{"Name" => ^name}, _acc -> {:halt, name}
      %{"Dependents" => dependents}, _acc ->
        case deep_find(dependents, name) do
          ^name -> {:halt, name}
          nil -> {:cont, nil}
        end
      _other, _acc -> {:cont, nil}
    end)
  end
end

iex> Name.deep_find "Allison Brown" 
"Allison Brown"
iex> Name.deep_find "Peter Nelson" 
"Peter Nelson"
iex> Name.deep_find "Pirate Pete" 
nil

Happy to answer questions any time.

Post #1

Aetherus

Just a depth-first search:

defmodule DFS do
  def search([%{"Name" => name} = found | _], name) do
    found
  end

  def search([head | tail], name) do
    search(head["Dependents"], name) || search(tail, name)
  end

  def search(_nil_or_empty_list, _name) do
    nil
  end
end

Not tail-recursion, but as you said there are only dozens of levels of nesting, this should work fine.

Post #2

egeersoz

Thanks, this is interesting! I don’t want to get the name though. I want to get the map itself so I can access its other properties, such as age.

Post #3

kip

ex_cldr Core Team

No problem there, just a small change to either solution. For mine:

  def deep_find(list_of_maps \\ @list_of_maps, name) do
    Enum.reduce_while(list_of_maps, {:halt, nil}, fn
      %{"Name" => ^name} = found, _acc -> {:halt, found}
      %{"Dependents" => dependents}, _acc ->
        case deep_find(dependents, name) do
          %{"Name" => ^name} = found -> {:halt, found}
          nil -> {:cont, nil}
        end
      _other, _acc -> {:cont, nil}
    end)
  end

iex> Name.deep_find "Allison Brown"
%{"Age" => 10, "Name" => "Allison Brown"}
iex> Name.deep_find "Peter Nelson" 
%{
  "Age" => 70,
  "Dependents" => [
    %{"Age" => 30, "Name" => "Amber Nauta"},
    %{"Age" => 26, "Name" => "Joseph Nauta"}
  ],
  "Name" => "Peter Nelson"
}
iex> Name.deep_find "Pirate Pete"  
nil

Post #4

mudasobwa

Creator of Cure

While I would definitely go with Enum.reduce_while/3 suggested by @kip, I am to post two other approaches, sort of a top-up.

comprehension

level =
  fn input, f ->
    List.first(for(%{"Name" => "Allison Brown"} = map <- input, do: map)) ||
      for(%{"Dependents" => dependents} <- input, do: f.(dependents, f))
  end
level.(input, level) |> List.flatten() |> List.first()

`Access`

level = 
  fn input, f ->
    (input |> get_in([Access.filter(& &1["Name"] == "Allison Brown")]) |> List.first()) ||
      f.(get_in(input, [Access.all(), "Dependents"]) |> Enum.reject(&is_nil/1) |> List.flatten(), f)
  end
level.(input, level)

Post #5

— All posts loaded —