• Each value in Rust has exactly one owner — when the owner goes out of scope, the value is dropped
• Assignment moves ownership by default; the original binding becomes invalid
• Borrowing (&T / &mut T) lets you reference data without taking ownership
• The compiler enforces: many shared references OR one mutable reference, never both
• No garbage collector needed — memory is freed deterministically at scope exit
use std::collections::HashMap;
#[derive(Debug, Default, Clone)]
pub struct Trie {
is_word: bool,
children: HashMap<char, Trie>,
}
impl Trie {
pub fn insert(&mut self, word: &str) {
let mut node = self;
for c in word.chars() {
// entry().or_default() creates a new empty Trie node if missing
node = node.children.entry(c).or_default();
}
node.is_word = true; // mark the final node as a complete word
}
pub fn contains(&self, word: &str) -> bool {
let mut node = self;
for c in word.chars() {
match node.children.get(&c) {
Some(child) => node = child,
None => return false, // prefix not found
}
}
node.is_word // true only if this is a complete word, not just a prefix
}
pub fn starts_with(&self, prefix: &str) -> bool {
let mut node = self;
for c in prefix.chars() {
match node.children.get(&c) {
Some(child) => node = child,
None => return false,
}
}
true // reached the end of prefix — exists in the trie
}
}| Concept | OCaml | Rust |
|---|---|---|
| Children map | `Map.Make(Char)` functor → immutable sorted map | `HashMap<char, Trie>` (fast) or `BTreeMap` (sorted) |
| Mutability | Immutable — insert returns a new trie | Mutable — `insert(&mut self, ...)` modifies in place |
| Create-or-insert | Recursive rebuild on each path | `entry().or_default()` — in-place |
| Memory layout | Heap-allocated tree nodes | Same — each `Trie` owns its children |
| ASCII optimization | N/A | `[Option<Box<Trie>>; 26]` array — avoids map overhead |
//! # Trie — Prefix Tree for Strings
//!
//! A trie stores strings with shared prefixes efficiently.
//! OCaml's `Map.Make(Char)` for children maps to Rust's `HashMap<char, Trie>`.
use std::collections::HashMap;
use std::collections::BTreeMap;
// ---------------------------------------------------------------------------
// Approach A: HashMap-based trie (idiomatic Rust)
// ---------------------------------------------------------------------------
#[derive(Debug, Default, Clone)]
pub struct Trie {
is_word: bool,
children: HashMap<char, Trie>,
}
impl Trie {
pub fn new() -> Self {
Self::default()
}
pub fn insert(&mut self, word: &str) {
let mut node = self;
for c in word.chars() {
node = node.children.entry(c).or_default();
}
node.is_word = true;
}
pub fn contains(&self, word: &str) -> bool {
let mut node = self;
for c in word.chars() {
match node.children.get(&c) {
Some(child) => node = child,
None => return false,
}
}
node.is_word
}
pub fn starts_with(&self, prefix: &str) -> bool {
let mut node = self;
for c in prefix.chars() {
match node.children.get(&c) {
Some(child) => node = child,
None => return false,
}
}
true
}
}
// ---------------------------------------------------------------------------
// Approach B: Immutable trie (mirrors OCaml's functional style)
// ---------------------------------------------------------------------------
#[derive(Debug, Clone)]
pub struct FunctionalTrie {
is_word: bool,
children: BTreeMap<char, FunctionalTrie>,
}
impl FunctionalTrie {
pub fn empty() -> Self {
FunctionalTrie { is_word: false, children: BTreeMap::new() }
}
pub fn insert(&self, word: &str) -> Self {
self.insert_chars(&word.chars().collect::<Vec<_>>(), 0)
}
fn insert_chars(&self, chars: &[char], i: usize) -> Self {
if i == chars.len() {
FunctionalTrie { is_word: true, children: self.children.clone() }
} else {
let c = chars[i];
let child = self.children.get(&c)
.cloned()
.unwrap_or_else(FunctionalTrie::empty);
let new_child = child.insert_chars(chars, i + 1);
let mut new_children = self.children.clone();
new_children.insert(c, new_child);
FunctionalTrie { is_word: self.is_word, children: new_children }
}
}
pub fn contains(&self, word: &str) -> bool {
let chars: Vec<char> = word.chars().collect();
self.contains_chars(&chars, 0)
}
fn contains_chars(&self, chars: &[char], i: usize) -> bool {
if i == chars.len() {
self.is_word
} else {
match self.children.get(&chars[i]) {
Some(child) => child.contains_chars(chars, i + 1),
None => false,
}
}
}
}
// ---------------------------------------------------------------------------
// Approach C: Array-based trie (performance-oriented, ASCII only)
// ---------------------------------------------------------------------------
pub struct ArrayTrie {
is_word: bool,
children: [Option<Box<ArrayTrie>>; 26],
}
impl ArrayTrie {
pub fn new() -> Self {
ArrayTrie {
is_word: false,
children: Default::default(),
}
}
pub fn insert(&mut self, word: &str) {
let mut node = self;
for c in word.chars() {
let idx = (c as u8 - b'a') as usize;
node = node.children[idx].get_or_insert_with(|| Box::new(ArrayTrie::new()));
}
node.is_word = true;
}
pub fn contains(&self, word: &str) -> bool {
let mut node = self;
for c in word.chars() {
let idx = (c as u8 - b'a') as usize;
match &node.children[idx] {
Some(child) => node = child,
None => return false,
}
}
node.is_word
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_insert_and_contains() {
let mut t = Trie::new();
for w in &["cat", "car", "card", "care", "dare"] {
t.insert(w);
}
assert!(t.contains("cat"));
assert!(!t.contains("ca"));
assert!(t.contains("card"));
assert!(t.contains("dare"));
assert!(!t.contains("dog"));
}
#[test]
fn test_starts_with() {
let mut t = Trie::new();
t.insert("hello");
assert!(t.starts_with("hel"));
assert!(!t.starts_with("world"));
}
#[test]
fn test_functional_trie() {
let t = FunctionalTrie::empty();
let t = t.insert("cat").insert("car").insert("card");
assert!(t.contains("cat"));
assert!(t.contains("car"));
assert!(!t.contains("ca"));
}
#[test]
fn test_array_trie() {
let mut t = ArrayTrie::new();
t.insert("cat");
t.insert("car");
assert!(t.contains("cat"));
assert!(t.contains("car"));
assert!(!t.contains("ca"));
}
#[test]
fn test_empty_string() {
let mut t = Trie::new();
t.insert("");
assert!(t.contains(""));
}
}
fn main() {
println!("{:?}", t.contains("cat"));
println!("{:?}", !t.contains("ca"));
println!("{:?}", t.contains("card"));
}
module CMap = Map.Make(Char)
type trie = { is_word: bool; children: trie CMap.t }
let empty = { is_word = false; children = CMap.empty }
let insert word trie =
let rec go i node =
if i = String.length word then { node with is_word = true }
else
let c = word.[i] in
let child = try CMap.find c node.children with Not_found -> empty in
{ node with children = CMap.add c (go (i+1) child) node.children }
in go 0 trie
let mem word trie =
let rec go i node =
if i = String.length word then node.is_word
else match CMap.find_opt word.[i] node.children with
| None -> false | Some child -> go (i+1) child
in go 0 trie
let () =
let t = List.fold_left (fun t w -> insert w t)
empty ["cat";"car";"card";"care";"dare"] in
List.iter (fun w ->
Printf.printf "%s: %b\n" w (mem w t)
) ["cat";"ca";"card";"dare";"dog"]
OCaml's trie is naturally functional: `Map.Make(Char)` gives an immutable sorted map for children, and every insert returns a new trie (sharing unchanged subtrees via structural sharing). Rust's idiomatic trie is mutable — `HashMap<char, Trie>` with `entry().or_default()` for elegant insertion. The functional Rust version requires explicit `.clone()` where OCaml shares structure implicitly.
🐪 Show OCaml equivalent
module CMap = Map.Make(Char)
type trie = { is_word: bool; children: trie CMap.t }
let rec insert_go word i node =
if i = String.length word then { node with is_word = true }
else
let c = word.[i] in
let child = try CMap.find c node.children with Not_found -> empty in
{ node with children = CMap.add c (insert_go word (i+1) child) node.children }
pub fn insert(&mut self, word: &str) {
let mut node = self;
for c in word.chars() {
node = node.children.entry(c).or_default();
}
node.is_word = true;
}pub fn insert(&self, word: &str) -> Self {
// Clone children, recursively insert — mirrors OCaml but explicit cloning
}| Aspect | OCaml | Rust (mutable) | Rust (functional) |
|---|---|---|---|
| Children map | `Map.Make(Char)` (tree) | `HashMap<char, Trie>` | `BTreeMap<char, Trie>` |
| Insert style | Returns new trie | Mutates in place | Returns new trie (clone) |
| Structural sharing | Automatic (GC) | N/A | Manual clone |
| Missing child | `Not_found` exception | `entry().or_default()` | `.unwrap_or_else(empty)` |
| Lookup | `CMap.find_opt` | `.get(&c)` | `.get(&c)` |
| Performance | O(k log 26) per op | O(k) amortized | O(k * clone_cost) |