960 Fundamental

960 Key Value Store

Functional Programming

Tutorial

The Problem

Implement a mutable key-value store backed by HashMap<String, String> with get/set/delete/contains/keys operations. The impl Into<String> pattern for set allows callers to pass &str or String without explicit conversion. Return sorted keys for deterministic output. Also implement an immutable functional variant using association lists.

🎯 Learning Outcomes

• Build a KvStore struct wrapping HashMap<String, String> with CRUD methods

• Use impl Into<String> for ergonomic insertion: accepts both &str and String at call sites

• Implement get returning Option<&str> (borrowed from the map's stored value)

• Implement sorted keys() by collecting, sorting, and returning Vec<&str>

• Contrast with an immutable association-list approach: Vec<(String, String)> updated via functional operations

Code Example

#![allow(clippy::all)]
// 960: Key-Value Store
// OCaml: Hashtbl (mutable) or association list (functional)
// Rust: HashMap<String, String> (mutable) or BTreeMap for sorted iteration

use std::collections::HashMap;

// Approach 1: HashMap-based mutable store
pub struct KvStore {
    data: HashMap<String, String>,
}

impl KvStore {
    pub fn new() -> Self {
        KvStore {
            data: HashMap::new(),
        }
    }

    pub fn set(&mut self, key: impl Into<String>, value: impl Into<String>) {
        self.data.insert(key.into(), value.into());
    }

    pub fn get(&self, key: &str) -> Option<&str> {
        self.data.get(key).map(|s| s.as_str())
    }

    pub fn delete(&mut self, key: &str) -> bool {
        self.data.remove(key).is_some()
    }

    pub fn contains(&self, key: &str) -> bool {
        self.data.contains_key(key)
    }

    pub fn keys(&self) -> Vec<&str> {
        let mut keys: Vec<&str> = self.data.keys().map(|s| s.as_str()).collect();
        keys.sort();
        keys
    }

    pub fn values(&self) -> Vec<&str> {
        self.data.values().map(|s| s.as_str()).collect()
    }

    pub fn size(&self) -> usize {
        self.data.len()
    }

    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }
}

impl Default for KvStore {
    fn default() -> Self {
        Self::new()
    }
}

// Approach 2: Functional (immutable) KV using Vec of pairs
#[derive(Clone, Debug)]
pub struct FunctionalStore<V: Clone> {
    data: Vec<(String, V)>,
}

impl<V: Clone> FunctionalStore<V> {
    pub fn new() -> Self {
        FunctionalStore { data: vec![] }
    }

    pub fn set(&self, key: impl Into<String>, value: V) -> Self {
        let key = key.into();
        let mut data: Vec<(String, V)> = self
            .data
            .iter()
            .filter(|(k, _)| k != &key)
            .cloned()
            .collect();
        data.insert(0, (key, value));
        FunctionalStore { data }
    }

    pub fn get(&self, key: &str) -> Option<&V> {
        self.data.iter().find(|(k, _)| k == key).map(|(_, v)| v)
    }

    pub fn delete(&self, key: &str) -> Self {
        let data = self
            .data
            .iter()
            .filter(|(k, _)| k != key)
            .cloned()
            .collect();
        FunctionalStore { data }
    }

    pub fn keys(&self) -> Vec<&str> {
        self.data.iter().map(|(k, _)| k.as_str()).collect()
    }
}

impl<V: Clone> Default for FunctionalStore<V> {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_mutable_store() {
        let mut s = KvStore::new();
        assert_eq!(s.size(), 0);
        assert!(s.is_empty());

        s.set("name", "Alice");
        s.set("age", "30");
        s.set("city", "Amsterdam");

        assert_eq!(s.get("name"), Some("Alice"));
        assert_eq!(s.get("age"), Some("30"));
        assert_eq!(s.get("missing"), None);
        assert!(s.contains("city"));
        assert!(!s.contains("missing"));
        assert_eq!(s.size(), 3);
    }

    #[test]
    fn test_update() {
        let mut s = KvStore::new();
        s.set("name", "Alice");
        s.set("name", "Bob");
        assert_eq!(s.get("name"), Some("Bob"));
        assert_eq!(s.size(), 1);
    }

