074: Bifunctor — Mapping Over Two Type Parameters

Difficulty: Intermediate Level: Intermediate When your container holds two different things, a Bifunctor lets you transform either one — or both — independently.

The Problem This Solves

`Result<T, E>` holds two types: a success value `T` and an error value `E`. You often need to transform just one of them:

// I have Result<i32, String> and want Result<i64, String>
// This works — map transforms the Ok side:
let r: Result<i64, String> = result.map(|n| n as i64);

// But what if I want to transform just the error side?
// There's map_err for that. But what about a custom Either type?
// You'd have to match manually every single time.

Once you build your own `Either<A, B>` type (useful for representing one-of-two outcomes), you immediately hit this: you want to transform the `Left` side, or the `Right` side, or both at once. Without a systematic approach, you write a `map_left`, a `map_right`, and forget they should compose nicely together. A Bifunctor is simply a container with two type slots, both of which support independent mapping. It's a Functor, but for pairs of types instead of single types. The concept exists to solve exactly that pain: "I have two things inside a container and I want to transform either one without touching the other."

The Intuition

Imagine a shipping label with two fields: sender address and recipient address. You want to:

Update just the recipient (forwarding a package)
Update just the sender (returning a package)
Update both (reshipping between two new parties)

A Bifunctor is that label: a container with two slots, where you can independently transform either slot, or both at once with a single operation. In code:

Either::Left(42) --bimap(double, uppercase)--> Either::Left(84)
Either::Right("hello") --bimap(double, uppercase)--> Either::Right("HELLO")

`bimap` takes two functions: one for the `Left` slot and one for the `Right` slot. It applies the appropriate function based on which variant is active. Neither function is called if its slot isn't populated. The two simpler operations fall out naturally:

`map_left(f)` = `bimap(f, identity)` — transform only the Left, leave Right as-is
`map_right(g)` = `bimap(identity, g)` — transform only the Right, leave Left as-is

How It Works in Rust

Step 1 — The Either type (the canonical Bifunctor):

#[derive(Debug, Clone, PartialEq)]
enum Either<A, B> {
 Left(A),
 Right(B),
}

Step 2 — bimap: transform both slots with two functions:

impl<A, B> Either<A, B> {
 fn bimap<C, D, F: FnOnce(A) -> C, G: FnOnce(B) -> D>(
     self, f: F, g: G,
 ) -> Either<C, D> {
     match self {
         Either::Left(a)  => Either::Left(f(a)),   // apply f to Left
         Either::Right(b) => Either::Right(g(b)),  // apply g to Right
     }
 }
}

Step 3 — map_left and map_right as special cases:

fn map_left<C, F: FnOnce(A) -> C>(self, f: F) -> Either<C, B> {
 self.bimap(f, |b| b)   // identity for the Right slot
}

fn map_right<D, G: FnOnce(B) -> D>(self, g: G) -> Either<A, D> {
 self.bimap(|a| a, g)   // identity for the Left slot
}

Usage:

let e: Either<i32, &str> = Either::Left(42);
let r = e.bimap(|n| n * 2, |s| s.to_uppercase());
// Either::Left(84) — only f was called; g was never invoked

Step 4 — Bifunctor for pairs (both slots always populated):

struct Pair<A, B>(A, B);

impl<A, B> Pair<A, B> {
 fn bimap<C, D, F: FnOnce(A)->C, G: FnOnce(B)->D>(self, f: F, g: G) -> Pair<C, D> {
     Pair(f(self.0), g(self.1))  // both f and g always called
 }
}

let pair = Pair("hello", 42_i32);
let result = pair.bimap(|s: &str| s.len(), |n| n * 2);
// Pair(5, 84)

Bifunctor laws (what `bimap` must satisfy): 1. `bimap(id, id)` == identity — doing nothing does nothing 2. `bimap(f∘g, h∘k)` == `bimap(f,h).bimap(g,k)` — order of composition doesn't matter

What This Unlocks

Independent transformation of either side. You can evolve error types or success types in `Result`-like structures without touching the other side. This is exactly how `Result::map` and `Result::map_err` work — they're the `map_right` and `map_left` of `Result`'s Bifunctor.
Symmetric error handling. `Either<AppError, Value>` lets you transform errors independently of values. Many Rust error-handling libraries (like `either` crate) are built on this pattern.
Generic algorithms over two-slot containers. Write functions that operate on any Bifunctor regardless of the concrete type.

