850 Fundamental

Functors Introduction

Functional Programming

Tutorial

The Problem

A functor is a type that supports mapping a function over its contents while preserving structure. Option::map, Result::map, Vec::iter().map(), Iterator::map() are all functors in Rust. The functor pattern abstracts "apply a transformation inside a container" independently of the container type. This enables writing generic algorithms that work over any functor: parse, transform, validate — all without knowing whether the value is present, absent, or in a list. Functors are the foundation of the map → filter → fold pipeline central to functional programming and the Rust iterator protocol.

🎯 Learning Outcomes

• Define a Functor trait: fn map<B, F: Fn(A) -> B>(self, f: F) -> Self<B> (approximated in Rust)

• Implement map for a custom Maybe<T> type mirroring Option<T>

• Verify functor laws: identity (map(id) == id) and composition (map(f∘g) == map(f)∘map(g))

• Recognize how Rust's Option::map, Result::map, and Iterator::map implement the functor concept

• Understand why Rust's type system cannot express the generic Functor<F> trait due to HKT limitations

Code Example

trait Functor {
    type Inner;
    type Mapped<U>: Functor;
    fn fmap<U, F: FnOnce(Self::Inner) -> U>(self, f: F) -> Self::Mapped<U>;
}

module type FUNCTOR = sig
  type 'a t
  val map : ('a -> 'b) -> 'a t -> 'b t
end

Key Differences

Aspect	Rust	OCaml
Generic functor trait	Not expressible (no HKT)	`FUNCTOR` module signature
Per-type map	`impl<T> Maybe<T> { fn map }`	`let map f = function ...`
Law verification	Property tests	Same; or module functors
Identity law	`x.map(\|v\| v) == x`	`map Fun.id x = x`
Composition law	`x.map(\|v\| g(f(v)))`	`map (f >> g) x = map g (map f x)`
stdlib	`Option::map`, `Result::map`	`Option.map`, `List.map`

OCaml Approach

OCaml represents Maybe as type 'a maybe = Nothing | Just of 'a. The map function is let map f = function Nothing -> Nothing | Just x -> Just (f x). OCaml's module system allows a Functor signature: module type FUNCTOR = sig type 'a t; val map : ('a -> 'b) -> 'a t -> 'b t end. This higher-kinded abstraction works in OCaml via parameterized modules. The Option.map in stdlib has the same signature. Law verification: map Fun.id x = x and map (f |> g) x = map g (map f x).

Full Source

#![allow(clippy::all)]
// Example 051: Functors Introduction
// A Functor is a type that supports mapping a function over its contents

// Approach 1: Custom Maybe type with map
#[derive(Debug, PartialEq, Clone)]
enum Maybe<T> {
    Nothing,
    Just(T),
}

impl<T> Maybe<T> {
    fn map<U, F: FnOnce(T) -> U>(self, f: F) -> Maybe<U> {
        match self {
            Maybe::Nothing => Maybe::Nothing,
            Maybe::Just(x) => Maybe::Just(f(x)),
        }
    }

    fn pure(x: T) -> Maybe<T> {
        Maybe::Just(x)
    }
}

// Approach 2: Functor trait (simulating OCaml's module type)
trait Functor {
    type Inner;
    type Mapped<U>: Functor;
    fn fmap<U, F: FnOnce(Self::Inner) -> U>(self, f: F) -> Self::Mapped<U>;
}

#[derive(Debug, PartialEq, Clone)]
struct Box_<T>(T);

impl<T> Functor for Box_<T> {
    type Inner = T;
    type Mapped<U> = Box_<U>;
    fn fmap<U, F: FnOnce(T) -> U>(self, f: F) -> Box_<U> {
        Box_(f(self.0))
    }
}

impl<T> Functor for Maybe<T> {
    type Inner = T;
    type Mapped<U> = Maybe<U>;
    fn fmap<U, F: FnOnce(T) -> U>(self, f: F) -> Maybe<U> {
        self.map(f)
    }
}

