Prefix tree(trie) implementation in F#

Update: all the code can be downloaded from here

This is my implementation of a a prefix tree data structure in F#.
This structure is described in more detail in a previous post of mine.
I just describe the F# related stuff in the comments.
I'm sure this is not the best implementation. I am aware this is not the most functional implementation ever.
I am open to all constructive criticism of course.

	open System.Collections.Generic;
	//the trie node type which is stores a char, a bool to mark the end of the node and a list of all it's subnodes
	type TrieNode = TrieNode of (char * bool * TrieNode list) with
	//just a getter the char stored
	member this.Char = match this with TrieNode(c,weh,subnodes) -> c
	//get the first node that is a subnode of the current node and stores the char passed as parameter (c)
	//this returns a list which can be either empty or have one element this is probably not the best option since there will never be
	//more than one element in the list but I am new to F#
	member this.GetChild(c:char) = match this with TrieNode(c,weh,subnodes) -> match List.tryFind (fun (this:TrieNode) -> this.Char = c) subnodes with
	| Some value -> [value]
	| None -> []
	//just return true if a word ends here
	member this.AWordEndsHere = match this with TrieNode(_,weh,_) -> weh
	//just a getter for the the subnodes
	member this.Subnodes = match this with TrieNode(_,_,subnodes) -> subnodes
	//type members cannot be recursive so I implemented this in a module
	//a more functional approach was to implement all methods here I guess ... anyways ...
	module TrieFunctions =
	//this inserts a word passed as a char list
	let rec insertWord (wordChars:char list) = function
	| TrieNode(c, weh, subnodes) as node ->
	if(wordChars.Length > 0) then
	//get the first char in the word and see if there are any child nodes storing that char
	let child = node.GetChild(wordChars.Head)
	if child = [] then
	//if there aren't insert this node and make a new node to pass to the insertion function
	let newnode = TrieNode(wordChars.Head,false,[])
	TrieNode(c,weh,(insertWord wordChars.Tail newnode)::subnodes )
	else
	//otherwise the node that has to be passed to the insertion function is the child node as all other nodes will be
	//added after it and the first char in the word will be added
	TrieNode(wordChars.Head,false,(insertWord wordChars.Tail child.Head)::subnodes )
	else
	//there are no more characters in the word so we must add a node with no subnodes and mark it as a valid end of a word
	TrieNode(c,true,[])
	//turn a string into a char list - ofSeq turns any sequence into a list of it's composing elements
	//and a string is made up of chars
	let stringToCharList(s:string) = List.ofSeq s
	//print the trie - use an accumulator(acc)
	let rec print acc = function
	//if there are no subnodes
	| TrieNode(c, weh, []) ->
	//add the current char node to the accumulator, print if it the end of a word and return unit
	let str = acc + c.ToString()
	if weh then printfn "%s" str
	()
	| TrieNode(c, weh, subnodes) ->
	//add the current char node to the accumulator, print if it the end of a word
	let str = acc + (if c.Equals(' ') then "" else c.ToString())
	if weh then printfn "%s" str
	//iterate through the list of subnodes and call print function for each of them
	List.iter (fun (node : TrieNode) -> print str node) subnodes
	//unlike in C# in F# the type has a default constructor containing the maximum number of parameters
	type Trie(inner : TrieNode) =
	member this.InsertWord(wordChars:char list) = Trie(TrieFunctions.insertWord wordChars inner)
	member this.InsertWord(str:string) = Trie(TrieFunctions.insertWord (TrieFunctions.stringToCharList str) inner)
	member this.Root() = inner
	//and an empty constructor must be declared if you want to have it
	new() = Trie(TrieNode(' ',false,List.empty))
	let trie = Trie()
	.InsertWord("abc")
	.InsertWord("abcd")
	.InsertWord("abcd")
	.InsertWord("abcde")
	.InsertWord("abcdef")
	.InsertWord("ab123cd")
	.InsertWord("abc123d")
	.InsertWord("abc132d")
	TrieFunctions.print "" (trie.Root())

view raw PrefixTreeF# hosted with ❤ by GitHub