The immutable structure of Trie in F #

Question

I play with aho-corasick algorithm to try a little better with F #, and I ran into a problem with Trie implementations, they are all mutable or cannot be optimized with tail.

The main problem from what I see is that immutable data structures must be built from the bottom up, because you cannot change what they point to, so your parameters either make them mutable or they discover nodes like you go (for example, recursion in construction).

Is there a way to make an immutable trie data structure with tail call optimization in the design? (and not lose efficiency by copying.)

Answer 1

Tail call optimization can be eliminated using continuation. Here is a sample, where is the key and value, stringand intaccordingly

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)

Deleting copies is a bit more complicated if you want to stick with immutable structures

Answer 2

I came across this post while researching my comment for code review , where I implemented in an immutable trie.

This is done using maps for links, not binary trees.