970 Fundamental

970 Rope String

Functional Programming

Tutorial

The Problem

Implement a rope — a tree-based string representation that enables O(log n) concatenation, splitting, and indexing for large strings. A Rope is either a Leaf(String) or a Node(left, right, total_len). Concatenation creates a new Node without copying content. Collecting to a String is O(n) but infrequent.

🎯 Learning Outcomes

• Define enum Rope { Leaf(String), Node(Box<Rope>, Box<Rope>, usize) } with length cached in Node

• Implement concat(left, right) -> Rope that creates a Node in O(1) — no string copying

• Implement len(&self) by reading the cached length from Node or Leaf::len()

• Implement char_at(&self, idx: usize) -> Option<char> by navigating left/right subtrees using cached lengths

• Implement to_string_val(&self) -> String as a recursive O(n) collection

Code Example

#![allow(clippy::all)]
// 970: Rope String
// Tree-based string for O(log n) concat/split, O(log n) indexing
// OCaml: recursive type; Rust: enum with Box for recursion

#[derive(Debug, Clone)]
pub enum Rope {
    Leaf(String),
    Node(Box<Rope>, Box<Rope>, usize), // left, right, total_len
}

impl Rope {
    pub fn from_str(s: &str) -> Self {
        Rope::Leaf(s.to_string())
    }

    pub fn len(&self) -> usize {
        match self {
            Rope::Leaf(s) => s.len(),
            Rope::Node(_, _, n) => *n,
        }
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    pub fn concat(left: Rope, right: Rope) -> Rope {
        let total = left.len() + right.len();
        Rope::Node(Box::new(left), Box::new(right), total)
    }

    /// Collect rope into a String (O(n))
    pub fn to_string_val(&self) -> String {
        match self {
            Rope::Leaf(s) => s.clone(),
            Rope::Node(l, r, _) => {
                let mut out = l.to_string_val();
                out.push_str(&r.to_string_val());
                out
            }
        }
    }

    /// Get character at index i (O(log n))
    pub fn index(&self, i: usize) -> Option<char> {
        match self {
            Rope::Leaf(s) => s.chars().nth(i),
            Rope::Node(l, r, _) => {
                let ln = l.len();
                if i < ln {
                    l.index(i)
                } else {
                    r.index(i - ln)
                }
            }
        }
    }

    /// Split at position i: returns (left[0..i], right[i..])
    pub fn split(self, i: usize) -> (Rope, Rope) {
        match self {
            Rope::Leaf(s) => {
                let i = i.min(s.len());
                let left = Rope::Leaf(s[..i].to_string());
                let right = Rope::Leaf(s[i..].to_string());
                (left, right)
            }
            Rope::Node(l, r, _) => {
                let ln = l.len();
                if i <= ln {
                    let (ll, lr) = l.split(i);
                    (ll, Rope::concat(lr, *r))
                } else {
                    let (rl, rr) = r.split(i - ln);
                    (Rope::concat(*l, rl), rr)
                }
            }
        }
    }

    /// Extract substring [start, start+len)
    pub fn sub(&self, start: usize, len: usize) -> String {
        let (_, right) = self.clone().split(start);
        let (mid, _) = right.split(len);
        mid.to_string_val()
    }
}

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

    fn make_rope() -> Rope {
        let r1 = Rope::from_str("Hello");
        let r2 = Rope::from_str(", ");
        let r3 = Rope::from_str("World");
        let r4 = Rope::from_str("!");
        Rope::concat(Rope::concat(r1, r2), Rope::concat(r3, r4))
    }

    #[test]
    fn test_length_and_to_string() {
        let rope = make_rope();
        assert_eq!(rope.len(), 13);
        assert_eq!(rope.to_string_val(), "Hello, World!");
    }

    #[test]
    fn test_index() {
        let rope = make_rope();
        assert_eq!(rope.index(0), Some('H'));
        assert_eq!(rope.index(7), Some('W'));
        assert_eq!(rope.index(12), Some('!'));
        assert_eq!(rope.index(13), None);
    }

    #[test]
    fn test_sub() {
        let rope = make_rope();
        assert_eq!(rope.sub(7, 5), "World");
        assert_eq!(rope.sub(0, 5), "Hello");
        assert_eq!(rope.sub(5, 2), ", ");
    }

    #[test]
    fn test_split() {
        let rope = make_rope();
        let (left, right) = rope.split(7);
        assert_eq!(left.to_string_val(), "Hello, ");
        assert_eq!(right.to_string_val(), "World!");
    }

