Updating the element of a struct and the struct object along with it

So, in Elixir, I haven’t really found a way to update the value of an element of a struct and then replace the struct object as well while keeping the updated value intact. For an easier explanation of what I am saying, basically, this is what I mean:

# Update the children list of node object
if (node.children[c - 'a'] == null) {
   node.children[c - 'a'] = new TrieNode();
 }
# Update the node
node = node.children[c - 'a'];

While I was trying to solve this Leetcode problem, I came across this java solution where the user had done the following:

public class WordDictionary {
   # Creating the TrieNode class
    public class TrieNode {
        public TrieNode[] children = new TrieNode[26];
        public String item = "";
    }
    
    private TrieNode root = new TrieNode();

    public void addWord(String word) {
        TrieNode node = root;
        # Loops over the word
        for (char c : word.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                # Updates the children array
                node.children[c - 'a'] = new TrieNode();
            }
            # Updates the node itself
            node = node.children[c - 'a'];
        }
        # Updates the item section of the node
        node.item = word;
    }
}

The user loops over the word, convert it into Unicode and then checks if the children element is null or not at that index. If it is, they simply add a TrieNode object into it. Afterward, they updates the node and then the loop starts again.

I tried following this solution and basically doing something similar in Elixir, however, I realized we can’t really update the children list and the node itself in Elixir.

Following is my solution:

defmodule TrieNode do
    defstruct children: List.duplicate(nil, 26), item: ""
    def init, do: %TrieNode{}
end

defmodule WordDictionary do
  defstruct root: TrieNode.init
  def init, do: %WordDictionary{}

  # Passing the Trie object into add_word 
  def addWord(trie_object, word) do
    node = trie_object.root
    node = 
      word |> String.graphemes |> Enum.reduce(node, fn(word, node) ->
        # Found the index of the current string
        {index, _} = :binary.match("abcdefghijklmnopqrstuvwxyz", word)
        node = 
          cond do
            # Updated the children element of node
            Enum.at(node.children, index) == nil -> 
              list = List.insert_at(node.children, index, TrieNode.init)
              %TrieNode{node | children: list}
            true -> node
          end

        # Updating the node
        Enum.at(node.children, index)
      end)

    # Setting the item and root
    node = %TrieNode{node | item: word}
    %WordDictionary{trie_object | root: node}
  end
end

I made my addWord function a bit different to the Leetcode one and am passing the struct to it. This is what my main function looks like:

dict = WordDictionary.init
dict = dict |> WordDictionary.addWord("help")
dict = dict |> WordDictionary.addWord("hello")
dict |> WordDictionary.addWord("sail")

My question is that can we update both the node and children element of it in Elixir? In the case of my solution, it isn’t working properly. Is there an alternative to this?

Any help will be appreciated!

I think you can use recursion in place of the for loop and pass the node as one of the arguments to the next iteration.

defmodule WordDictionary do
  # you can also try using :gb_trees instead of maps
  # https://www.erlang.org/doc/man/gb_trees.html
  @spec init :: map
  def init, do: %{}

  @spec add_word(map, String.t()) :: map
  def add_word(dict, word) do
    update_children(String.downcase(word), dict)
  end

  defp update_children(<<char::utf8, rest::bytes>>, node) when char in ?a..?z do
    node = node || %{}
    Map.put(node, char, update_children(rest, node[char]))
  end

  defp update_children(<<_char::utf8, rest::bytes>>, node) do
    update_children(rest, node)
  end

  defp update_children(<<>>, node), do: node
end

defmodule WordDictionaryTest do
  use ExUnit.Case

  test "dict" do
    dict = WordDictionary.init()

    dict = WordDictionary.add_word(dict, "hello")

    assert dict == %{
             ?h => %{
               ?e => %{
                 ?l => %{
                   ?l => %{
                     ?o => nil
                   }
                 }
               }
             }
           }

    dict = WordDictionary.add_word(dict, "Hel-lo")

    assert dict == %{
             ?h => %{
               ?e => %{
                 ?l => %{
                   ?l => %{
                     ?o => nil
                   }
                 }
               }
             }
           }

    dict = WordDictionary.add_word(dict, "Hellllo")

    assert dict == %{
             ?h => %{
               ?e => %{
                 ?l => %{
                   ?l => %{
                     ?o => nil,
                     ?l => %{
                       ?l => %{
                         ?o => nil
                       }
                     }
                   }
                 }
               }
             }
           }
  end
end
2 Likes

Thank you! This seems really helpful :+1:

The idiomatic way in Elixir is: provided c is an integer and node.children is a map.

node = Map.get(node.children, c - ?a, TrieNode.new())

For faster lookups you should use maps, not lists, this is a structure you can use, (also note the convention is to name the init function new

defmodule TrieNode do
  children = for letter <- ?a..?z, into: %{} do
    {<<letter::utf8>>, nil}
  end
  
  defstruct children: children,
    item: ""

  def new, do: %__MODULE__{}
end
2 Likes