    #[test]
    fn test_delete() {
        let mut s = KvStore::new();
        s.set("name", "Alice");
        s.set("age", "30");
        let removed = s.delete("age");
        assert!(removed);
        assert_eq!(s.get("age"), None);
        assert_eq!(s.size(), 1);
        assert!(!s.delete("missing"));
    }

    #[test]
    fn test_keys_sorted() {
        let mut s = KvStore::new();
        s.set("city", "Amsterdam");
        s.set("name", "Alice");
        assert_eq!(s.keys(), vec!["city", "name"]);
    }

    #[test]
    fn test_functional_store() {
        let fs: FunctionalStore<i32> = FunctionalStore::new();
        let fs = fs.set("x", 1);
        let fs = fs.set("y", 2);
        let fs = fs.set("x", 10); // update
        assert_eq!(fs.get("x"), Some(&10));
        assert_eq!(fs.get("y"), Some(&2));
        assert_eq!(fs.get("z"), None);

        let fs2 = fs.delete("y");
        assert_eq!(fs2.get("y"), None);
        assert_eq!(fs.get("y"), Some(&2)); // original unchanged
    }
}

(* 960: Key-Value Store *)
(* Simple in-memory KV store using Hashtbl *)

(* Approach 1: Hashtbl-based store with functional interface *)

type 'a store = (string, 'a) Hashtbl.t

let create () : 'a store = Hashtbl.create 16

let set store key value =
  Hashtbl.replace store key value

let get store key =
  Hashtbl.find_opt store key

let delete store key =
  Hashtbl.remove store key

let keys store =
  Hashtbl.fold (fun k _ acc -> k :: acc) store []

let values store =
  Hashtbl.fold (fun _ v acc -> v :: acc) store []

let size store = Hashtbl.length store

let contains store key = Hashtbl.mem store key

(* Approach 2: Functional (immutable) KV using association list *)

type 'a fstore = (string * 'a) list

