I am playing around with the aho-corasick algorithm to try and get a little better with F#, and I ran across a problem with the Trie implementations, they are all mutable or can't be tail call optimized.
The basic issue from what I can see is that immutable data structures have to be built "bottom up" since you can't change what they point to, so your options are either make them mutable, or find out the nodes as you go along(i.e. recurse in construction).
Is there any way of making an immutable trie data structure with tail call optimizations on the construction?(and not lose efficiency by copying.)
The tail call optimiation can be eliminated by using a continuation. Here's a sample where the key and value are string
and int
respectively
type Trie =
| Data of string * int * Trie * Trie
| Leaf
let Insert start key value =
let rec inner current withNode =
match current with
| Data (currentKey, currentValue, left, right) ->
if key < currentKey then
inner left (fun left -> Data (currentKey, currentValue, left, right))
else
inner right (fun right -> Data (currentKey, currentValue, left, right))
| Leaf -> withNode (Data (key, value, Leaf, Leaf))
inner start (fun x -> x)
Eliminating the copies is a bit more difficult if you want to stick with immutable structures
I came across this post while researching for my code review post where I've implemented at immutable trie.
It is performant using maps for links rather than binary trees.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With