821 Intermediate

Trie Autocomplete

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Trie Autocomplete" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Autocomplete and prefix search are fundamental to user interfaces: search bars, IDE completion, spell checkers, and IP routing tables all need to answer "what words start with this prefix?" efficiently. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Autocomplete and prefix search are fundamental to user interfaces: search bars, IDE completion, spell checkers, and IP routing tables all need to answer "what words start with this prefix?" efficiently. A hash map of all words answers exact lookups in O(1) but cannot answer prefix queries. A trie (prefix tree) organizes strings by shared prefixes, enabling prefix queries in O(m) time where m is the prefix length — independent of how many words are stored. This also makes insertion, deletion, and "does any word start with X?" all O(m). Tries power the autocomplete in Google Search, the routing table lookup in routers, and the dictionary in word games.

🎯 Learning Outcomes

• Build a trie where each node maps characters to children and marks word endings

• Implement insert in O(m) by traversing/creating nodes character by character

• Implement prefix search by traversing to the prefix endpoint then collecting all completions via DFS

• Understand memory tradeoffs: tries use more memory than hash maps but enable prefix operations

• Recognize compressed tries (patricia/radix tries) as space optimization for sparse tries

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Trie in OCaml — functional-style with records and Map *)

module CharMap = Map.Make(Char)

type trie = {
  is_end  : bool;
  children: trie CharMap.t;
}

let empty_trie = { is_end = false; children = CharMap.empty }

(* Insert a word into the trie — pure functional (returns new trie) *)
let rec insert (word : string) (pos : int) (t : trie) : trie =
  if pos = String.length word then
    { t with is_end = true }
  else
    let c = word.[pos] in
    let child =
      match CharMap.find_opt c t.children with
      | None -> empty_trie
      | Some ct -> ct
    in
    let child' = insert word (pos + 1) child in
    { t with children = CharMap.add c child' t.children }

let insert_word word t = insert word 0 t

(* Find the node for a given prefix, if it exists *)
let rec find_prefix (prefix : string) (pos : int) (t : trie) : trie option =
  if pos = String.length prefix then Some t
  else
    let c = prefix.[pos] in
    match CharMap.find_opt c t.children with
    | None -> None
    | Some child -> find_prefix prefix (pos + 1) child

(* Collect all words in a subtrie, prepending the given prefix *)
let rec collect_words (prefix : string) (t : trie) : string list =
  let from_children =
    CharMap.fold
      (fun c child acc ->
        (collect_words (prefix ^ String.make 1 c) child) @ acc)
      t.children []
  in
  if t.is_end then prefix :: from_children
  else from_children

(* Autocomplete: return all words with the given prefix *)
let autocomplete (prefix : string) (t : trie) : string list =
  match find_prefix prefix 0 t with
  | None -> []
  | Some subtrie -> List.sort String.compare (collect_words prefix subtrie)

let () =
  let words = ["apple"; "app"; "application"; "apply"; "apt"; "bat"; "ball"; "band"] in
  let trie = List.fold_right insert_word words empty_trie in

  let test prefix =
    let results = autocomplete prefix trie in
    Printf.printf "autocomplete(%S): [%s]\n" prefix (String.concat ", " results)
  in

  test "app";
  test "ba";
  test "apt";
  test "xyz";
  test ""

Key Differences

Aspect	Rust	OCaml
Node storage	`HashMap<char, TrieNode>`	`Hashtbl` or `Map.Make(Char).t`
Insertion	Mutable traversal with `entry()`	Mutable `Hashtbl` or immutable path copy
Completions DFS	Recursive with `&mut Vec<String>`	Accumulator list or `Buffer`
Memory	Each node heap-allocated	GC-managed, similar cost
Sorted output	Extra sort step	`Map` gives sorted iteration free
End marker	`bool` field	`bool` field or `unit option`

OCaml Approach

OCaml represents trie nodes as { children: (char * node) list; is_end: bool } or with a Hashtbl. Functional insertion creates a new node path, relying on structural sharing for efficiency. With mutable Hashtbl, insertion mutates like Rust's approach. OCaml's Map.Make(Char) creates a balanced BST per node for sorted child iteration — convenient for alphabetical autocomplete results. The DFS for completions uses continuation-passing or an accumulator list. OCaml's algebraic types make is_end a natural bool field.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Trie in OCaml — functional-style with records and Map *)

module CharMap = Map.Make(Char)

type trie = {
  is_end  : bool;
  children: trie CharMap.t;
}

let empty_trie = { is_end = false; children = CharMap.empty }

(* Insert a word into the trie — pure functional (returns new trie) *)
let rec insert (word : string) (pos : int) (t : trie) : trie =
  if pos = String.length word then
    { t with is_end = true }
  else
    let c = word.[pos] in
    let child =
      match CharMap.find_opt c t.children with
      | None -> empty_trie
      | Some ct -> ct
    in
    let child' = insert word (pos + 1) child in
    { t with children = CharMap.add c child' t.children }

let insert_word word t = insert word 0 t

(* Find the node for a given prefix, if it exists *)
let rec find_prefix (prefix : string) (pos : int) (t : trie) : trie option =
  if pos = String.length prefix then Some t
  else
    let c = prefix.[pos] in
    match CharMap.find_opt c t.children with
    | None -> None
    | Some child -> find_prefix prefix (pos + 1) child

(* Collect all words in a subtrie, prepending the given prefix *)
let rec collect_words (prefix : string) (t : trie) : string list =
  let from_children =
    CharMap.fold
      (fun c child acc ->
        (collect_words (prefix ^ String.make 1 c) child) @ acc)
      t.children []
  in
  if t.is_end then prefix :: from_children
  else from_children

(* Autocomplete: return all words with the given prefix *)
let autocomplete (prefix : string) (t : trie) : string list =
  match find_prefix prefix 0 t with
  | None -> []
  | Some subtrie -> List.sort String.compare (collect_words prefix subtrie)

let () =
  let words = ["apple"; "app"; "application"; "apply"; "apt"; "bat"; "ball"; "band"] in
  let trie = List.fold_right insert_word words empty_trie in

  let test prefix =
    let results = autocomplete prefix trie in
    Printf.printf "autocomplete(%S): [%s]\n" prefix (String.concat ", " results)
  in

  test "app";
  test "ba";
  test "apt";
  test "xyz";
  test ""

Deep Comparison

OCaml vs Rust: Trie Autocomplete

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement delete(word) that removes a word while preserving words that share its prefix.

Add a frequency count per word and implement autocomplete returning the top-k most frequent completions.

Implement fuzzy search: return all words within Levenshtein distance 1 from a query.

Build a compressed radix trie (patricia trie) that merges single-child chains into single edges.

Measure memory usage of trie vs. sorted Vec<String> + binary search for a dictionary of 100k words.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust