066: Sequence Monadic

Difficulty: ⭐⭐ Level: Foundations Turn a list of optional or fallible values into a single optional or fallible list — and understand why `collect()` is Rust's universal sequence operator.

The Problem This Solves

You have a `Vec<Option<T>>` — maybe from a list of lookups that might not find anything — and you want a single `Option<Vec<T>>`. If any lookup returned `None`, the whole thing should be `None`. If all succeeded, you want the collected values. Same pattern for errors: `Vec<Result<T, E>>` → `Result<Vec<T>, E>`. This is called `sequence` in functional programming. It's the pattern behind "if everything succeeds, give me the results; otherwise give me the failure." Without sequence, you write a loop with early returns, accumulating into a temporary vec, checking for failures, returning the right variant. Every time. With sequence, it's one line.

The Intuition

`sequence` is `traverse` with the identity function — you're not transforming values, just flipping the container nesting. A list of Optionals becomes an Optional list. A list of Results becomes a Result of list. In OCaml, you write this with `fold_right`, pattern-matching on each element. In Rust, `collect()` does it for you — it's polymorphic over the output container type, and both `Option` and `Result` implement the `FromIterator` trait that makes this work. Think of `collect()` as "assemble these pieces into the right container." When the container is `Result<Vec<_>, _>`, it knows to short-circuit on `Err`. When it's `Option<Vec<_>>`, it short-circuits on `None`.

How It Works in Rust

// sequence for Option: None anywhere → None
fn sequence_option<T>(xs: Vec<Option<T>>) -> Option<Vec<T>> {
 xs.into_iter().collect()
}

// sequence for Result: Err anywhere → first Err
fn sequence_result<T, E>(xs: Vec<Result<T, E>>) -> Result<Vec<T>, E> {
 xs.into_iter().collect()
}

Real-world example — parse a list of strings, fail if any is invalid:

let parsed: Option<Vec<i32>> = vec!["1", "2", "3"]
 .iter()
 .map(|s| s.parse::<i32>().ok())  // each parse gives Option<i32>
 .collect();                        // collect() turns Vec<Option<i32>> into Option<Vec<i32>>

// parsed == Some(vec![1, 2, 3])
// If any string was "bad", parsed == None

What This Unlocks

Batch lookups — query a database for multiple IDs; if any is missing, return `None`
Multi-field parsing — parse every field in a struct from strings; get `Result<Struct, Error>` at the end
Chaining optional steps — combine multiple `Option`-returning operations into one

Key Differences

Concept	OCaml	Rust
sequence for Option	`fold_right` with pattern match	`.collect::<Option<Vec<_>>>()`
sequence for Result	`fold_right` with pattern match	`.collect::<Result<Vec<_>,_>>()`
Generic sequence	Higher-order `bind`/`return_`	`FromIterator` trait (built-in)
Short-circuit	Returns first `None`/`Error e`	Same semantics, built into `collect()`

// Example 066: Sequence Monadic
// Turn a collection of monadic values into a monadic collection

// Approach 1: sequence for Option using collect
fn sequence_option<T>(xs: Vec<Option<T>>) -> Option<Vec<T>> {
    xs.into_iter().collect()
}

// Approach 2: sequence for Result using collect
fn sequence_result<T, E>(xs: Vec<Result<T, E>>) -> Result<Vec<T>, E> {
    xs.into_iter().collect()
}

// Approach 3: Manual fold implementation
fn sequence_option_fold<T>(xs: Vec<Option<T>>) -> Option<Vec<T>> {
    xs.into_iter().try_fold(Vec::new(), |mut acc, x| {
        acc.push(x?);
        Some(acc)
    })
}

