ExamplesBy LevelBy TopicLearning Paths
020 Intermediate
← 019021 →

020 — Remove the Kth Element

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "020 — Remove the Kth Element" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Removing the element at position k from a list (OCaml 99 Problems #20) is a fundamental list surgery operation — the building block for deletion in arrays, linked lists, and sequences. Key difference from OCaml: 1. **`Vec::remove` vs list surgery**: Rust's `Vec::remove(i)` is O(n) due to shifting. OCaml's list removal reconstructs the prefix list, also O(n) but with different constant factors.

Tutorial

The Problem

Removing the element at position k from a list (OCaml 99 Problems #20) is a fundamental list surgery operation — the building block for deletion in arrays, linked lists, and sequences. It produces a new list with one element missing and returns both the removed element and the modified list.

This pattern appears everywhere: removing a player from a queue, deleting a row from a table, extracting the winner from a lottery draw (example 024), and implementing undo operations. The challenge is handling the removed element cleanly — returning it alongside the modified list as a tuple.

🎯 Learning Outcomes

  • • Return a (T, Vec<T>) tuple to simultaneously yield the removed element and the new list
  • • Use enumerate().filter() or explicit split for position-based removal
  • • Handle out-of-bounds removal gracefully with Option<(T, Vec<T>)>
  • • Implement both the iterative and recursive versions
  • • Understand k as 1-based (OCaml 99) vs 0-based (Rust convention)
  • • Return Option<(T, Vec<T>)> for safe out-of-bounds handling rather than panicking
  • • Distinguish Vec::remove(k) (O(n) shift, in-place) from Vec::swap_remove(k) (O(1), changes order)

    • Code Example

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

    Key Differences

  • **Vec::remove vs list surgery**: Rust's Vec::remove(i) is O(n) due to shifting. OCaml's list removal reconstructs the prefix list, also O(n) but with different constant factors.
  • Error handling: Rust's Vec::remove panics on out-of-bounds. Return Option or check bounds first. OCaml uses failwith (raises an exception).
  • **rev_append**: OCaml's List.rev_append acc t is a key idiom — it combines reversing the accumulator with appending the tail in one pass. Rust achieves the same with [&v[..k], &v[k+1..]].concat().
  • Indexing: OCaml 99 Problems uses 1-based indexing. Rust's standard library uses 0-based. Always be explicit about which convention is used.
  • **Vec::remove in-place:** Rust's v.remove(k) removes and returns the element at index k, shifting elements left — O(n). Returns the removed value directly (panics on out-of-bounds).
  • **Option for safety:** The safe version returns Option<(T, Vec<T>)> to handle out-of-bounds. OCaml's version typically raises an exception on invalid index.
  • Slice concatenation: [&v[..k], &v[k+1..]].concat() creates a new Vec skipping index k — O(n) with explicit O(n) allocation. Both forms are equivalent.

    • OCaml Approach

    OCaml's version: let remove_at k lst = let rec aux acc n = function | [] -> failwith "index out of bounds" | x :: t -> if n = k then (x, List.rev_append acc t) else aux (x :: acc) (n + 1) t in aux [] 1 lst. List.rev_append acc t concatenates the reversed accumulator with the tail — this is O(n) and avoids a separate reverse call.

    OCaml's version returns a tuple: let rec remove_at k = function | [] -> (None, []) | h :: t -> if k = 1 then (Some h, t) else let (removed, rest) = remove_at (k-1) t in (removed, h :: rest). The tail-recursive version uses an accumulator for the prefix, reversing at the end. OCaml's 99 Problems uses 1-based indexing.

    Full Source

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

    Deep Comparison

    OCaml vs Rust: Remove Kth

    Overview

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

    Key Differences

    AspectOCamlRust
    Type systemHindley-MilnerOwnership + traits
    MemoryGCZero-cost abstractions
    MutabilityExplicit refmut keyword
    Error handlingOption/ResultResult<T, E>

    See README.md for detailed comparison.

    Exercises

  • Remove all of value: Write remove_all(v: &[i32], x: i32) -> Vec<i32> that removes all occurrences of x using .filter(). Compare with retain() (in-place filter).
  • Remove first of value: Write remove_first(v: &[i32], x: i32) -> Option<Vec<i32>> that removes only the first occurrence. Use .iter().position() to find the index.
  • Remove and reinsert: Write move_to_end(v: &mut Vec<i32>, k: usize) that removes the element at position k and appends it to the end, using Vec::remove and Vec::push.
  • Multi-remove: Implement remove_all(v: &[T], indices: &[usize]) -> Vec<T> that removes elements at multiple indices in one pass. Sort indices first to process them efficiently.
  • Swap remove: Implement swap_remove_safe(v: &mut Vec<T>, k: usize) -> Option<T> — O(1) removal by swapping the element with the last one. Useful when order doesn't matter.

    • Open Source Repos

    functional-rust

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

    Rust