deep_causality_haft 0.6.0

/*
 * SPDX-License-Identifier: MIT
 * Copyright (c) 2023 - 2026. The DeepCausality Authors and Contributors. All Rights Reserved.
 */
pub mod diagonal;

use crate::{Applicative, Foldable, Functor, HKT};

/// The `Traversable` trait abstracts over data structures that can be "traversed"
/// or "sequenced" in a way that preserves effects. It combines the capabilities
/// of `Functor` (mapping over elements) and `Foldable` (reducing to a single value).
///
/// The core operation of `Traversable` is `sequence`, which takes a structure
/// containing monadic/applicative values (`F<M<A>>`) and "flips" it inside out
/// to produce a monadic/applicative value containing the structure (`M<F<A>>`).
///
/// # Intuition & Analogy
///
/// Imagine you have a list of optional values (`Vec<Option<i32>>`). If any of the
/// options in the list are `None`, you might want the whole operation to fail and
/// just yield `None`. Otherwise, you want `Some` list of integers (`Option<Vec<i32>>`).
/// `sequence` achieves exactly this.
///
/// - `Vec<Option<A>>` -> `Option<Vec<A>>`
/// - `Vec<Result<A, E>>` -> `Result<Vec<A>, E>`
/// - `Option<Result<A, E>>` -> `Result<Option<A>, E>`
///
/// `Traversable` allows you to abstract over these kinds of transformations. It's
/// particularly useful for collecting errors, propagating "empty" states, or
/// accumulating results across collections of effectful computations.
///
/// # Laws (Informal)
///
/// `Traversable` laws are typically expressed in terms of `sequence` and `traverse`
/// (which can be defined in terms of `sequence` and `fmap`, or vice-versa). References:
/// McBride & Paterson, JFP 18(1) 2008 §3; Jaskelioff & Rypacek, MSFP 2012.
///
/// 1.  **Naturality**: for every applicative morphism `phi: M -> N` (preserving `pure` and
///     `apply`), `phi(t.sequence::<M>()) == t.map(phi).sequence::<N>()`
///     (post-processing the result equals pre-processing each element).
/// 2.  **Identity**: `t.map(Identity::new).sequence::<Identity>() == Identity::new(t)`
///     (sequencing at the *Identity applicative* is the identity — note: the weaker phrasing
///     `t.sequence == t.map(id).sequence` is vacuously true by the Functor law and
///     constrains nothing).
/// 3.  **Composition**: `t.map(compose).sequence == t.sequence.sequence`
///     (Sequencing over a composite structure is equivalent to composing the sequenced results).
///
/// Laws are stated for pure functions; a stateful `FnMut` closure voids them.
/// Laws 1–2 are machine-checked in `lean/DeepCausalityFormal/Haft/Traversable.lean`.
///
/// # Type Parameters
///
/// *   `F`: A Higher-Kinded Type (HKT) witness that represents the type constructor
///     of the traversable structure (e.g., `VecWitness`, `OptionWitness`).
///     This `F` must also be a `Functor` and `Foldable`.
pub trait Traversable<F: HKT>: Functor<F> + Foldable<F> {
    /// Transforms a structure containing applicative values (`F::Type<M::Type<A>>`)
    /// into an applicative value containing the structure (`M::Type<F::Type<A>>`).
    ///
    /// This operation essentially "flips" the outer structure with the inner applicative context.
    /// If any inner applicative value is in an "empty" or "failure" state, that state
    /// propagates to the outer applicative result. Otherwise, the values are collected
    /// into the structure wrapped by the applicative context.
    ///
    /// # Arguments
    ///
    /// *   `fa`: An instance of the traversable structure (`F::Type`) where each element
    ///     is wrapped in an applicative context (`M::Type`).
    ///
    /// # Returns
    ///
    /// An instance of the applicative context (`M::Type`) containing the original
    /// traversable structure (`F::Type`) with its elements unwrapped from their
    /// individual applicative contexts.
    ///
    /// # Type Parameters
    ///
    /// *   `A`: The type of the values contained within the innermost applicative context.
    /// *   `M`: The Higher-Kinded Type (HKT) witness for the inner applicative context
    ///     (e.g., `OptionWitness`, `ResultWitness<E>`). This `M` must implement `Applicative`.
    ///
    /// # Requirements
    ///
    /// *   `M: Applicative<M> + HKT`: The inner type `M` must be an `Applicative`
    ///     (which implies it is also a `Functor`) and an `HKT`.
    /// *   `A: Clone`: The values `A` must be clonable, as elements might be copied
    ///     during the sequencing process (e.g., when building a new collection).
    ///
    /// # Examples
    ///
    /// ```rust
    /// use deep_causality_haft::{OptionWitness, ResultWitness, Traversable};
    ///
    /// // Flipping `Option<Result<i32, String>>` into `Result<Option<i32>, String>`.
    /// let ok: Option<Result<i32, String>> = Some(Ok(5));
    /// let flipped: Result<Option<i32>, String> =
    ///     OptionWitness::sequence::<i32, ResultWitness<String>>(ok);
    /// assert_eq!(flipped, Ok(Some(5)));
    ///
    /// // A failure in the inner context propagates outward.
    /// let err: Option<Result<i32, String>> = Some(Err("boom".to_string()));
    /// let flipped_err: Result<Option<i32>, String> =
    ///     OptionWitness::sequence::<i32, ResultWitness<String>>(err);
    /// assert_eq!(flipped_err, Err("boom".to_string()));
    ///
    /// // An empty outer structure succeeds, carrying nothing.
    /// let none: Option<Result<i32, String>> = None;
    /// let flipped_none: Result<Option<i32>, String> =
    ///     OptionWitness::sequence::<i32, ResultWitness<String>>(none);
    /// assert_eq!(flipped_none, Ok(None));
    /// ```
    ///
    /// A sequential carrier flips the same way, one element at a time, and an empty container
    /// succeeds carrying nothing:
    ///
    /// ```rust
    /// use deep_causality_haft::{OptionWitness, Traversable, VecWitness};
    ///
    /// let all: Vec<Option<i32>> = vec![Some(1), Some(2), Some(3)];
    /// assert_eq!(
    ///     VecWitness::sequence::<i32, OptionWitness>(all),
    ///     Some(vec![1, 2, 3])
    /// );
    ///
    /// // One failing element collapses the whole traversal.
    /// let partial: Vec<Option<i32>> = vec![Some(1), None, Some(3)];
    /// assert_eq!(VecWitness::sequence::<i32, OptionWitness>(partial), None);
    /// ```
    ///
    /// `VecWitness`'s fold is quadratic in element clones; see its impl for why.
    fn sequence<A, M>(fa: F::Type<M::Type<A>>) -> M::Type<F::Type<A>>
    where
        M: Applicative<M> + HKT,
        A: Clone;
}