dimitarvp / trie

A basic Elixir implementation of the Trie data structure

Hello. 👋

🧔 Programmer with a keen eye for detail, loves making the code readable and maintainable. Pragmatic and never cutting corners. Automating myself out of the job is my ultimate goal.

💼 Focused on backend programming with Elixir, Rust and Golang, know shell scripting and databases. Interested in Linux system administration and network administration and I do well there.

📖 Previous experience: C, C++, some x86 Assembly, Java, PHP, Javascript, Ruby (plus Ruby on Rails).

👷 I am open to many formats of work but have come to appreciate stability and loyalty more than anything else. I am a good and patient coach, and have made money through that, and code reviewing too.

🔖 Keen interest in game bots, financial trading, formal verification of code and super-optimization (compiler tech).

📫 Drop me a line if you want to talk, I am friendly and curious and don't refuse interesting discussions, be it about programming or anything else.

Other profiles:

• HackerNews: https://news.ycombinator.com/user?id=pdimitar
• LinkedIn: https://www.linkedin.com/in/dpanayotov/

trie's Issues

Move smaller tests to doctests

Some of the tests are really minimal. It would improve the code and docs readability if those tests are moved to doctests instead of residing in the test script.

Include better examples in the Trie module docs

Something along the way of a more real-world usage like:

Fill the Trie:

Tag
|> Repo.all(select: [:name])
|> Trie.put_words()

Use the Trie for auto-completion:

Trie.search(params["query"])
|> # ...respond with search results here

Make the own struct pattern-matching less paranoid

Replace this:

%__MODULE__{children: %{} = children}

with this:

%__MODULE__{}

Replace `children` pattern-matching in function heads with direct access

Namely change code like this:

  defp get_or_create_node(%__MODULE__{children: %{} = children}, key) do
    children
    |> # ...

to this:

  defp get_or_create_node(%__MODULE__{} = t, key) do
    t.children
    |> # ...

Make your own guards

Don't use some of the builtin Elixir guards. Make your own. Those come to mind for now:

defguard is_key(x) when is_integer(x)
defguard is_char(x) when is_integer(x)
defguard is_pop_fn(x) when is_function(x, 1)

Can't avoid using is_list and is_binary because the library is supposed to allow both charlist and String inputs and thus having separate function pattern-matching heads working with them separately is completely normal.

Why elixir base trie when we have ets ?? ( trie DS )

Hi. Ets internally implement judy array. Actually
Judy array is family of trie/radix-tree and etc.

When we have ets ( c based, without garbage )
Why is need to elixir based trie ?!

Just I want more know for myself

Make the struct type opaque

Since the internals of the struct aren't to be relied upon by users, this should have been the case in the first place.

Add property tests