Newbie F # trie implementation went wrong

Question

I am trying to implement a trie data structure in F #. I have a problem's. I cannot debug the word insert function. None of my breakpoints inside this function reached something, but I don't see any error. I also have serious doubts if I have implemented this correctly. Anyway, here is the code:

type TrieNode = | SubNodes of char * bool * TrieNode list | Nil member this.Char = match this with | Nil -> ' ' | SubNodes(c,weh,subnodes) -> c member this.GetChild(c:char) = match this with | Nil -> [] | SubNodes(c,weh,subnodes) ->[ (List.filter(fun (this:TrieNode) -> this.Char = c) subnodes).Head ] member this.AWordEndsHere = match this with | Nil -> false | SubNodes(c,weh,subnodes) -> weh module TrieFunctions = let rec insertWord (wordChars:char list) = function | Nil -> SubNodes(wordChars.Head, false, []) | SubNodes(c, weh, subnodes) as node -> let child = node.GetChild(wordChars.Head) if child = [] then SubNodes(wordChars.Head,false,[insertWord wordChars.Tail node]) else SubNodes(wordChars.Head,false,[insertWord wordChars.Tail child.Head]) type Trie(inner : TrieNode) = member this.InsertWord(wordChars:char list) = TrieFunctions.insertWord(wordChars) let trie = Trie(SubNodes(' ',false,List.empty)).InsertWord(['g';'i';'g';'i']) 

So my questions are:
1. How can I get debug access to the insertWord function? Why am I not getting it now? Why can't I see the error?
2. How to make the insert word function return a list of TrieNode objects so that I don’t have to wrap the call around square brackets ("[", "]"). I think this is a mistake.
3. Any other advice you can give me about implementing this data structure in F # is welcome. I know that I have to do a lot of things because I am very new to this language. I know, for example, that the word insertion function is erroneous because it does not check if the list is empty or not, so it ends prematurely. I wanted to cross this bridge when I got to it.

Thank you in advance

Thank you in advance

Answer 1

• You probably cannot call your breakpoint because you are not fully using insertWords : it takes two currency parameters, but you only pass one wordChars argument. Perhaps you wanted to define your Trie type like this?

   type Trie(inner : TrieNode) = member this.InsertWord(wordChars:char list) = TrieFunctions.insertWord wordChars inner 

• Well, you can wrap all of your return values ​​in [] to make them single lists, and then not transfer the recursive calls to insertWords . However, it seems likely that something is wrong with your algorithm (anyway) because you only ever get lists of single elements ...

  Please note that at the moment you are completely discarding the existing subnodes list - if you want to add it to the beginning, use (insertWord wordChards.Tail node)::subnodes . However, sometimes you need to replace an existing record, rather than adding a new one, which will require a lot of effort.

• There are a few questions. Here are a few to get you started:

  • Try to avoid using Head , especially because you do not always know that your lists are not empty when you call it.
  • When you insert a word into an empty Trie , you drop everything except the first character! Similarly, you also need to rethink your recursive calls.
  • More importantly, your TrieNode type has a slight problem. Can you write down the result that you expect to see, which contains only two words "in" and "to" ?

Answer 2

As for your first question, as @kvb said, you are partially using insertWord . By defining it, you specify an explicit wordChars argument and using the function construct to match patterns, you basically add a second parameter of type TrieNode , so your function ends with the following signature:

 insertWord : char list -> TrieNode -> TrieNode 

Since in your call to insertWord (which is only a wrapper for insertWord ), you provide only one argument (a char list), the function will not be called, but you will get a function that TrieNode a TrieNode back. The insertWord signature makes this clear:

 InsertWord : wordChars:char list -> (TrieNode -> TrieNode) 

Pay attention to the brackets.

You probably want to provide Nil in your case, since conceptually you are extending an empty trie:

 let trie = Trie(SubNodes(' ',false,List.empty)).InsertWord(['g';'i';'g';'i']) Nil 

Here you will find an example implementation of a trie structure: http://lepensemoi.free.fr/index.php/2009/10/15/trie-and-anagrams-with-f