@favonia I decided on the name complete at the very beginning, but now I am not so sure that it is the right name.

@kentookura I'm not 100% if tags should be used to remember the edit distances. Anyway, it seems we do not need to see the internal implementations of tries? Is it technically possible to separate it out as an individual module?

If we want to combine these altogether, apparently the current data structure is bad for calculation distances, and maybe it's better to redesign the whole thing (?)

Is it technically possible to separate it out as an individual module?

As far as I can tell this could be implemented by a consumer of Yuujinchou, so yes.

It's interesting that string based tries are used to implement autocomplete, but this fact is not used here. Maybe a guiding principle for redesign can be to share code between path-based and string-based tries? Maybe an API that converts a namespace into a datastructure that can be used to power an autocomplete engine?

I pushed a branch of forester that implements this functionality using the existing API, so the changes I made aren't strictly necessary.

@kentookura I will check the code after I finish my current work on asai...

@favonia
I think there is an argument for a more sophisticated feature. The current
state of the PR suffices to implement the "Did you mean..." feature, it is
probably not very efficient nor elegant. A cursory google search reveals that
it is actually possible to use string-based tries to implement Levenshtein.

As far as I understand the trie implementation of yuujinchou, it does
distinguish paths like ["foo"; "bar"] and ["fo"; "obar"]. I wonder how
much code can be shared between a trie that is indexed by paths, and a trie
that is indexed simply by strings. Eager for your input on this part.

Suppose that problem is solved. Here is a rough sketch of the API I envision:

type path_trie = Path_trie.t
type string_trie = String_trie.t

val make_completion : ?cutoff -> ?fuzzy -> ?filter -> Path_trie -> string_trie

val suggest : string -> string_trie -> Completion_item.t list

where the arguments of make_completion allow to configure the completion
behavior of the returned trie.

It would also be neat if it were possible to feed individual characters or
deletion into the string_trie and it were able to efficiently respond, but I
don't know how that API should look. The use case is to filter results on
keystroke for an LSP server.