Map operation on recursive hierarchical structure (Composite pattern)

I’m new to Elixir and functional programming, and I’m wondering if anyone has an example of how to perform a mapping operation on a hierarchical structure. The map represents a menu item, and each item may have multiple children of menu items, recursively.

This is tricky with your regular old OO code, but thinking of how to approach it with Elixir is making my brain melt.

The goal is to evaluate one attribute and use it to modify another. In this case, there’s sometimes an asterisk in the label, and if it is present, we strip it out of the label and set another field as a flag.

For example, this:

%{
    "label" => "My Title*",
    "has_footnote" => false
    "children" => [...]
}

Becomes this:

%{
    "label => My Title",
    "has_footnote" => true
    "children" => [...]
}

But recursively. Have I met my match? Is there some elegant way to do this, or is it something that only a ninja can pull off?

Thanks for any tips!

Are you looking for something like this?

iex(7)> posts                                                                                  
[
  %{"has_footnote" => false, "label" => "My Title Without Asterisk"},
  %{"has_footnote" => false, "label" => "My Title*"}
]
iex(8)> for %{"label" => title} = p <- posts do                                                
...(8)>   if String.ends_with?(title, "*") do                                         
...(8)>     %{p | "label" => String.trim_trailing(title, "*"), "has_footnote" => true}
...(8)>   else
...(8)>     p                                                                         
...(8)>   end
...(8)> end
[
  %{"has_footnote" => false, "label" => "My Title Without Asterisk"},
  %{"has_footnote" => true, "label" => "My Title"}
] 

Note that you don’t have to match the “label” key or even the fact that it’s a map. I just did it so that I could use title without writing p.title, but the risk here is that if you have a badly formed collection of posts and some of them don’t have the "label" key, this actually acts as a filter, which is likely not what you want.

The correct thing, of course, is to not be able to create a post struct like this without having these keys. You can do this using defstruct and the @enforce_keys module attribute (or using Vex, Ecto, etc. to have validation and required fields some other way):

defmodule MyApp.Post do
  @fields [:label, :has_footnote]
  defstruct @fields
  @enforce_keys @fields
end

Edit: Of course @kokolegorille has it: You need to simply call the transformation on the list of children you have as well, and as long as they have the needed keys you’ll be fine.

2 Likes

Maybe You want something more recursive, to process children as well?

defmodule Koko do
  def transform(%{"label" => label, "children" => children} = item) do
    if String.ends_with?(label, "*") do
      %{item | 
        "has_footnote" => true, 
        "label" => String.trim_trailing(label, "*"),
        "children" => Enum.map(children, &transform(&1))
      }
    else
      %{item | 
        "children" => Enum.map(children, &transform(&1))
      }
    end
  end
end

iex> koko = %{
  "label" => "My Title*",
  "has_footnote" => false,
  "children" => [
    %{
      "label" => "My Child with *",
      "has_footnote" => false,
      "children" => [
        %{
          "label" => "My SubChild with *",
          "has_footnote" => false,
          "children" => []
        },
        %{
          "label" => "My SubChild without",
          "has_footnote" => false,
          "children" => []
        }
      ]
    },
    %{
      "label" => "My Child without",
      "has_footnote" => false,
      "children" => []
    }
  ]
}

iex> Koko.transform koko
%{
  "children" => [ 
    %{
      "children" => [
        %{
          "children" => [],
          "has_footnote" => true,
          "label" => "My SubChild with "
        },
        %{
          "children" => [],
          "has_footnote" => false,
          "label" => "My SubChild without"
        }
      ],
      "has_footnote" => true,
      "label" => "My Child with "
    },
    %{"children" => [], "has_footnote" => false, "label" => "My Child without"}
  ],
  "has_footnote" => true,
  "label" => "My Title"
}
1 Like

I find it more structured to separate the walking of the map (a “deep map”) from the transformation process. For example, I have a function called deep_map/2 that will recursively walk a map and invoke a function on each key-value pair. Its quite simple and documented at https://github.com/kipcole9/cldr/blob/master/lib/cldr/helpers/map.ex#L6-L44 I suspect many members of this forum have a similar function in their back pocket.

Using this approach you would do the following:

deep_map(your_map, fn 
  {"label", value} when is_binary(value) ->
    {key, String.trim_trailing(value, "*")}
  {key, value} -> 
    {key, value}
end)

(edited a bit to be clearer, not necessary exactly the required use case)

5 Likes

Here is a modification of @kokolegorille’s example, from an editor with some more structure:

defmodule Sandbox.Post do
  # `label` is the only key that needs explicit setting
  @keys [:label, has_footnote: false, children: []]
  @enforce_keys [:label]
  defstruct @keys

  @type t :: %__MODULE__{label: String.t(), has_footnote: boolean(), children: [t()]}

  @spec set_footnote(post :: t()) :: t()
  def set_footnote(%__MODULE__{label: title, children: children} = post) do
    if String.ends_with?(title, "*") do
      %{
        post
        | label: String.trim_trailing(title, "*"),
          has_footnote: true,
          children: Enum.map(children, &set_footnote/1)
      }
    else
      %{post | children: Enum.map(children, &set_footnote/1)}
    end
  end

  @spec new(label :: String.t(), children :: [t()]) :: t()
  def new(label, children \\ []) do
    if String.ends_with?(label, "*") do
      label_without_asterisk = String.trim_trailing(label, "*")

      %__MODULE__{
        label: label_without_asterisk,
        has_footnote: true,
        children: Enum.map(children, &set_footnote/1)
      }
    else
      %__MODULE__{label: label, children: children}
    end
  end
end

defmodule Sandbox.PostsRecursive do
  alias Sandbox.Post

  @posts [
    %Post{
      label: "Post with footnote*",
      children: [%Post{label: "Nested post with footnote*"}, %Post{label: "No footnote here"}]
    },
    %Post{label: "Top-level note without footnote", children: [%Post{label: "Footnote here*"}]}
  ]

  def example(), do: Enum.map(@posts, &Post.set_footnote/1)
end

I suggest studying @kip’s function in order to understand what is happening, as you’ll likely not have any issues with recursion as a concept if you fully understand it.

Edit: I’ve added an alternative approach using a new function that could move the application of this logic to the creation of posts instead, provided you create them by calling that function.

This, coupled with some discipline, is useful when you want to guarantee things about datatypes and is the preferred way in languages where the norm is to not expose raw data constructors and instead have limited interfaces generally only exposing constructor/modification/accessor functions.

2 Likes