056 Intermediate

fold_right — Structural Recursion

Higher-Order Functions

Tutorial Video

Text description (accessibility)

This video demonstrates the "fold_right — Structural Recursion" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Higher-Order Functions. Implement `fold_right`, the fundamental higher-order function that processes a list from right to left by replacing each cons (`::`) with an operator and `[]` with an initial value: `fold_right f [a; b; c] init = f a (f b (f c init))`. Key difference from OCaml: 1. **Stack safety:** OCaml's fold_right can stack overflow on large lists; Rust's `rfold` uses an internal loop (no stack growth)

Tutorial

The Problem

Implement fold_right, the fundamental higher-order function that processes a list from right to left by replacing each cons (::) with an operator and [] with an initial value: fold_right f [a; b; c] init = f a (f b (f c init)).

🎯 Learning Outcomes

• Understand fold_right as "replacing constructors" in a list

• See why fold_right is not tail-recursive (builds up stack frames)

• Compare OCaml's natural recursion with Rust's iterator-based rfold

• Use partial application to create specialized functions from fold

• Recognize when right-fold ordering matters (e.g., string concatenation, list copy)

🦀 The Rust Way

Rust offers three approaches:

Idiomatic: iter().sum(), iter().product(), to_vec() — specialized methods

Functional: Explicit recursive fold_right over slices using [head, tail @ ..] patterns

rfold: iter().rfold() on DoubleEndedIterator — Rust's built-in right fold

Code Example

pub fn sum_idiomatic(xs: &[i64]) -> i64 {
    xs.iter().sum()
}

pub fn product_idiomatic(xs: &[i64]) -> i64 {
    xs.iter().product()
}

pub fn concat_idiomatic(xs: &[&str]) -> String {
    xs.iter().copied().collect()
}

let rec fold_right f lst acc =
  match lst with
  | []     -> acc
  | h :: t -> f h (fold_right f t acc)

let sum  lst = fold_right ( + ) lst 0
let prod lst = fold_right ( * ) lst 1
let cat  lst = fold_right ( ^ ) lst ""

Key Differences

Stack safety: OCaml's fold_right can stack overflow on large lists; Rust's rfold uses an internal loop (no stack growth)

Borrowing: Rust's fold takes &T references from slices; OCaml's takes owned values from the cons-list

Partial application: OCaml creates specialized functions via currying (let sum = fold_right (+) lst 0); Rust uses closures

No cons-list: Rust slices are contiguous memory — rfold iterates backwards by index, not by recursive structure

Copy semantics: copy in OCaml is free (structural sharing); in Rust it allocates a new Vec

Right vs left fold direction: fold_right f [a; b; c] init = f a (f b (f c init)) — processes right-to-left. fold_left f init [a; b; c] = f (f (f init a) b) c — processes left-to-right. For non-associative operations, the order matters.

Stack usage: fold_right on a linked list is not tail-recursive — it builds a chain of pending f calls on the stack. For large lists, it risks stack overflow. fold_left with an accumulator is O(1) stack.

**Rust's fold is fold_left:** iter.fold(init, |acc, x| f(acc, x)) applies f left-to-right — it is fold_left. Rust has no built-in fold_right because right-fold on iterators requires buffering all elements first.

**rfold for right fold:** iter.rev().fold(init, |acc, x| ...) approximates right-fold on finite iterators. Alternatively, use iter.collect::<Vec<_>>().into_iter().rfold(init, f) if true right-fold semantics are needed.

OCaml Approach

OCaml's fold_right recurses to the end of the list first, then applies f as it unwinds. This matches the list's recursive structure perfectly — it's the most natural recursion over a cons-list.

Full Source

#![allow(clippy::all)]
//! # fold_right — Structural Recursion
//!
//! OCaml's `fold_right` processes a list from right to left:
//!   fold_right f [a; b; c] init = f a (f b (f c init))
//!
//! In Rust, the closest stdlib equivalent is `Iterator::rfold` (on
//! double-ended iterators) or simply `fold` with reversed logic.