Real codebases where this pattern appears: `Result<T,E>` in the standard library (which is a Bifunctor — `map` and `map_err` are its `map_right` and `map_left`), the `either` crate, parser combinators that separate parse errors from semantic errors, and RPC systems that tag responses as success or failure.

Key Differences

Concept	OCaml	Rust
Either type	`type ('a,'b) either = Left of 'a \	Right of 'b`	`enum Either<A,B> { Left(A), Right(B) }`
bimap signature	`val bimap : ('a->'c) -> ('b->'d) -> ('a,'b) either -> ('c,'d) either`	`fn bimap<C,D,F,G>(self, f:F, g:G) -> Either<C,D>`
Calling style	`bimap f g e` (curried, function-first)	`e.bimap(f, g)` (method syntax)
Pair / tuple	`(a, b)` — built-in tuple, no newtype needed	`struct Pair<A,B>(A,B)` — newtype to add `bimap` method
`Result` as Bifunctor	`Result.map` + `Result.map_error`	`Result::map` + `Result::map_err`
Generic Bifunctor trait	Module signature with `type ('a,'b) t`	Trait with GATs: `type Target<C,D>`
Identity in bimap	`fun x -> x`	`\	x\	x`

// Bifunctor: a type with two type parameters, each mappable independently.
// bimap f g applies f to the "left" and g to the "right".
//
// Bifunctor laws:
//   bimap id id = id
//   bimap (f . g) (h . k) = bimap f h . bimap g k

// ── Bifunctor trait ──────────────────────────────────────────────────────────

pub trait Bifunctor<A, B> {
    type Target<C, D>;

    fn bimap<C, D, F: FnOnce(A) -> C, G: FnOnce(B) -> D>(
        self,
        f: F,
        g: G,
    ) -> Self::Target<C, D>;

    fn map_left<C, F: FnOnce(A) -> C>(self, f: F) -> Self::Target<C, B>
    where
        Self: Sized,
        B: Clone + 'static,
    {
        // Default impl using bimap — concrete types override as needed
        self.bimap(f, |b| b)
    }

    fn map_right<D, G: FnOnce(B) -> D>(self, g: G) -> Self::Target<A, D>
    where
        Self: Sized,
        A: Clone + 'static,
    {
        self.bimap(|a| a, g)
    }
}

// ── Either type ─────────────────────────────────────────────────────────────

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Either<A, B> {
    Left(A),
    Right(B),
}

impl<A, B> Either<A, B> {
    pub fn bimap<C, D, F: FnOnce(A) -> C, G: FnOnce(B) -> D>(
        self,
        f: F,
        g: G,
    ) -> Either<C, D> {
        match self {
            Either::Left(a) => Either::Left(f(a)),
            Either::Right(b) => Either::Right(g(b)),
        }
    }

    pub fn map_left<C, F: FnOnce(A) -> C>(self, f: F) -> Either<C, B> {
        self.bimap(f, |b| b)
    }

    pub fn map_right<D, G: FnOnce(B) -> D>(self, g: G) -> Either<A, D> {
        self.bimap(|a| a, g)
    }

    pub fn is_left(&self) -> bool {
        matches!(self, Either::Left(_))
    }

    pub fn is_right(&self) -> bool {
        matches!(self, Either::Right(_))
    }
}

// ── Pair/tuple as a bifunctor ────────────────────────────────────────────────

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Pair<A, B>(pub A, pub B);

impl<A, B> Pair<A, B> {
    pub fn bimap<C, D, F: FnOnce(A) -> C, G: FnOnce(B) -> D>(
        self,
        f: F,
        g: G,
    ) -> Pair<C, D> {
        Pair(f(self.0), g(self.1))
    }

    pub fn map_fst<C, F: FnOnce(A) -> C>(self, f: F) -> Pair<C, B> {
        self.bimap(f, |b| b)
    }

    pub fn map_snd<D, G: FnOnce(B) -> D>(self, g: G) -> Pair<A, D> {
        self.bimap(|a| a, g)
    }
}