// Approach 3: Functor for a tree type
#[derive(Debug, PartialEq, Clone)]
enum Tree<T> {
    Leaf,
    Node(std::boxed::Box<Tree<T>>, T, std::boxed::Box<Tree<T>>),
}

impl<T> Tree<T> {
    fn map<U, F: Fn(&T) -> U>(&self, f: &F) -> Tree<U>
    where
        T: Clone,
    {
        match self {
            Tree::Leaf => Tree::Leaf,
            Tree::Node(l, v, r) => Tree::Node(
                std::boxed::Box::new(l.map(f)),
                f(v),
                std::boxed::Box::new(r.map(f)),
            ),
        }
    }

    fn node(l: Tree<T>, v: T, r: Tree<T>) -> Tree<T> {
        Tree::Node(std::boxed::Box::new(l), v, std::boxed::Box::new(r))
    }
}

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

    #[test]
    fn test_maybe_map_just() {
        assert_eq!(Maybe::Just(5).map(|n| n * 2), Maybe::Just(10));
    }

    #[test]
    fn test_maybe_map_nothing() {
        let n: Maybe<i32> = Maybe::Nothing;
        assert_eq!(n.map(|x| x * 2), Maybe::Nothing);
    }

    #[test]
    fn test_maybe_map_type_change() {
        assert_eq!(Maybe::Just("hello").map(|s| s.len()), Maybe::Just(5));
    }

    #[test]
    fn test_box_functor() {
        let b = Box_(42);
        assert_eq!(b.fmap(|x| x + 1), Box_(43));
    }

    #[test]
    fn test_tree_map() {
        let t = Tree::node(
            Tree::node(Tree::Leaf, 1, Tree::Leaf),
            2,
            Tree::node(Tree::Leaf, 3, Tree::Leaf),
        );
        let expected = Tree::node(
            Tree::node(Tree::Leaf, 10, Tree::Leaf),
            20,
            Tree::node(Tree::Leaf, 30, Tree::Leaf),
        );
        assert_eq!(t.map(&|x: &i32| x * 10), expected);
    }

    #[test]
    fn test_chained_maps() {
        let result = Maybe::Just(3)
            .map(|x| x + 1)
            .map(|x| x * 2)
            .map(|x| x.to_string());
        assert_eq!(result, Maybe::Just("8".to_string()));
    }
}

(* Example 051: Functors Introduction *)
(* A Functor is a type that supports mapping a function over its contents *)

(* Approach 1: Custom Maybe type with map *)
module Maybe = struct
  type 'a t = Nothing | Just of 'a

  let map f = function
    | Nothing -> Nothing
    | Just x -> Just (f x)

  let pure x = Just x

  let to_string f = function
    | Nothing -> "Nothing"
    | Just x -> Printf.sprintf "Just(%s)" (f x)
end

(* Approach 2: Functor signature and implementation for a Box type *)
module type FUNCTOR = sig
  type 'a t
  val map : ('a -> 'b) -> 'a t -> 'b t
end

module Box : FUNCTOR = struct
  type 'a t = Box of 'a
  let map f (Box x) = Box (f x)
end

(* Approach 3: Functor for a tree type *)
type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree

let rec tree_map f = function
  | Leaf -> Leaf
  | Node (l, v, r) -> Node (tree_map f l, f v, tree_map f r)