// ---------------------------------------------------------------------------
// Approach A: Idiomatic Rust — use iterator combinators
// ---------------------------------------------------------------------------

/// Sum via `iter().sum()`.
pub fn sum_idiomatic(xs: &[i64]) -> i64 {
    xs.iter().sum()
}

/// Product via `iter().product()`.
pub fn product_idiomatic(xs: &[i64]) -> i64 {
    xs.iter().product()
}

/// Concatenation via `iter().collect()` (or `join`).
pub fn concat_idiomatic(xs: &[&str]) -> String {
    // collect on an iterator of &str directly concatenates
    xs.iter().copied().collect()
}

/// Copy a slice into a Vec — trivially `to_vec()`.
pub fn copy_idiomatic(xs: &[i64]) -> Vec<i64> {
    xs.to_vec()
}

// ---------------------------------------------------------------------------
// Approach B: Functional / explicit fold_right (recursive)
// ---------------------------------------------------------------------------

/// A generic right fold, mirroring OCaml's `fold_right`.
///
/// Because Rust doesn't have a cons-list with O(1) pattern matching,
/// we recurse over a slice index. This is *not* tail-recursive — it
/// mirrors OCaml's stack-consuming `fold_right` faithfully.
pub fn fold_right<T, A>(f: impl Fn(&T, A) -> A + Copy, xs: &[T], init: A) -> A {
    // We take `&T` rather than `T` because Rust slices lend references.
    match xs {
        [] => init,
        [head, tail @ ..] => f(head, fold_right(f, tail, init)),
    }
}

pub fn sum_functional(xs: &[i64]) -> i64 {
    fold_right(|x, acc| x + acc, xs, 0)
}

pub fn product_functional(xs: &[i64]) -> i64 {
    fold_right(|x, acc| x * acc, xs, 1)
}

pub fn concat_functional(xs: &[&str]) -> String {
    fold_right(|s, acc: String| format!("{s}{acc}"), xs, String::new())
}

pub fn copy_functional(xs: &[i64]) -> Vec<i64> {
    // Mirrors OCaml: fold_right (fun h t -> h :: t) lst []
    fold_right(
        |&x, mut acc: Vec<i64>| {
            acc.insert(0, x); // prepend — O(n) per call, faithful to OCaml semantics
            acc
        },
        xs,
        Vec::new(),
    )
}

// ---------------------------------------------------------------------------
// Approach C: rfold — Rust's built-in right fold on DoubleEndedIterator
// ---------------------------------------------------------------------------

pub fn sum_rfold(xs: &[i64]) -> i64 {
    xs.iter().rfold(0, |acc, &x| x + acc)
}

pub fn product_rfold(xs: &[i64]) -> i64 {
    xs.iter().rfold(1, |acc, &x| x * acc)
}

pub fn concat_rfold(xs: &[&str]) -> String {
    // rfold processes right-to-left, accumulating left-to-right
    xs.iter()
        .rfold(String::new(), |acc, &s| format!("{s}{acc}"))
}

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

    #[test]
    fn test_sum_basic() {
        let xs = [1, 2, 3, 4, 5];
        assert_eq!(sum_idiomatic(&xs), 15);
        assert_eq!(sum_functional(&xs), 15);
        assert_eq!(sum_rfold(&xs), 15);
    }

    #[test]
    fn test_sum_empty() {
        let xs: &[i64] = &[];
        assert_eq!(sum_idiomatic(xs), 0);
        assert_eq!(sum_functional(xs), 0);
        assert_eq!(sum_rfold(xs), 0);
    }

    #[test]
    fn test_product_single() {
        let xs = [42];
        assert_eq!(product_idiomatic(&xs), 42);
        assert_eq!(product_functional(&xs), 42);
        assert_eq!(product_rfold(&xs), 42);
    }

    #[test]
    fn test_product_basic() {
        let xs = [1, 2, 3, 4, 5];
        assert_eq!(product_idiomatic(&xs), 120);
        assert_eq!(product_functional(&xs), 120);
        assert_eq!(product_rfold(&xs), 120);
    }

    #[test]
    fn test_concat() {
        let xs = ["a", "b", "c"];
        assert_eq!(concat_idiomatic(&xs), "abc");
        assert_eq!(concat_functional(&xs), "abc");
        assert_eq!(concat_rfold(&xs), "abc");
    }

    #[test]
    fn test_concat_empty() {
        let xs: &[&str] = &[];
        assert_eq!(concat_idiomatic(xs), "");
        assert_eq!(concat_functional(xs), "");
        assert_eq!(concat_rfold(xs), "");
    }

    #[test]
    fn test_copy() {
        let xs = [10, 20, 30];
        assert_eq!(copy_idiomatic(&xs), vec![10, 20, 30]);
        assert_eq!(copy_functional(&xs), vec![10, 20, 30]);
    }

    #[test]
    fn test_fold_right_generic() {
        // Use fold_right to build a string representation
        let xs = [1, 2, 3];
        let result = fold_right(
            |x, acc: String| format!("{x}::{acc}"),
            &xs,
            "[]".to_string(),
        );
        assert_eq!(result, "1::2::3::[]");
    }
}