    #[test]
    fn test_empty_rope() {
        let r = Rope::from_str("");
        assert!(r.is_empty());
        assert_eq!(r.to_string_val(), "");
    }
}

(* 970: Rope String *)
(* Tree-based string structure for O(log n) concatenation *)
(* Naive concat is O(1), but split/index are O(log n) *)

type rope =
  | Leaf of string
  | Node of rope * rope * int  (* left, right, total_length *)

let length = function
  | Leaf s -> String.length s
  | Node (_, _, n) -> n

let concat r1 r2 =
  Node (r1, r2, length r1 + length r2)

let of_string s = Leaf s

(* Convert rope back to string *)
let rec to_string = function
  | Leaf s -> s
  | Node (l, r, _) -> to_string l ^ to_string r

(* Index: get character at position i *)
let rec index rope i =
  match rope with
  | Leaf s ->
    if i >= 0 && i < String.length s then Some s.[i]
    else None
  | Node (l, r, _) ->
    let ln = length l in
    if i < ln then index l i
    else index r (i - ln)

(* Split rope into (left, right) at position i *)
let rec split rope i =
  match rope with
  | Leaf s ->
    let n = String.length s in
    let i = max 0 (min i n) in
    (Leaf (String.sub s 0 i), Leaf (String.sub s i (n - i)))
  | Node (l, r, _) ->
    let ln = length l in
    if i <= ln then
      let (ll, lr) = split l i in
      (ll, concat lr r)
    else
      let (rl, rr) = split r (i - ln) in
      (concat l rl, rr)

(* Substring extraction *)
let sub rope start len =
  let (_, right) = split rope start in
  let (mid, _) = split right len in
  to_string mid

let () =
  let r1 = of_string "Hello" in
  let r2 = of_string ", " in
  let r3 = of_string "World" in
  let r4 = of_string "!" in

  let rope = concat (concat r1 r2) (concat r3 r4) in
  assert (length rope = 13);
  assert (to_string rope = "Hello, World!");

  assert (index rope 0 = Some 'H');
  assert (index rope 7 = Some 'W');
  assert (index rope 12 = Some '!');
  assert (index rope 13 = None);

  assert (sub rope 7 5 = "World");
  assert (sub rope 0 5 = "Hello");

  let (left, right) = split rope 7 in
  assert (to_string left = "Hello, ");
  assert (to_string right = "World!");

  Printf.printf "✓ All tests passed\n"

Key Differences

Aspect	Rust	OCaml
Recursive enum	`Box<Rope>` in variants (required)	Direct recursion (GC handles indirection)
Concat	O(1) — allocates one `Node`	O(1) — allocates one `Node` record
`to_string`	O(n) — `push_str` into buffer	O(n) — `^` for each concat
`char_at`	O(log n) for balanced tree	O(log n) same

Ropes are valuable for large text editors where users insert and delete characters frequently. For strings under ~1KB, plain String is faster due to CPU cache effects.

OCaml Approach

type rope =
  | Leaf of string
  | Node of rope * rope * int  (* left, right, len *)

let from_str s = Leaf s

let len = function
  | Leaf s -> String.length s
  | Node (_, _, n) -> n

let concat l r = Node (l, r, len l + len r)

let rec char_at rope idx =
  match rope with
  | Leaf s -> if idx < String.length s then Some s.[idx] else None
  | Node (left, right, _) ->
    let ll = len left in
    if idx < ll then char_at left idx
    else char_at right (idx - ll)

let rec to_string = function
  | Leaf s -> s
  | Node (l, r, _) -> to_string l ^ to_string r  (* O(n) due to ^ *)

OCaml's ^ is string concatenation — O(n) for the concat step. The rope type delays this cost: concat in OCaml is O(1) just like in Rust.

Full Source

#![allow(clippy::all)]
// 970: Rope String
// Tree-based string for O(log n) concat/split, O(log n) indexing
// OCaml: recursive type; Rust: enum with Box for recursion

#[derive(Debug, Clone)]
pub enum Rope {
    Leaf(String),
    Node(Box<Rope>, Box<Rope>, usize), // left, right, total_len
}

impl Rope {
    pub fn from_str(s: &str) -> Self {
        Rope::Leaf(s.to_string())
    }