fn sequence_result_fold<T, E>(xs: Vec<Result<T, E>>) -> Result<Vec<T>, E> {
    xs.into_iter().try_fold(Vec::new(), |mut acc, x| {
        acc.push(x?);
        Ok(acc)
    })
}


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

    #[test]
    fn test_sequence_option_all_some() {
        assert_eq!(sequence_option(vec![Some(1), Some(2), Some(3)]), Some(vec![1, 2, 3]));
    }

    #[test]
    fn test_sequence_option_with_none() {
        assert_eq!(sequence_option(vec![Some(1), None, Some(3)]), None);
    }

    #[test]
    fn test_sequence_option_empty() {
        assert_eq!(sequence_option::<i32>(vec![]), Some(vec![]));
    }

    #[test]
    fn test_sequence_result_all_ok() {
        assert_eq!(sequence_result::<i32, String>(vec![Ok(1), Ok(2), Ok(3)]), Ok(vec![1, 2, 3]));
    }

    #[test]
    fn test_sequence_result_with_err() {
        let rs: Vec<Result<i32, &str>> = vec![Ok(1), Err("e"), Ok(3)];
        assert_eq!(sequence_result(rs), Err("e"));
    }

    #[test]
    fn test_fold_versions() {
        assert_eq!(sequence_option_fold(vec![Some(1), Some(2)]), Some(vec![1, 2]));
        assert_eq!(sequence_option_fold(vec![Some(1), None]), None);
        assert_eq!(sequence_result_fold::<i32, String>(vec![Ok(1), Ok(2)]), Ok(vec![1, 2]));
    }

    #[test]
    fn test_practical_parse() {
        let parsed: Option<Vec<i32>> = vec!["1", "2", "3"]
            .iter()
            .map(|s| s.parse().ok())
            .collect();
        assert_eq!(parsed, Some(vec![1, 2, 3]));

        let parsed2: Option<Vec<i32>> = vec!["1", "bad", "3"]
            .iter()
            .map(|s| s.parse().ok())
            .collect();
        assert_eq!(parsed2, None);
    }
}

(* Example 066: Sequence Monadic *)
(* Turn a list of monadic values into a monadic list *)

(* Approach 1: sequence for Option *)
let sequence_option xs =
  List.fold_right (fun x acc ->
    match x, acc with
    | Some y, Some ys -> Some (y :: ys)
    | _ -> None
  ) xs (Some [])

(* Approach 2: sequence for Result *)
let sequence_result xs =
  List.fold_right (fun x acc ->
    match x, acc with
    | Ok y, Ok ys -> Ok (y :: ys)
    | Error e, _ | _, Error e -> Error e
  ) xs (Ok [])

(* Approach 3: Generic sequence via bind *)
let sequence_generic ~bind ~return_ xs =
  List.fold_right (fun mx acc ->
    bind mx (fun x ->
    bind acc (fun xs ->
    return_ (x :: xs)))
  ) xs (return_ [])

let opt_bind m f = match m with None -> None | Some x -> f x
let opt_return x = Some x

let res_bind m f = match m with Error e -> Error e | Ok x -> f x
let res_return x = Ok x

let () =
  (* Option sequence *)
  assert (sequence_option [Some 1; Some 2; Some 3] = Some [1; 2; 3]);
  assert (sequence_option [Some 1; None; Some 3] = None);
  assert (sequence_option [] = Some []);

  (* Result sequence *)
  assert (sequence_result [Ok 1; Ok 2; Ok 3] = Ok [1; 2; 3]);
  assert (sequence_result [Ok 1; Error "e"; Ok 3] = Error "e");

  (* Generic sequence *)
  let opt_seq = sequence_generic ~bind:opt_bind ~return_:opt_return in
  assert (opt_seq [Some 1; Some 2] = Some [1; 2]);
  assert (opt_seq [Some 1; None] = None);

  let res_seq = sequence_generic ~bind:res_bind ~return_:res_return in
  assert (res_seq [Ok 1; Ok 2] = Ok [1; 2]);

  Printf.printf "✓ All tests passed\n"

📊 Detailed Comparison

Comparison: Sequence Monadic

Option Sequence

OCaml:

🐪 Show OCaml equivalent

let sequence_option xs =
List.fold_right (fun x acc ->
 match x, acc with
 | Some y, Some ys -> Some (y :: ys)
 | _ -> None
) xs (Some [])

Rust:

fn sequence_option<T>(xs: Vec<Option<T>>) -> Option<Vec<T>> {
 xs.into_iter().collect()  // That's it!
}

Generic Sequence