(* fold_right — Structural Recursion *)

(* Implementation 1: Direct recursive fold_right *)
let rec fold_right f lst acc =
  match lst with
  | []     -> acc
  | h :: t -> f h (fold_right f t acc)

(* Implementation 2: Using List.fold_right from stdlib *)
let fold_right_stdlib f lst acc = List.fold_right f lst acc

(* Classic uses *)
let sum  lst = fold_right ( + ) lst 0
let prod lst = fold_right ( * ) lst 1
let cat  lst = fold_right ( ^ ) lst ""
let copy lst = fold_right (fun h t -> h :: t) lst []

(* Tests *)
let () =
  assert (sum [1; 2; 3; 4; 5] = 15);
  assert (prod [1; 2; 3; 4; 5] = 120);
  assert (cat ["a"; "b"; "c"] = "abc");
  assert (copy [1; 2; 3] = [1; 2; 3]);
  assert (sum [] = 0);
  assert (prod [] = 1);
  assert (cat [] = "");
  Printf.printf "All fold_right tests passed!\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_sum_basic() {
        let xs = [1, 2, 3, 4, 5];
        assert_eq!(sum_idiomatic(&xs), 15);
        assert_eq!(sum_functional(&xs), 15);
        assert_eq!(sum_rfold(&xs), 15);
    }

    #[test]
    fn test_sum_empty() {
        let xs: &[i64] = &[];
        assert_eq!(sum_idiomatic(xs), 0);
        assert_eq!(sum_functional(xs), 0);
        assert_eq!(sum_rfold(xs), 0);
    }

    #[test]
    fn test_product_single() {
        let xs = [42];
        assert_eq!(product_idiomatic(&xs), 42);
        assert_eq!(product_functional(&xs), 42);
        assert_eq!(product_rfold(&xs), 42);
    }

    #[test]
    fn test_product_basic() {
        let xs = [1, 2, 3, 4, 5];
        assert_eq!(product_idiomatic(&xs), 120);
        assert_eq!(product_functional(&xs), 120);
        assert_eq!(product_rfold(&xs), 120);
    }

    #[test]
    fn test_concat() {
        let xs = ["a", "b", "c"];
        assert_eq!(concat_idiomatic(&xs), "abc");
        assert_eq!(concat_functional(&xs), "abc");
        assert_eq!(concat_rfold(&xs), "abc");
    }

    #[test]
    fn test_concat_empty() {
        let xs: &[&str] = &[];
        assert_eq!(concat_idiomatic(xs), "");
        assert_eq!(concat_functional(xs), "");
        assert_eq!(concat_rfold(xs), "");
    }

    #[test]
    fn test_copy() {
        let xs = [10, 20, 30];
        assert_eq!(copy_idiomatic(&xs), vec![10, 20, 30]);
        assert_eq!(copy_functional(&xs), vec![10, 20, 30]);
    }

    #[test]
    fn test_fold_right_generic() {
        // Use fold_right to build a string representation
        let xs = [1, 2, 3];
        let result = fold_right(
            |x, acc: String| format!("{x}::{acc}"),
            &xs,
            "[]".to_string(),
        );
        assert_eq!(result, "1::2::3::[]");
    }
}

