Recursively scanning a list of nested maps

Questions / Help
1

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.

2

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.

3

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.

1 Like
4

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. :grinning:

5

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
1 Like
6

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)
1 Like