865 Expert

Sequence Monadic

Functional Programming

Tutorial

The Problem

sequence converts a collection of monadic values into a monadic collection: Vec<Option<T>> → Option<Vec<T>> or Vec<Result<T,E>> → Result<Vec<T>,E>. While traverse applies a function and sequences simultaneously, sequence is pure rearrangement — it just flips the containers. If you already have a Vec<Option<T>> from mapping over a collection, sequence collects them into Option<Vec<T>>. Rust's Iterator::collect achieves this for Option and Result. The pattern appears when: you have pre-computed individual results and need to combine them, or when working with futures (Vec<Future<T>> → Future<Vec<T>> via futures::future::join_all).

🎯 Learning Outcomes

• Understand sequence as a special case of traverse with the identity function

• Implement sequence_option(Vec<Option<T>>) -> Option<Vec<T>> using collect

• Implement sequence_result(Vec<Result<T,E>>) -> Result<Vec<T>,E> using collect

• Recognize the connection to futures: join_all is sequence for futures

• Distinguish sequence from flat_map: flat_map chains and flattens; sequence flips the container

Code Example

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

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

Key Differences

Aspect	Rust	OCaml
For Option	`collect::<Option<Vec<_>>>()`	`List.fold_right` or `Option.all`
For Result	`collect::<Result<Vec<_>,_>>()`	Same fold pattern
One-liner	Yes (built-in FromIterator)	Requires manual fold
Futures	`futures::join_all`	`Lwt.all`
vs. traverse	`traverse(xs, id)` = sequence	`traverse Fun.id xs`
Short-circuit	First `None`/`Err`	Same

OCaml Approach

OCaml's sequence_option: let sequence xs = List.fold_right (fun x acc -> match x, acc with Some y, Some ys -> Some (y :: ys) | _ -> None) xs (Some []). The sequence_result is analogous with Result. OCaml's Option.all (in some versions) or manual fold implements this. For futures, Lwt.all sequences a list of Lwt promises. The relationship to traverse: sequence xs = traverse Fun.id xs.

Full Source

#![allow(clippy::all)]
// 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"

✓ Tests Rust test suite

#[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);
    }
}

Deep Comparison

Comparison: Sequence Monadic

Option Sequence

OCaml:

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

OCaml:

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_ [])

Rust (no direct equivalent — collect handles it via FromIterator):

// For Option: xs.into_iter().collect::<Option<Vec<_>>>()
// For Result: xs.into_iter().collect::<Result<Vec<_>, _>>()
// The trait system handles the dispatch

Exercises

Implement sequence_option using try_fold (without collect) to understand the manual accumulation.

Show that sequence(map(xs, f)) == traverse(xs, f) with a concrete test.

Implement sequence for a Vec<Vec<T>> — what does flipping the containers mean here? (It's transpose.)

Use sequence to collect results from parallel IO operations: generate Vec<Result<T,E>> then sequence.

Implement unsequence: Option<Vec<T>> -> Vec<Option<T>> and verify it's the inverse when all elements are Some.

Open Source Repos

functional-rust

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

Rust