Deep Comparison

Comparison: fold_right — OCaml vs Rust

OCaml — Direct Recursion

let rec fold_right f lst acc =
  match lst with
  | []     -> acc
  | h :: t -> f h (fold_right f t acc)

let sum  lst = fold_right ( + ) lst 0
let prod lst = fold_right ( * ) lst 1
let cat  lst = fold_right ( ^ ) lst ""

Rust — Idiomatic (Iterator Methods)

pub fn sum_idiomatic(xs: &[i64]) -> i64 {
    xs.iter().sum()
}

pub fn product_idiomatic(xs: &[i64]) -> i64 {
    xs.iter().product()
}

pub fn concat_idiomatic(xs: &[&str]) -> String {
    xs.iter().copied().collect()
}

Rust — Functional (Recursive fold_right)

pub fn fold_right<T, A>(f: impl Fn(&T, A) -> A + Copy, xs: &[T], init: A) -> A {
    match xs {
        [] => init,
        [head, tail @ ..] => f(head, fold_right(f, tail, init)),
    }
}

pub fn sum_functional(xs: &[i64]) -> i64 {
    fold_right(|x, acc| x + acc, xs, 0)
}

Rust — rfold (Built-in Right Fold)

pub fn sum_rfold(xs: &[i64]) -> i64 {
    xs.iter().rfold(0, |acc, &x| x + acc)
}

Comparison Table

Aspect	OCaml	Rust
Type signature	`('a -> 'b -> 'b) -> 'a list -> 'b -> 'b`	`fn fold_right<T, A>(f: impl Fn(&T, A) -> A, xs: &[T], init: A) -> A`
Data structure	Cons-list (recursive)	Slice (contiguous memory)
Stack safety	Can overflow on large lists	Recursive version can overflow; `rfold` is safe
Element access	Pattern match `h :: t`	Slice pattern `[head, tail @ ..]`
Ownership	Values shared/copied implicitly	`&T` references borrowed from slice
Partial application	`let sum = fold_right (+)`	Closures: `\\|x, acc\\| x + acc`
Built-in	`List.fold_right`	`Iterator::rfold`

Type Signatures Explained

OCaml: val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b

• 'a and 'b are type variables (generics)

• Takes: a function, a list, and an initial accumulator

• The function takes an element and accumulator, returns new accumulator

Rust: fn fold_right<T, A>(f: impl Fn(&T, A) -> A + Copy, xs: &[T], init: A) -> A

• T and A are generic type parameters

• &T: borrows elements (OCaml copies)

• impl Fn: accepts any callable (closure, function pointer)

• + Copy: needed because the closure is called recursively

Takeaways

fold_right is natural in OCaml because lists are recursive — the fold mirrors the data structure

Rust prefers iterators — rfold achieves the same semantics without stack risk

Borrowing changes the API — Rust's fold_right takes &T where OCaml takes 'a

Partial application is lightweight in OCaml; Rust uses closures for the same effect

The recursive Rust version is primarily pedagogical — in production, use rfold or fold

Exercises

Use fold_right to implement map — derive the mapping operation purely from a right fold.

Implement maximum using fold_right that returns the largest element in a non-empty list wrapped in Option.

Use fold_right to implement flatten that concatenates a list of lists into a single list, and compare its stack usage to an iterative approach for large inputs.

List from fold_right: Implement map_via_fold_right<T: Clone, U>(f: impl Fn(&T) -> U, list: &[T]) -> Vec<U> using only fold_right — demonstrate that fold_right can express map.

Natural number arithmetic: Use fold_right to implement sum_right and product_right on a list. Compare the results with fold_left for subtraction to see where the difference in direction matters.

Open Source Repos

functional-rust

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

Rust