rustica 0.12.0

Rustica is a functional programming library for the Rust language.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

//! Trait implementations for persistent vectors.
//!
//! This module provides implementations of various functional programming traits
//! for [`PersistentVector`], enabling use with the Rustica categorical framework.
//!
//! # Implemented Traits
//!
//! ## Category Theory Traits
//!
//! - [`HKT`]: Higher-kinded type support for generic programming
//! - [`Functor`]: Structure-preserving mapping via `fmap`
//! - [`Foldable`]: Left and right folds over elements
//!
//! ## Algebraic Traits
//!
//! - [`Semigroup`]: Concatenation via `combine`
//! - [`Monoid`]: Empty vector as identity element
//!
//! # Examples
//!
//! ```
//! use rustica::pvec::PersistentVector;
//! use rustica::traits::functor::Functor;
//! use rustica::traits::foldable::Foldable;
//! use rustica::traits::monoid::Monoid;
//! use rustica::traits::semigroup::Semigroup;
//!
//! // Functor: map over elements
//! let vec = PersistentVector::from_slice(&[1, 2, 3]);
//! let doubled: PersistentVector<i32> = vec.fmap(|x| x * 2);
//! assert_eq!(doubled.to_vec(), vec![2, 4, 6]);
//!
//! // Foldable: reduce elements
//! let sum = vec.fold_left(&0, |acc, x| acc + x);
//! assert_eq!(sum, 6);
//!
//! // Monoid: empty and combine
//! let empty: PersistentVector<i32> = PersistentVector::empty();
//! let combined = vec.combine(&PersistentVector::from_slice(&[4, 5]));
//! assert_eq!(combined.to_vec(), vec![1, 2, 3, 4, 5]);
//! ```

use crate::traits::{
    foldable::Foldable, functor::Functor, hkt::HKT, monoid::Monoid, semigroup::Semigroup,
};

use super::core::PersistentVector;

/// Higher-kinded type implementation for `PersistentVector`.
///
/// This enables `PersistentVector` to be used with generic functions that
/// operate on type constructors (e.g., `F<A>` -> `F<B>`).
impl<T> HKT for PersistentVector<T> {
    type Source = T;
    type Output<U> = PersistentVector<U>;
}

/// Functor implementation for `PersistentVector`.
///
/// Enables structure-preserving transformations over vector elements.
/// The functor laws are satisfied:
/// - Identity: `vec.fmap(|x| x) == vec`
/// - Composition: `vec.fmap(f).fmap(g) == vec.fmap(|x| g(f(x)))`
impl<T: Clone> Functor for PersistentVector<T> {
    #[inline]
    fn fmap<B, F>(&self, f: F) -> Self::Output<B>
    where
        F: Fn(&Self::Source) -> B,
        B: Clone,
    {
        self.map(f)
    }

    #[inline]
    fn fmap_owned<B, F>(self, f: F) -> Self::Output<B>
    where
        F: Fn(Self::Source) -> B,
        B: Clone,
        Self: Sized,
    {
        PersistentVector::from_iter(self.into_iter().map(f))
    }
}

/// Foldable implementation for `PersistentVector`.
///
/// Provides left and right folds for reducing vector elements to a single value.
/// Note: This implementation does not require `T: Clone`.
impl<T> Foldable for PersistentVector<T> {
    /// Folds elements from left to right.
    #[inline]
    fn fold_left<U: Clone, F>(&self, init: &U, f: F) -> U
    where
        F: Fn(&U, &Self::Source) -> U,
    {
        let mut acc = init.clone();
        for item in self {
            acc = f(&acc, item);
        }
        acc
    }

    /// Folds elements from right to left.
    ///
    /// Uses `DoubleEndedIterator` for efficient reverse traversal.
    #[inline]
    fn fold_right<U: Clone, F>(&self, init: &U, f: F) -> U
    where
        F: Fn(&Self::Source, &U) -> U,
    {
        self.iter()
            .rev()
            .fold(init.clone(), |acc, item| f(item, &acc))
    }

    #[inline]
    fn length(&self) -> usize {
        self.len()
    }
}

/// Semigroup implementation for `PersistentVector`.
///
/// Concatenation is the associative binary operation:
/// `(a.combine(b)).combine(c) == a.combine(b.combine(c))`
impl<T: Clone> Semigroup for PersistentVector<T> {
    /// Concatenates two vectors.
    #[inline]
    fn combine(&self, other: &Self) -> Self {
        self.concat(other)
    }

    #[inline]
    fn combine_owned(self, other: Self) -> Self {
        self.concat(&other)
    }
}

/// Monoid implementation for `PersistentVector`.
///
/// The empty vector serves as the identity element:
/// - `empty().combine(x) == x`
/// - `x.combine(empty()) == x`
impl<T: Clone> Monoid for PersistentVector<T> {
    #[inline]
    fn empty() -> Self {
        PersistentVector::new()
    }
}