fn main() {
    let e1: Either<i32, String> = Either::Left(42);
    let e2: Either<i32, String> = Either::Right("hello".to_string());

    // bimap: transform both sides
    let r1 = e1.bimap(|n| n * 2, |s: String| s.to_uppercase());
    let r2 = e2.bimap(|n| n * 2, |s: String| s.to_uppercase());

    match r1 {
        Either::Left(84) => println!("bimap Left: 84"),
        _ => panic!("unexpected"),
    }
    match r2 {
        Either::Right(ref s) if s == "HELLO" => println!("bimap Right: HELLO"),
        _ => panic!("unexpected"),
    }

    // map_left / map_right independently
    let e3: Either<i32, String> = Either::Left(42);
    let e4: Either<i32, String> = Either::Right("hello".to_string());

    let r3 = e3.map_left(|n| n + 1);
    let r4 = e4.map_right(|s| s.len());

    match r3 {
        Either::Left(43) => println!("map_left: 43"),
        _ => panic!("unexpected"),
    }
    match r4 {
        Either::Right(5) => println!("map_right: 5"),
        _ => panic!("unexpected"),
    }

    // Bifunctor identity law: bimap id id = id
    let e5: Either<i32, &str> = Either::Left(99);
    let identity_result = e5.clone().bimap(|x| x, |x| x);
    assert_eq!(identity_result, e5);
    println!("bifunctor identity law holds");

    // Pair bifunctor
    let pair = Pair("hello", 42_i32);
    let mapped = pair.bimap(|s: &str| s.len(), |n| n * 2);
    println!("Pair bimap: ({}, {})", mapped.0, mapped.1);
}

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

    #[test]
    fn test_bimap_left() {
        let e: Either<i32, &str> = Either::Left(5);
        let r = e.bimap(|n| n * 2, |s: &str| s.len());
        assert_eq!(r, Either::Left(10));
    }

    #[test]
    fn test_bimap_right() {
        let e: Either<i32, &str> = Either::Right("hello");
        let r = e.bimap(|n| n * 2, |s: &str| s.len());
        assert_eq!(r, Either::Right(5));
    }

    #[test]
    fn test_bimap_identity_law() {
        let e: Either<i32, &str> = Either::Left(42);
        let r = e.clone().bimap(|x| x, |x| x);
        assert_eq!(r, e);
    }

    #[test]
    fn test_map_left() {
        let e: Either<i32, &str> = Either::Left(10);
        assert_eq!(e.map_left(|n| n + 5), Either::Left(15));
    }

    #[test]
    fn test_map_right() {
        let e: Either<i32, &str> = Either::Right("rust");
        assert_eq!(e.map_right(|s| s.len()), Either::Right(4));
    }

    #[test]
    fn test_pair_bifunctor() {
        let p = Pair(3_i32, "hi");
        let r = p.bimap(|n| n * 10, |s: &str| s.len());
        assert_eq!(r, Pair(30, 2));
    }

    #[test]
    fn test_bimap_composition_law() {
        // bimap (f . g) (h . k) = bimap f h . bimap g k
        let e: Either<i32, i32> = Either::Left(3);
        let f = |x: i32| x + 1;
        let g = |x: i32| x * 2;
        let h = |x: i32| x - 1;
        let k = |x: i32| x + 10;

        let lhs = e.clone().bimap(|x| f(g(x)), |x| h(k(x)));
        let rhs = e.bimap(g, k).bimap(f, h);
        assert_eq!(lhs, rhs);
    }
}

(* Bifunctor: a type with two type parameters, each mappable independently.
   bimap f g applies f to the "left" and g to the "right". *)

(* Either type as a canonical bifunctor *)
type ('a, 'b) either = Left of 'a | Right of 'b

let bimap f g = function
  | Left  a -> Left  (f a)
  | Right b -> Right (g b)

let map_left  f e = bimap f (fun x -> x) e
let map_right g e = bimap (fun x -> x) g e

(* Bifunctor laws:
   bimap id id = id
   bimap (f . g) (h . k) = bimap f h . bimap g k *)

let () =
  let e1 : (int, string) either = Left 42 in
  let e2 : (int, string) either = Right "hello" in

  (* bimap: transform both sides *)
  let r1 = bimap (fun n -> n * 2) String.uppercase_ascii e1 in
  let r2 = bimap (fun n -> n * 2) String.uppercase_ascii e2 in
  (match r1 with Left 84 -> Printf.printf "bimap Left: 84\n" | _ -> assert false);
  (match r2 with Right "HELLO" -> Printf.printf "bimap Right: HELLO\n" | _ -> assert false);

  (* map_left / map_right independently *)
  let r3 = map_left (fun n -> n + 1) e1 in
  let r4 = map_right String.length e2 in
  (match r3 with Left 43 -> Printf.printf "map_left: 43\n" | _ -> assert false);
  (match r4 with Right 5  -> Printf.printf "map_right: 5\n"  | _ -> assert false)