    pub fn len(&self) -> usize {
        match self {
            Rope::Leaf(s) => s.len(),
            Rope::Node(_, _, n) => *n,
        }
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    pub fn concat(left: Rope, right: Rope) -> Rope {
        let total = left.len() + right.len();
        Rope::Node(Box::new(left), Box::new(right), total)
    }

    /// Collect rope into a String (O(n))
    pub fn to_string_val(&self) -> String {
        match self {
            Rope::Leaf(s) => s.clone(),
            Rope::Node(l, r, _) => {
                let mut out = l.to_string_val();
                out.push_str(&r.to_string_val());
                out
            }
        }
    }

    /// Get character at index i (O(log n))
    pub fn index(&self, i: usize) -> Option<char> {
        match self {
            Rope::Leaf(s) => s.chars().nth(i),
            Rope::Node(l, r, _) => {
                let ln = l.len();
                if i < ln {
                    l.index(i)
                } else {
                    r.index(i - ln)
                }
            }
        }
    }

    /// Split at position i: returns (left[0..i], right[i..])
    pub fn split(self, i: usize) -> (Rope, Rope) {
        match self {
            Rope::Leaf(s) => {
                let i = i.min(s.len());
                let left = Rope::Leaf(s[..i].to_string());
                let right = Rope::Leaf(s[i..].to_string());
                (left, right)
            }
            Rope::Node(l, r, _) => {
                let ln = l.len();
                if i <= ln {
                    let (ll, lr) = l.split(i);
                    (ll, Rope::concat(lr, *r))
                } else {
                    let (rl, rr) = r.split(i - ln);
                    (Rope::concat(*l, rl), rr)
                }
            }
        }
    }

    /// Extract substring [start, start+len)
    pub fn sub(&self, start: usize, len: usize) -> String {
        let (_, right) = self.clone().split(start);
        let (mid, _) = right.split(len);
        mid.to_string_val()
    }
}

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

    fn make_rope() -> Rope {
        let r1 = Rope::from_str("Hello");
        let r2 = Rope::from_str(", ");
        let r3 = Rope::from_str("World");
        let r4 = Rope::from_str("!");
        Rope::concat(Rope::concat(r1, r2), Rope::concat(r3, r4))
    }

    #[test]
    fn test_length_and_to_string() {
        let rope = make_rope();
        assert_eq!(rope.len(), 13);
        assert_eq!(rope.to_string_val(), "Hello, World!");
    }

    #[test]
    fn test_index() {
        let rope = make_rope();
        assert_eq!(rope.index(0), Some('H'));
        assert_eq!(rope.index(7), Some('W'));
        assert_eq!(rope.index(12), Some('!'));
        assert_eq!(rope.index(13), None);
    }

    #[test]
    fn test_sub() {
        let rope = make_rope();
        assert_eq!(rope.sub(7, 5), "World");
        assert_eq!(rope.sub(0, 5), "Hello");
        assert_eq!(rope.sub(5, 2), ", ");
    }

    #[test]
    fn test_split() {
        let rope = make_rope();
        let (left, right) = rope.split(7);
        assert_eq!(left.to_string_val(), "Hello, ");
        assert_eq!(right.to_string_val(), "World!");
    }

    #[test]
    fn test_empty_rope() {
        let r = Rope::from_str("");
        assert!(r.is_empty());
        assert_eq!(r.to_string_val(), "");
    }
}

(* 970: Rope String *)
(* Tree-based string structure for O(log n) concatenation *)
(* Naive concat is O(1), but split/index are O(log n) *)

type rope =
  | Leaf of string
  | Node of rope * rope * int  (* left, right, total_length *)

let length = function
  | Leaf s -> String.length s
  | Node (_, _, n) -> n

let concat r1 r2 =
  Node (r1, r2, length r1 + length r2)

let of_string s = Leaf s

(* Convert rope back to string *)
let rec to_string = function
  | Leaf s -> s
  | Node (l, r, _) -> to_string l ^ to_string r

(* Index: get character at position i *)
let rec index rope i =
  match rope with
  | Leaf s ->
    if i >= 0 && i < String.length s then Some s.[i]
    else None
  | Node (l, r, _) ->
    let ln = length l in
    if i < ln then index l i
    else index r (i - ln)

(* Split rope into (left, right) at position i *)
let rec split rope i =
  match rope with
  | Leaf s ->
    let n = String.length s in
    let i = max 0 (min i n) in
    (Leaf (String.sub s 0 i), Leaf (String.sub s i (n - i)))
  | Node (l, r, _) ->
    let ln = length l in
    if i <= ln then
      let (ll, lr) = split l i in
      (ll, concat lr r)
    else
      let (rl, rr) = split r (i - ln) in
      (concat l rl, rr)

