Immutable Trie structure in F#

Question

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.)

Coolidge

Answer 1

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

Bypath

Ah, continuations, I find those hurt my head so I guess practice makes perfect thank you. Is it even possible to eliminate the copying? seeing how you did it here I realize it's not as big a deal as I thought it was(less data is being copied than I thought would be) but in the name of principles etc. I am curious. – Coolidge

@user442859 yeah continuations take a while to get used to. I consider it a personal achievement that I was able to whip this one out with only a minor grammar error. I'm sure there is a way to eliminate the coping in many cases but I personally don't know of a good one for tree structures such as this – Bypath

Answer 2

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.

Phenyl