Folk Computer

A Trie is the data structure that underlies Folk's database. It is the index to all Wishes, Claims, and Whens. The Trie works by inserting and removing Clauses. A Clause is an array of space-seperated words, with each word being called a Term. An example Clause, “the sky is blue”, would become [“the”, “sky”, “is”, “blue”].

Let's insert the Clause into the Trie and see what happens:

As you can see, the Clause has been turned into a set of nodes in the Trie. Let's try inserting another Clause, “the sky has clouds”:

As seen, a Trie is just a tree, with each successive Term being one level deeper in the tree*.

We've now covered inserting, but what about querying? Let's try querying for “the sky has clouds”. We'll do this by comparing each Term of the query against the Trie:

Notice how we never had to check the Term “blue”, since that was on a separate branch of the Trie. When there's thousands of nodes, the Trie effectively trims irrelevent branches at each level.

* Technically, the definition of a trie uses a level for each letter, not for each word. It makes more sense to be for each word in Folk though.