Call for criticism: a minimal Trie library

On a first glance, it’s really nice. My only nitpick is that your t type should probably be __MODULE__ and probably opaque, to reflect your comment about not counting on internals, and correspondingly move it out of @moduledoc and into code comments.

A property test would also make me more confident though it is a well known data structure that it’s easy to verify you’ve done correctly.

I don’t have time to look at the code right now but I was wondering if you could give an example or two of when you would want to use this library instead of the built-in data structures.

I don’t really like that public and private functions are intermixed. I personally prefer to have all the public functions and the documentation at the top of the module with the implementation being separate. In fact I like making separate modules for documentation and implementation using delegates, but that might be my personal kind of madness

Update: I ran dialyzer and made a pr that seems to fix the error.

One tip I have is to move some of the shorter testing functions to doctests, which will help to improve the documentation. Besides this kind of data structure being very testable with property-based testing, as @ityonemo already mentioned, I think that some more code examples in the documentation would be helpful.

As for the code: There are some places where I would prefer a function call written on one line rather than split over many lines, but I believe the Elixir formatter has some heuristics that do not agree with my opinion here.
One of the things I have a question about is why in (almost?) every place you pattern-match on the struct, you also pattern-match on that children is a map (%__MODULE__{children: %{} = children} ). I think it would be better to make your type opague and just leave those matches out. In many cases you can also just use trie.children rather than pattern-matching on the struct’s fields in the function head at all; that is only really useful if you have different clauses you want to do depending on the contents of children.

I think integrating it with Access is not too much, and probably a good idea, because it means that it is easier to integrate it with existing programs that use the Access protocol.

Imagine loading all tags in your DB in the Trie:

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

And then when people want to put tag(s) on an object you have an autocomplete controller action that does this:

Trie.search(params["tag"])

…and then put the results in a response (in my case JSON).

That was my original idea and that’s what I am using my own library for.

PR accepted. Thanks!

Agreed, I’ll add a bit more real-world examples similar to what I pasted to you above.

I understand. I have seen at least 4 schools of thought on that topic and I personally optimise for reading the code top-to-bottom: as you are scrolling and inspecting the code, you stumble upon a public function with almost no body that calls a private function; you then proceed to find it just a few coding lines below it.

Your remark is valid and in my case I haven’t done it your way because I don’t feel the code is very big as to warrant such a separation.

@ityonemo / @Qqwy I see no reason not to make property tests indeed. Save for the fact that it usually takes me a few hours.

Good idea. Noted in the GitHub issues.

At certain point I gave up and just wrote code however I wanted and then run mix format. Even if I don’t like some of its choices – like you – I prefer to have the coding style standardised. Bonus points for having standard git diffs as well.

Agreed. This was one of my first Elixir projects and looking at the code now I definitely went overboard with pattern-matching paranoia. Also noted in the GitHub issues.

Agreed.

Going to fix that even if I don’t feel it’s a major problem. Noted in GitHub issues.

That’s what I thought back then and needed the sanity check. Thank you.