So I have an assignment for school, that needs me (among other stuff) to create a trie, in order to use it to store some numbers and the times each path is being used. For example, if I insert "1234" and then "1255", nodes of 1 and 2 should have a value=2 while nodes of 3 and 4 should have a value=1.
Problem is, I don't know how to implement such a trie in Prolog (i'm quite a begginer). I found this code here:
:- use_module(library(lists)).
new_trie(root-[]).
%%% Add a string to the trie.
% We have reached a word ending, so this must be a terminal node.
extend_trie([], TrieIn, TrieOut) :-
ensure_terminal(TrieIn, TrieOut).
% If we have a node for C here, we need to extend it with Cs.
extend_trie([C | Cs], Char-Children, Char-[NewChild | OtherChildren]) :-
select(C-CChildren, Children, OtherChildren),
!,
extend_trie(Cs, C-CChildren, NewChild).
% There is no C node, so we need to construct a new one.
extend_trie([C | Cs], Char-Children, Char-[NewChild | Children]) :-
extend_trie(Cs, C-[], NewChild).
% A terminal node is one with the 'terminal' child.
ensure_terminal(Char-Children, Char-Children) :-
member(terminal, Children),
!.
ensure_terminal(Char-Children, Char-[terminal | Children]).
%%% ----------------------------------------------------------------------
%%% Decide whether or not a word occupies the trie.
%%% ----------------------------------------------------------------------
% If we've got to the end of our string, it is a word if there is a terminal child.
lookup_trie([], _Char-Children) :-
member(terminal, Children).
% If we have more characters in our string, lookup the C trie and continue.
lookup_trie([C | Cs], _Char-Children) :-
member(C-GrandChildren, Children),
lookup_trie(Cs, C-GrandChildren).
But I don't know how to use this. I mean I don't know how to create a trie with this, or insert/lookup values.
Any help or advice?