Functor Category — Functors as Objects, Natural Transformations as Morphisms

// Natural transformation: slice → Option, borrows in/out (no allocation)
pub fn list_to_option<T>(list: &[T]) -> Option<&T> {
    list.first()
}

// Natural transformation: Option → Vec
pub fn option_to_list<T>(opt: Option<T>) -> Vec<T> {
    match opt {
        None => vec![],
        Some(x) => vec![x],
    }
}

(* Functor interface using module signature — HKT via type 'a t *)
module type FUNCTOR = sig
  type 'a t
  val map : ('a -> 'b) -> 'a t -> 'b t
end

(* Natural transformation: list → option (take head) *)
let list_to_option : 'a list -> 'a option = function
  | []     -> None
  | x :: _ -> Some x

(* Naturality: map f . nat = nat . map f *)
let check_naturality () =
  let f x = x * 2 in
  let lst = [1; 2; 3] in
  let lhs = list_to_option (List.map f lst) in
  let rhs = Option.map f (list_to_option lst) in
  assert (lhs = rhs)

#![allow(clippy::all)]
// In a functor category, objects are functors and morphisms are natural transformations.
// Rust models functors as generic types with map-like operations (Vec, Option).
// Natural transformations are polymorphic functions between two such types.

// ---------------------------------------------------------------------------
// Natural transformation: Vec → Option  (take the head element)
// ---------------------------------------------------------------------------

/// Solution 1: Idiomatic Rust — delegates to `slice::first`, borrows in/out.
pub fn list_to_option<T>(list: &[T]) -> Option<&T> {
    list.first()
}

/// Solution 2: Functional/recursive style, mirroring OCaml pattern match.
pub fn list_to_option_rec<T>(list: &[T]) -> Option<&T> {
    match list {
        [] => None,
        [head, ..] => Some(head),
    }
}

// ---------------------------------------------------------------------------
// Natural transformation: Option → Vec  (wrap or empty)
// ---------------------------------------------------------------------------

/// Both idiomatic and functional: a single match is already the Rust idiom.
pub fn option_to_list<T>(opt: Option<T>) -> Vec<T> {
    match opt {
        None => vec![],
        Some(x) => vec![x],
    }
}

// ---------------------------------------------------------------------------
// Naturality condition
//
// A natural transformation η : F → G must commute with fmap:
//   G.map(f) ∘ η  =  η ∘ F.map(f)
//
// Concretely for list_to_option:
//   list_to_option(list.map(f))  ==  Option::map(f)(list_to_option(list))
// ---------------------------------------------------------------------------

/// Returns `true` when the naturality square commutes for `list_to_option` and `f`.
pub fn naturality_holds<T, U, F>(list: &[T], f: F) -> bool
where
    T: Clone,
    U: PartialEq,
    F: Fn(T) -> U,
{
    // lhs: apply f to every element, then take the head
    let mapped: Vec<U> = list.iter().cloned().map(&f).collect();
    let lhs = mapped.first();

    // rhs: take the head first, then apply f
    let rhs = list.first().cloned().map(f);

    // compare Option<&U>  vs  Option<&U>  (rhs.as_ref() gives &U)
    lhs == rhs.as_ref()
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

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

    #[test]
    fn test_list_to_option_empty() {
        assert_eq!(list_to_option::<i32>(&[]), None);
    }

    #[test]
    fn test_list_to_option_single() {
        assert_eq!(list_to_option(&[42]), Some(&42));
    }

    #[test]
    fn test_list_to_option_multiple() {
        assert_eq!(list_to_option(&[1, 2, 3]), Some(&1));
    }

    #[test]
    fn test_list_to_option_rec_matches_idiomatic() {
        let cases: &[&[i32]] = &[&[], &[1], &[1, 2, 3]];
        for &list in cases {
            assert_eq!(list_to_option(list), list_to_option_rec(list));
        }
    }

    #[test]
    fn test_option_to_list_none() {
        assert_eq!(option_to_list::<i32>(None), vec![]);
    }

    #[test]
    fn test_option_to_list_some() {
        assert_eq!(option_to_list(Some(42)), vec![42]);
    }

    #[test]
    fn test_naturality_nonempty() {
        // list_to_option([2,4,6]) == map(*2)(list_to_option([1,2,3]))
        assert!(naturality_holds(&[1i32, 2, 3], |x| x * 2));
    }

    #[test]
    fn test_naturality_empty() {
        // Both sides are None — naturality trivially holds
        assert!(naturality_holds::<i32, i32, _>(&[], |x| x * 2));
    }
}

(* In a functor category, objects are functors and morphisms are
   natural transformations. In OCaml, functors + polymorphic functions. *)

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

(* Natural transformation: polymorphic function between two functors *)
(* nat_trans F G = forall a. F.t a -> G.t a *)

module ListF : FUNCTOR = struct
  type 'a t = 'a list
  let map = List.map
end

module OptionF : FUNCTOR = struct
  type 'a t = 'a option
  let map = Option.map
end

(* Natural transformation: list -> option (head) *)
let list_to_option : 'a list -> 'a option = function
  | []     -> None
  | x :: _ -> Some x

(* Naturality condition: map f . nat = nat . map f *)
let check_naturality () =
  let f x = x * 2 in
  let lst = [1; 2; 3] in
  (* list_to_option (map f lst) = map f (list_to_option lst) *)
  let lhs = list_to_option (List.map f lst) in
  let rhs = Option.map f (list_to_option lst) in
  assert (lhs = rhs);
  Printf.printf "Naturality: list_to_option is a natural transformation\n"

(* Another nat trans: option -> list *)
let option_to_list : 'a option -> 'a list = function
  | None   -> []
  | Some x -> [x]

let () =
  check_naturality ();
  Printf.printf "list_to_option [1;2;3] = %s\n"
    (match list_to_option [1;2;3] with Some n -> string_of_int n | None -> "None");
  Printf.printf "option_to_list (Some 42) = [%s]\n"
    (option_to_list (Some 42) |> List.map string_of_int |> String.concat ";")