let fset (store : 'a fstore) key value : 'a fstore =
  (key, value) :: List.filter (fun (k, _) -> k <> key) store

let fget (store : 'a fstore) key =
  List.assoc_opt key store

let fdelete (store : 'a fstore) key : 'a fstore =
  List.filter (fun (k, _) -> k <> key) store

let fkeys (store : 'a fstore) =
  List.map fst store

let () =
  (* Mutable store *)
  let s = create () in
  assert (size s = 0);

  set s "name" "Alice";
  set s "age" "30";
  set s "city" "Amsterdam";

  assert (get s "name" = Some "Alice");
  assert (get s "age" = Some "30");
  assert (get s "missing" = None);
  assert (contains s "city");
  assert (not (contains s "missing"));
  assert (size s = 3);

  (* Update existing key *)
  set s "name" "Bob";
  assert (get s "name" = Some "Bob");
  assert (size s = 3);

  (* Delete *)
  delete s "age";
  assert (get s "age" = None);
  assert (size s = 2);

  let ks = List.sort compare (keys s) in
  assert (ks = ["city"; "name"]);

  (* Functional store *)
  let fs = [] in
  let fs = fset fs "x" 1 in
  let fs = fset fs "y" 2 in
  let fs = fset fs "x" 10 in (* update *)
  assert (fget fs "x" = Some 10);
  assert (fget fs "y" = Some 2);
  assert (fget fs "z" = None);

  let fs = fdelete fs "y" in
  assert (fget fs "y" = None);
  assert (fkeys fs = ["x"]);

  Printf.printf "✓ All tests passed\n"

Key Differences

Aspect	Rust	OCaml
Hash table	`HashMap` — O(1) average	`Hashtbl` — O(1) average (mutable)
Ergonomic insertion	`impl Into<String>`	Direct `string` — no conversion needed
Functional variant	`Vec<(String, String)>` — O(n) lookup	Association list — same
Sorted keys	Manual `.sort()`	`List.sort String.compare`
Remove result	`Option<String>` — know if key existed	`unit` — `Hashtbl.remove` is void

HashMap does not guarantee key order. Use BTreeMap when sorted iteration matters for correctness (e.g., when serializing to a deterministic format). The keys() method here sorts on each call — for read-heavy usage, consider maintaining a sorted BTreeMap instead.

OCaml Approach

(* Mutable: Hashtbl *)
module KvStore = struct
  type t = (string, string) Hashtbl.t

  let create () = Hashtbl.create 16
  let set tbl k v = Hashtbl.replace tbl k v
  let get tbl k = Hashtbl.find_opt tbl k
  let delete tbl k = Hashtbl.remove tbl k
  let contains tbl k = Hashtbl.mem tbl k
  let keys tbl =
    Hashtbl.fold (fun k _ acc -> k :: acc) tbl []
    |> List.sort String.compare
end

(* Functional: association list *)
let set_al k v pairs = (k, v) :: List.filter (fun (k', _) -> k' <> k) pairs
let get_al k pairs = List.assoc_opt k pairs
let delete_al k pairs = List.filter (fun (k', _) -> k' <> k) pairs

OCaml's Hashtbl is a mutable hash table similar to Rust's HashMap. The functional association list approach creates new lists on every update — persistent but O(n) for all operations.

Full Source

#![allow(clippy::all)]
// 960: Key-Value Store
// OCaml: Hashtbl (mutable) or association list (functional)
// Rust: HashMap<String, String> (mutable) or BTreeMap for sorted iteration

use std::collections::HashMap;

// Approach 1: HashMap-based mutable store
pub struct KvStore {
    data: HashMap<String, String>,
}

impl KvStore {
    pub fn new() -> Self {
        KvStore {
            data: HashMap::new(),
        }
    }

    pub fn set(&mut self, key: impl Into<String>, value: impl Into<String>) {
        self.data.insert(key.into(), value.into());
    }

    pub fn get(&self, key: &str) -> Option<&str> {
        self.data.get(key).map(|s| s.as_str())
    }

    pub fn delete(&mut self, key: &str) -> bool {
        self.data.remove(key).is_some()
    }

    pub fn contains(&self, key: &str) -> bool {
        self.data.contains_key(key)
    }

    pub fn keys(&self) -> Vec<&str> {
        let mut keys: Vec<&str> = self.data.keys().map(|s| s.as_str()).collect();
        keys.sort();
        keys
    }

    pub fn values(&self) -> Vec<&str> {
        self.data.values().map(|s| s.as_str()).collect()
    }

    pub fn size(&self) -> usize {
        self.data.len()
    }

    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }
}

impl Default for KvStore {
    fn default() -> Self {
        Self::new()
    }
}

// Approach 2: Functional (immutable) KV using Vec of pairs
#[derive(Clone, Debug)]
pub struct FunctionalStore<V: Clone> {
    data: Vec<(String, V)>,
}

impl<V: Clone> FunctionalStore<V> {
    pub fn new() -> Self {
        FunctionalStore { data: vec![] }
    }

    pub fn set(&self, key: impl Into<String>, value: V) -> Self {
        let key = key.into();
        let mut data: Vec<(String, V)> = self
            .data
            .iter()
            .filter(|(k, _)| k != &key)
            .cloned()
            .collect();
        data.insert(0, (key, value));
        FunctionalStore { data }
    }

    pub fn get(&self, key: &str) -> Option<&V> {
        self.data.iter().find(|(k, _)| k == key).map(|(_, v)| v)
    }

    pub fn delete(&self, key: &str) -> Self {
        let data = self
            .data
            .iter()
            .filter(|(k, _)| k != key)
            .cloned()
            .collect();
        FunctionalStore { data }
    }

    pub fn keys(&self) -> Vec<&str> {
        self.data.iter().map(|(k, _)| k.as_str()).collect()
    }
}

impl<V: Clone> Default for FunctionalStore<V> {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_mutable_store() {
        let mut s = KvStore::new();
        assert_eq!(s.size(), 0);
        assert!(s.is_empty());

        s.set("name", "Alice");
        s.set("age", "30");
        s.set("city", "Amsterdam");

        assert_eq!(s.get("name"), Some("Alice"));
        assert_eq!(s.get("age"), Some("30"));
        assert_eq!(s.get("missing"), None);
        assert!(s.contains("city"));
        assert!(!s.contains("missing"));
        assert_eq!(s.size(), 3);
    }

    #[test]
    fn test_update() {
        let mut s = KvStore::new();
        s.set("name", "Alice");
        s.set("name", "Bob");
        assert_eq!(s.get("name"), Some("Bob"));
        assert_eq!(s.size(), 1);
    }

    #[test]
    fn test_delete() {
        let mut s = KvStore::new();
        s.set("name", "Alice");
        s.set("age", "30");
        let removed = s.delete("age");
        assert!(removed);
        assert_eq!(s.get("age"), None);
        assert_eq!(s.size(), 1);
        assert!(!s.delete("missing"));
    }

    #[test]
    fn test_keys_sorted() {
        let mut s = KvStore::new();
        s.set("city", "Amsterdam");
        s.set("name", "Alice");
        assert_eq!(s.keys(), vec!["city", "name"]);
    }

    #[test]
    fn test_functional_store() {
        let fs: FunctionalStore<i32> = FunctionalStore::new();
        let fs = fs.set("x", 1);
        let fs = fs.set("y", 2);
        let fs = fs.set("x", 10); // update
        assert_eq!(fs.get("x"), Some(&10));
        assert_eq!(fs.get("y"), Some(&2));
        assert_eq!(fs.get("z"), None);

        let fs2 = fs.delete("y");
        assert_eq!(fs2.get("y"), None);
        assert_eq!(fs.get("y"), Some(&2)); // original unchanged
    }
}

(* 960: Key-Value Store *)
(* Simple in-memory KV store using Hashtbl *)

(* Approach 1: Hashtbl-based store with functional interface *)

type 'a store = (string, 'a) Hashtbl.t

let create () : 'a store = Hashtbl.create 16

let set store key value =
  Hashtbl.replace store key value

let get store key =
  Hashtbl.find_opt store key

let delete store key =
  Hashtbl.remove store key

let keys store =
  Hashtbl.fold (fun k _ acc -> k :: acc) store []

let values store =
  Hashtbl.fold (fun _ v acc -> v :: acc) store []

let size store = Hashtbl.length store

let contains store key = Hashtbl.mem store key

(* Approach 2: Functional (immutable) KV using association list *)

type 'a fstore = (string * 'a) list

let fset (store : 'a fstore) key value : 'a fstore =
  (key, value) :: List.filter (fun (k, _) -> k <> key) store

let fget (store : 'a fstore) key =
  List.assoc_opt key store

let fdelete (store : 'a fstore) key : 'a fstore =
  List.filter (fun (k, _) -> k <> key) store

let fkeys (store : 'a fstore) =
  List.map fst store

let () =
  (* Mutable store *)
  let s = create () in
  assert (size s = 0);

  set s "name" "Alice";
  set s "age" "30";
  set s "city" "Amsterdam";

  assert (get s "name" = Some "Alice");
  assert (get s "age" = Some "30");
  assert (get s "missing" = None);
  assert (contains s "city");
  assert (not (contains s "missing"));
  assert (size s = 3);

  (* Update existing key *)
  set s "name" "Bob";
  assert (get s "name" = Some "Bob");
  assert (size s = 3);

  (* Delete *)
  delete s "age";
  assert (get s "age" = None);
  assert (size s = 2);

  let ks = List.sort compare (keys s) in
  assert (ks = ["city"; "name"]);

  (* Functional store *)
  let fs = [] in
  let fs = fset fs "x" 1 in
  let fs = fset fs "y" 2 in
  let fs = fset fs "x" 10 in (* update *)
  assert (fget fs "x" = Some 10);
  assert (fget fs "y" = Some 2);
  assert (fget fs "z" = None);

  let fs = fdelete fs "y" in
  assert (fget fs "y" = None);
  assert (fkeys fs = ["x"]);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_mutable_store() {
        let mut s = KvStore::new();
        assert_eq!(s.size(), 0);
        assert!(s.is_empty());

        s.set("name", "Alice");
        s.set("age", "30");
        s.set("city", "Amsterdam");

        assert_eq!(s.get("name"), Some("Alice"));
        assert_eq!(s.get("age"), Some("30"));
        assert_eq!(s.get("missing"), None);
        assert!(s.contains("city"));
        assert!(!s.contains("missing"));
        assert_eq!(s.size(), 3);
    }

    #[test]
    fn test_update() {
        let mut s = KvStore::new();
        s.set("name", "Alice");
        s.set("name", "Bob");
        assert_eq!(s.get("name"), Some("Bob"));
        assert_eq!(s.size(), 1);
    }

    #[test]
    fn test_delete() {
        let mut s = KvStore::new();
        s.set("name", "Alice");
        s.set("age", "30");
        let removed = s.delete("age");
        assert!(removed);
        assert_eq!(s.get("age"), None);
        assert_eq!(s.size(), 1);
        assert!(!s.delete("missing"));
    }

    #[test]
    fn test_keys_sorted() {
        let mut s = KvStore::new();
        s.set("city", "Amsterdam");
        s.set("name", "Alice");
        assert_eq!(s.keys(), vec!["city", "name"]);
    }

    #[test]
    fn test_functional_store() {
        let fs: FunctionalStore<i32> = FunctionalStore::new();
        let fs = fs.set("x", 1);
        let fs = fs.set("y", 2);
        let fs = fs.set("x", 10); // update
        assert_eq!(fs.get("x"), Some(&10));
        assert_eq!(fs.get("y"), Some(&2));
        assert_eq!(fs.get("z"), None);

        let fs2 = fs.delete("y");
        assert_eq!(fs2.get("y"), None);
        assert_eq!(fs.get("y"), Some(&2)); // original unchanged
    }
}

Deep Comparison

Key-Value Store — Comparison

Core Insight

Both Hashtbl (OCaml) and HashMap (Rust) are hash-based mutable dictionaries. The API is nearly identical. The key difference: Rust wraps state in a struct with &mut self methods (enforcing ownership), while OCaml passes the table as a function argument. Both languages also support functional association lists for immutable KV storage.

OCaml Approach

• Hashtbl.create 16 creates a mutable table with initial capacity

• Hashtbl.replace — set (handles both insert and update)

• Hashtbl.find_opt — get returning option

• Hashtbl.remove — delete key

• Hashtbl.mem — contains check

• Hashtbl.fold — iterate over all entries

• Functional alternative: (string * 'a) list with List.assoc_opt

Rust Approach

• HashMap::new() wrapped in a struct for encapsulation

• insert (returns old value), get, remove, contains_key

• &self for reads, &mut self for writes — ownership enforced by compiler

• impl Into<String> for flexible key/value input

• Functional alternative: Vec<(String, V)> with filter + find

Comparison Table

Aspect	OCaml	Rust
Hash table	`Hashtbl.t`	`HashMap<K, V>`
Create	`Hashtbl.create 16`	`HashMap::new()`
Insert/update	`Hashtbl.replace t k v`	`map.insert(k, v)`
Lookup	`Hashtbl.find_opt t k`	`map.get(k)` → `Option<&V>`
Delete	`Hashtbl.remove t k`	`map.remove(k)`
Contains	`Hashtbl.mem t k`	`map.contains_key(k)`
Iteration	`Hashtbl.fold` / `Hashtbl.iter`	`.iter()` / `.keys()` / `.values()`
Encapsulation	Module functions + table arg	`struct` with `impl` block
Mutation	Passed by value (mutable)	`&mut self` methods

Exercises

Add a merge(other: &KvStore) method that copies all entries from other, with other winning on conflicts.

Implement update<F: Fn(&str) -> String>(key: &str, f: F) that applies a function to an existing value.

Add an event log: record each set and delete with a timestamp in a Vec<(Instant, Event)>.

Implement prefix_keys(prefix: &str) -> Vec<&str> that returns all keys starting with the given prefix.

Build a persistent_kv_store that serializes to/from a file using serde_json on HashMap<String, String>.

Open Source Repos

functional-rust

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

Rust