(* Tests *)
let () =
  (* Test Maybe functor *)
  let x = Maybe.Just 5 in
  let y = Maybe.map (fun n -> n * 2) x in
  assert (y = Maybe.Just 10);

  let n = Maybe.Nothing in
  let m = Maybe.map (fun n -> n * 2) n in
  assert (m = Maybe.Nothing);

  (* Test chained maps *)
  let result = Maybe.map (fun s -> String.length s) (Maybe.Just "hello") in
  assert (result = Maybe.Just 5);

  (* Test tree functor *)
  let t = Node (Node (Leaf, 1, Leaf), 2, Node (Leaf, 3, Leaf)) in
  let t2 = tree_map (fun x -> x * 10) t in
  assert (t2 = Node (Node (Leaf, 10, Leaf), 20, Node (Leaf, 30, Leaf)));

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_maybe_map_just() {
        assert_eq!(Maybe::Just(5).map(|n| n * 2), Maybe::Just(10));
    }

    #[test]
    fn test_maybe_map_nothing() {
        let n: Maybe<i32> = Maybe::Nothing;
        assert_eq!(n.map(|x| x * 2), Maybe::Nothing);
    }

    #[test]
    fn test_maybe_map_type_change() {
        assert_eq!(Maybe::Just("hello").map(|s| s.len()), Maybe::Just(5));
    }

    #[test]
    fn test_box_functor() {
        let b = Box_(42);
        assert_eq!(b.fmap(|x| x + 1), Box_(43));
    }

    #[test]
    fn test_tree_map() {
        let t = Tree::node(
            Tree::node(Tree::Leaf, 1, Tree::Leaf),
            2,
            Tree::node(Tree::Leaf, 3, Tree::Leaf),
        );
        let expected = Tree::node(
            Tree::node(Tree::Leaf, 10, Tree::Leaf),
            20,
            Tree::node(Tree::Leaf, 30, Tree::Leaf),
        );
        assert_eq!(t.map(&|x: &i32| x * 10), expected);
    }

    #[test]
    fn test_chained_maps() {
        let result = Maybe::Just(3)
            .map(|x| x + 1)
            .map(|x| x * 2)
            .map(|x| x.to_string());
        assert_eq!(result, Maybe::Just("8".to_string()));
    }
}

Deep Comparison

Comparison: Functors Introduction

Defining a Functor Interface

OCaml:

module type FUNCTOR = sig
  type 'a t
  val map : ('a -> 'b) -> 'a t -> 'b t
end

Rust:

trait Functor {
    type Inner;
    type Mapped<U>: Functor;
    fn fmap<U, F: FnOnce(Self::Inner) -> U>(self, f: F) -> Self::Mapped<U>;
}

Implementing Map for a Custom Type

OCaml:

type 'a maybe = Nothing | Just of 'a

let map f = function
  | Nothing -> Nothing
  | Just x -> Just (f x)

Rust:

enum Maybe<T> {
    Nothing,
    Just(T),
}

impl<T> Maybe<T> {
    fn map<U, F: FnOnce(T) -> U>(self, f: F) -> Maybe<U> {
        match self {
            Maybe::Nothing => Maybe::Nothing,
            Maybe::Just(x) => Maybe::Just(f(x)),
        }
    }
}

Chaining Maps

OCaml:

Just 3 |> map (fun x -> x + 1) |> map (fun x -> x * 2)
(* = Just 8 *)

Rust:

Maybe::Just(3)
    .map(|x| x + 1)
    .map(|x| x * 2)
// = Just(8)

Tree Functor

OCaml:

type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree

let rec tree_map f = function
  | Leaf -> Leaf
  | Node (l, v, r) -> Node (tree_map f l, f v, tree_map f r)

Rust:

enum Tree<T> {
    Leaf,
    Node(Box<Tree<T>>, T, Box<Tree<T>>),  // Box needed for recursive type
}

impl<T> Tree<T> {
    fn map<U, F: Fn(&T) -> U>(&self, f: &F) -> Tree<U> {
        match self {
            Tree::Leaf => Tree::Leaf,
            Tree::Node(l, v, r) => Tree::Node(
                Box::new(l.map(f)), f(v), Box::new(r.map(f)),
            ),
        }
    }
}

Exercises

Implement map for a custom Tree<T> type that applies the function to every leaf value.

Verify the functor identity law by writing a test: tree.map(|x| x) should equal tree for any tree.

Verify the composition law: tree.map(f).map(g) should equal tree.map(|x| g(f(x))).

Implement a generic function that works over any type with a map method using a trait bound.

Demonstrate that Rust's Iterator::map satisfies the functor laws for lazy sequences.

Open Source Repos

functional-rust

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

Rust