(* Substring extraction *)
let sub rope start len =
  let (_, right) = split rope start in
  let (mid, _) = split right len in
  to_string mid

let () =
  let r1 = of_string "Hello" in
  let r2 = of_string ", " in
  let r3 = of_string "World" in
  let r4 = of_string "!" in

  let rope = concat (concat r1 r2) (concat r3 r4) in
  assert (length rope = 13);
  assert (to_string rope = "Hello, World!");

  assert (index rope 0 = Some 'H');
  assert (index rope 7 = Some 'W');
  assert (index rope 12 = Some '!');
  assert (index rope 13 = None);

  assert (sub rope 7 5 = "World");
  assert (sub rope 0 5 = "Hello");

  let (left, right) = split rope 7 in
  assert (to_string left = "Hello, ");
  assert (to_string right = "World!");

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    fn make_rope() -> Rope {
        let r1 = Rope::from_str("Hello");
        let r2 = Rope::from_str(", ");
        let r3 = Rope::from_str("World");
        let r4 = Rope::from_str("!");
        Rope::concat(Rope::concat(r1, r2), Rope::concat(r3, r4))
    }

    #[test]
    fn test_length_and_to_string() {
        let rope = make_rope();
        assert_eq!(rope.len(), 13);
        assert_eq!(rope.to_string_val(), "Hello, World!");
    }

    #[test]
    fn test_index() {
        let rope = make_rope();
        assert_eq!(rope.index(0), Some('H'));
        assert_eq!(rope.index(7), Some('W'));
        assert_eq!(rope.index(12), Some('!'));
        assert_eq!(rope.index(13), None);
    }

    #[test]
    fn test_sub() {
        let rope = make_rope();
        assert_eq!(rope.sub(7, 5), "World");
        assert_eq!(rope.sub(0, 5), "Hello");
        assert_eq!(rope.sub(5, 2), ", ");
    }

    #[test]
    fn test_split() {
        let rope = make_rope();
        let (left, right) = rope.split(7);
        assert_eq!(left.to_string_val(), "Hello, ");
        assert_eq!(right.to_string_val(), "World!");
    }

    #[test]
    fn test_empty_rope() {
        let r = Rope::from_str("");
        assert!(r.is_empty());
        assert_eq!(r.to_string_val(), "");
    }
}

Deep Comparison

Rope String — Comparison

Core Insight

A rope represents a string as a binary tree of smaller strings (leaves). Concatenation creates a new Node in O(1). Indexing and splitting traverse the tree in O(log n). Both languages express this as a recursive algebraic type. The critical Rust difference: Box<Rope> is required because recursive enum variants must have statically known size, and a direct self-reference would be infinite.

OCaml Approach

• type rope = Leaf of string | Node of rope * rope * int — recursive type, implicit

• No heap boxing needed — OCaml's GC handles pointer-sized references automatically

• String.sub s 0 i for splitting leaf strings

• s.[i] for character access (byte index)

• to_string l ^ to_string r — string concatenation (O(n) but readable)

Rust Approach

• enum Rope { Leaf(String), Node(Box<Rope>, Box<Rope>, usize) } — explicit Box

• Box::new(...) allocates on the heap, providing the indirection needed for recursion

• s[..i].to_string() for splitting (byte-indexed slice)

• s.chars().nth(i) for Unicode-safe character access

• #[derive(Clone)] needed because to_string_val requires cloning for sub

• l.to_string_val() + push_str instead of ^ operator

Comparison Table

Aspect	OCaml	Rust
Recursive type	`type rope = ... Node of rope * rope * int`	`enum Rope { Node(Box<Rope>, Box<Rope>, usize) }`
Heap boxing	Implicit (GC)	Explicit `Box<T>`
String split	`String.sub s 0 i`	`s[..i].to_string()`
Char access	`s.[i]` (byte)	`s.chars().nth(i)` (Unicode)
Concat strings	`^` operator	`String::push_str`
Clone	Not needed (GC shares)	`#[derive(Clone)]` explicit
Length field	`int`	`usize`

Exercises

Implement split(rope, pos) -> (Rope, Rope) that splits the rope at character index pos in O(log n).

Implement insert(rope, pos, s) that inserts string s at position pos using split + concat.

Implement delete(rope, l, r) that removes characters in range [l, r) using split + concat.

Implement rope rebalancing: when a rope's tree depth exceeds 2 * log2(len), flatten to a Leaf and rebuild.

Implement iter_chars(&self) -> impl Iterator<Item=char> that lazily yields characters without materializing the full string.

Open Source Repos

functional-rust

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

Rust