056: Fold Right

Difficulty: 2 Level: Beginner Process a list from right to left by recursing to the end, then combining on the way back.

The Problem This Solves

Some operations are naturally right-associative. String concatenation from a list — `"a" ++ ("b" ++ ("c" ++ ""))` — is right-fold. Building a new list with the same order — prepending each element as you unwind — is right-fold. Any operation where the last element's result feeds into the second-to-last, and so on, needs `fold_right`. `fold_left` accumulates left-to-right in a single pass. `fold_right` recurses to the end first, then combines on the way back. The two folds aren't interchangeable: `fold_right (+) [1;2;3] 0` gives the same answer for addition (commutative), but `fold_right (^) ["a";"b";"c"] ""` gives `"abc"` while a left fold gives `"cba"`. The trade-off is stack space: right fold is not tail-recursive. Each recursive call stays on the stack until the base case is reached.

The Intuition

Think of `fold_right f [a, b, c] init` as replacing every comma with `f` and the end with `init`:

[a, b, c]  →  f(a, f(b, f(c, init)))

The innermost call (`f(c, init)`) resolves first, its result flows outward into `f(b, ...)`, then into `f(a, ...)`. Right to left, outside-in. For string concatenation: `f(a, f(b, f(c, ""))) = a ++ (b ++ (c ++ "")) = "abc"`. The right-fold structure produces the correct associativity automatically.

How It Works in Rust

// Recursive right fold — mirrors OCaml's fold_right exactly
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)),
     //                          ^-- recurse first, combine after
 }
}

// Usage:
fold_right(|x, acc| x + acc, &[1,2,3], 0)             // → 6
fold_right(|s, acc: String| format!("{s}{acc}"), &["a","b","c"], String::new()) // → "abc"

// Rust's built-in right fold on slices:
xs.iter().rfold(init, |acc, &x| f(x, acc))
// rfold iterates backwards using index — no stack growth

The `Copy` bound on `f` lets the closure be copied into each recursive call rather than moved. The key structural difference from `fold_left`: the recursive call is inside `f(...)`, not in tail position, so the stack frame stays alive until the inner call returns.

What This Unlocks

Right-associative operations — string building, list copying, any operation where order of association matters.
Understanding fold duality — knowing when to use `fold_right` vs `fold_left` is a fundamental FP skill.
`rfold` for safety — Rust's `Iterator::rfold` gives right-fold semantics without stack growth, via internal loop.

Key Differences

Concept	OCaml	Rust
Tail recursion	Not tail-recursive (stack-consuming)	Same — `fold_right` is stack-consuming
Safe alternative	`List.fold_right` in stdlib (same risk)	`Iterator::rfold` (loop-based, no stack growth)
Base case	`fold_right f [] init = init`	`[] => init` via slice pattern
Borrowing	Takes owned values from cons-list	Takes `&T` references from slice
`copy` of list	Structural sharing (free)	Allocates new `Vec`

//! # 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::[]");
    }
}

fn main() {
    println!("{:?}", sum_idiomatic(&xs), 15);
    println!("{:?}", sum_functional(&xs), 15);
    println!("{:?}", sum_rfold(&xs), 15);
}

(* 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"

📊 Detailed Comparison

Comparison: fold_right — OCaml vs Rust

OCaml — Direct Recursion

🐪 Show OCaml equivalent

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

1. fold_right is natural in OCaml because lists are recursive — the fold mirrors the data structure 2. Rust prefers iterators — `rfold` achieves the same semantics without stack risk 3. Borrowing changes the API — Rust's fold_right takes `&T` where OCaml takes `'a` 4. Partial application is lightweight in OCaml; Rust uses closures for the same effect 5. The recursive Rust version is primarily pedagogical — in production, use `rfold` or `fold`