rusty_hkt/
lib.rs

1#![no_std]
2
3extern crate alloc;
4use alloc::vec::Vec;
5
6
7/// Core trait for higher-kinded types
8pub trait HKT {
9    type Applied<A>;
10}
11
12/// Marker trait for type constructors
13pub trait TypeConstructor {}
14
15/// Functor trait for mappable types
16pub trait Functor: HKT {
17    fn map<A, B, F>(fa: Self::Applied<A>, f: F) -> Self::Applied<B>
18    where
19        F: FnMut(A) -> B;
20}
21
22/// Applicative trait extending Functor
23pub trait Applicative: Functor {
24    fn pure<A>(a: A) -> Self::Applied<A>;
25    
26    fn ap<A, B, F>(ff: Self::Applied<F>, fa: Self::Applied<A>) -> Self::Applied<B>
27    where
28        F: FnMut(A) -> B;
29}
30
31/// Monad trait extending Applicative
32pub trait Monad: Applicative {
33    fn flat_map<A, B, F>(fa: Self::Applied<A>, f: F) -> Self::Applied<B>
34    where
35        F: FnMut(A) -> Self::Applied<B>;
36        
37    // Default implementation removed - clients must implement
38}
39
40// Option implementation
41
42pub struct OptionHKT;
43
44impl HKT for OptionHKT {
45    type Applied<A> = Option<A>;
46}
47
48impl Functor for OptionHKT {
49    fn map<A, B, F>(fa: Self::Applied<A>, mut f: F) -> Self::Applied<B>
50    where
51        F: FnMut(A) -> B,
52    {
53        fa.map(|a| f(a))
54    }
55}
56
57impl Applicative for OptionHKT {
58    fn pure<A>(a: A) -> Self::Applied<A> {
59        Some(a)
60    }
61    
62    fn ap<A, B, F>(ff: Self::Applied<F>, fa: Self::Applied<A>) -> Self::Applied<B>
63    where
64        F: FnMut(A) -> B,
65    {
66        match (ff, fa) {
67            (Some(mut f), Some(a)) => Some(f(a)),
68            _ => None,
69        }
70    }
71}
72
73impl Monad for OptionHKT {
74    fn flat_map<A, B, F>(fa: Self::Applied<A>, mut f: F) -> Self::Applied<B>
75    where
76        F: FnMut(A) -> Self::Applied<B>,
77    {
78        fa.and_then(|a| f(a))
79    }
80}
81
82// Result implementation
83
84pub struct ResultHKT<E>(core::marker::PhantomData<E>);
85
86impl<E> HKT for ResultHKT<E> {
87    type Applied<A> = Result<A, E>;
88}
89
90impl<E> Functor for ResultHKT<E> {
91    fn map<A, B, F>(fa: Self::Applied<A>, mut f: F) -> Self::Applied<B>
92    where
93        F: FnMut(A) -> B,
94    {
95        fa.map(|a| f(a))
96    }
97}
98
99impl<E> Applicative for ResultHKT<E> {
100    fn pure<A>(a: A) -> Self::Applied<A> {
101        Ok(a)
102    }
103    
104    fn ap<A, B, F>(ff: Self::Applied<F>, fa: Self::Applied<A>) -> Self::Applied<B>
105    where
106        F: FnMut(A) -> B,
107    {
108        match (ff, fa) {
109            (Ok(mut f), Ok(a)) => Ok(f(a)),
110            (Err(e), _) => Err(e),
111            (_, Err(e)) => Err(e),
112        }
113    }
114}
115
116impl<E> Monad for ResultHKT<E> {
117    fn flat_map<A, B, F>(fa: Self::Applied<A>, mut f: F) -> Self::Applied<B>
118    where
119        F: FnMut(A) -> Self::Applied<B>,
120    {
121        fa.and_then(|a| f(a))
122    }
123}
124
125// Vec implementation (uses alloc)
126
127pub struct VecHKT;
128
129impl HKT for VecHKT {
130    type Applied<A> = Vec<A>;
131}
132
133impl Functor for VecHKT {
134    fn map<A, B, F>(fa: Self::Applied<A>, mut f: F) -> Self::Applied<B>
135    where
136        F: FnMut(A) -> B,
137    {
138        let mut result = Vec::with_capacity(fa.len());
139        for a in fa {
140            result.push(f(a));
141        }
142        result
143    }
144}
145
146impl Applicative for VecHKT {
147    fn pure<A>(a: A) -> Self::Applied<A> {
148        let mut result = Vec::with_capacity(1);
149        result.push(a);
150        result
151    }
152    
153    fn ap<A, B, F>(ff: Self::Applied<F>, fa: Self::Applied<A>) -> Self::Applied<B>
154    where
155        F: FnMut(A) -> B,
156    {
157        let mut result = Vec::new();
158        for mut f in ff {
159            for a in &fa {
160                // Need to copy here since we can't move out of borrowed content
161                let a_owned = unsafe { core::ptr::read(a) };
162                result.push(f(a_owned));
163            }
164        }
165        result
166    }
167}
168
169impl Monad for VecHKT {
170    fn flat_map<A, B, F>(fa: Self::Applied<A>, mut f: F) -> Self::Applied<B>
171    where
172        F: FnMut(A) -> Self::Applied<B>,
173    {
174        let mut result = Vec::new();
175        for a in fa {
176            result.extend(f(a));
177        }
178        result
179    }
180}
181
182// Generic HKT for Box
183pub struct BoxHKT;
184
185impl HKT for BoxHKT {
186    type Applied<A> = alloc::boxed::Box<A>;
187}
188
189impl Functor for BoxHKT {
190    fn map<A, B, F>(fa: Self::Applied<A>, mut f: F) -> Self::Applied<B>
191    where
192        F: FnMut(A) -> B,
193    {
194        alloc::boxed::Box::new(f(*fa))
195    }
196}
197
198impl Applicative for BoxHKT {
199    fn pure<A>(a: A) -> Self::Applied<A> {
200        alloc::boxed::Box::new(a)
201    }
202    
203    fn ap<A, B, F>(ff: Self::Applied<F>, fa: Self::Applied<A>) -> Self::Applied<B>
204    where
205        F: FnMut(A) -> B,
206    {
207        let mut f = *ff;
208        alloc::boxed::Box::new(f(*fa))
209    }
210}
211
212impl Monad for BoxHKT {
213    fn flat_map<A, B, F>(fa: Self::Applied<A>, mut f: F) -> Self::Applied<B>
214    where
215        F: FnMut(A) -> Self::Applied<B>,
216    {
217        f(*fa)
218    }
219}
220
221// Identity type implementation
222pub struct Identity<A>(pub A);
223
224pub struct IdentityHKT;
225
226impl HKT for IdentityHKT {
227    type Applied<A> = Identity<A>;
228}
229
230impl Functor for IdentityHKT {
231    fn map<A, B, F>(fa: Self::Applied<A>, mut f: F) -> Self::Applied<B>
232    where
233        F: FnMut(A) -> B,
234    {
235        Identity(f(fa.0))
236    }
237}
238
239impl Applicative for IdentityHKT {
240    fn pure<A>(a: A) -> Self::Applied<A> {
241        Identity(a)
242    }
243    
244    fn ap<A, B, F>(ff: Self::Applied<F>, fa: Self::Applied<A>) -> Self::Applied<B>
245    where
246        F: FnMut(A) -> B,
247    {
248        let mut f = ff.0;
249        Identity(f(fa.0))
250    }
251}
252
253impl Monad for IdentityHKT {
254    fn flat_map<A, B, F>(fa: Self::Applied<A>, mut f: F) -> Self::Applied<B>
255    where
256        F: FnMut(A) -> Self::Applied<B>,
257    {
258        f(fa.0)
259    }
260}
261
262// Usage helpers
263
264pub fn map<F, A, B, G>(fa: F::Applied<A>, g: G) -> F::Applied<B>
265where
266    F: Functor,
267    G: FnMut(A) -> B,
268{
269    F::map(fa, g)
270}
271
272pub fn pure<F, A>(a: A) -> F::Applied<A>
273where
274    F: Applicative,
275{
276    F::pure(a)
277}
278
279pub fn flat_map<F, A, B, G>(fa: F::Applied<A>, g: G) -> F::Applied<B>
280where
281    F: Monad,
282    G: FnMut(A) -> F::Applied<B>,
283{
284    F::flat_map(fa, g)
285}
286
287// Additional utility functions
288pub fn then<F, A, B>(fa: F::Applied<A>, fb: F::Applied<B>) -> F::Applied<B>
289where
290    F: Monad,
291    F::Applied<B>: Clone,
292{
293    F::flat_map(fa, move |_| fb.clone())
294}
295
296#[cfg(test)]
297mod tests {
298    use super::*;
299    use alloc::vec;
300
301    #[test]
302    fn option_functor() {
303        let opt = Some(3);
304        let res = map::<OptionHKT, _, _, _>(opt, |x| x * 2);
305        assert_eq!(res, Some(6));
306    }
307
308    #[test]
309    fn result_monad() {
310        let res: Result<i32, &str> = Ok(3);
311        let doubled = flat_map::<ResultHKT<&str>, _, _, _>(res, |x| Ok(x * 2));
312        assert_eq!(doubled, Ok(6));
313    }
314    
315    #[test]
316    fn vec_functor() {
317        let v = vec![1, 2, 3];
318        let res = map::<VecHKT, _, _, _>(v, |x| x * 2);
319        assert_eq!(res, vec![2, 4, 6]);
320    }
321    
322    #[test]
323    fn identity_monad() {
324        let id = Identity(5);
325        let res = flat_map::<IdentityHKT, _, _, _>(id, |x| Identity(x * 2));
326        assert_eq!(res.0, 10);
327    }
328}
rusty_hkt/lib.rs

rusty_hkt/
lib.rs
