rs_category/
lib.rs

1#![no_std]
2
3//#![feature(fn_traits)]
4//#![feature(type_alias_impl_trait)]
5
6use core::{marker::PhantomData, mem, ptr};
7use void::Void;
8
9pub trait H1 {
10    type H<A>;
11}
12
13pub trait H2 {
14    type H<A, B>;
15}
16
17pub trait EndofunctorOnce: EndofunctorMut {
18    fn map_once<A, B>(_: impl FnOnce(A) -> B, _: Self::H<A>) -> Self::H<B>;
19}
20
21pub trait EndofunctorMut: Endofunctor {
22    fn map_mut<A, B>(_: impl FnMut(A) -> B, _: Self::H<A>) -> Self::H<B>;
23}
24
25pub trait Endofunctor: H1 {
26    fn map<A, B>(_: impl Fn(A) -> B, _: Self::H<A>) -> Self::H<B>;
27}
28
29pub trait ApplicableOnce: ApplicableMut + EndofunctorOnce {
30    #[inline]
31    fn ap_once<A, B>(f: Self::H<impl FnOnce(A) -> B>, a: Self::H<A>) -> Self::H<B> { Self::liftA2_once(|f, a| f(a), f, a) }
32
33    #[inline]
34    fn liftA2_once<A, B, C>(f: impl FnOnce(A, B) -> C, a: Self::H<A>, b: Self::H<B>) -> Self::H<C> {
35        Self::ap_once(Self::map_once(move |a| |b| f(a, b), a), b)
36    }
37}
38
39pub trait ApplicableMut: Applicable + EndofunctorMut {
40    #[inline]
41    fn ap_mut<A, B>(f: Self::H<impl FnMut(A) -> B>, a: Self::H<A>) -> Self::H<B> { Self::liftA2_mut(|mut f, a| f(a), f, a) }
42
43    fn liftA2_mut<A, B, C>(_: impl FnMut(A, B) -> C, _: Self::H<A>, _: Self::H<B>) -> Self::H<C>;
44}
45
46pub trait Applicable: Endofunctor {
47    #[inline]
48    fn ap<A, B>(f: Self::H<impl Fn(A) -> B>, a: Self::H<A>) -> Self::H<B> { Self::liftA2(|f, a| f(a), f, a) }
49
50    fn liftA2<A, B, C>(_: impl Fn(A, B) -> C, _: Self::H<A>, _: Self::H<B>) -> Self::H<C>;
51}
52
53pub trait Semimonad: Endofunctor {
54    fn join<A>(_: Self::H<Self::H<A>>) -> Self::H<A>;
55}
56
57#[inline]
58pub fn bind_once<A, B, F: Semimonad + EndofunctorOnce, Φ: FnOnce(A) -> F::H<B>>(f: Φ, a: F::H<A>) -> F::H<B> { F::join(F::map_once(f, a)) }
59
60#[inline]
61pub fn bind_mut<A, B, F: Semimonad + EndofunctorMut, Φ: FnMut(A) -> F::H<B>>(f: Φ, a: F::H<A>) -> F::H<B> { F::join(F::map_mut(f, a)) }
62
63#[inline]
64pub fn bind<A, B, F: Semimonad + EndofunctorMut, Φ: Fn(A) -> F::H<B>>(f: Φ, a: F::H<A>) -> F::H<B> { F::join(F::map(f, a)) }
65
66pub trait Pointed: H1 {
67    fn point<A>(_: A) -> Self::H<A>;
68}
69
70pub trait TraversableOnce: EndofunctorOnce + TraversableMut {
71    fn traverse_once<A, B, P: Pointed + ApplicableOnce>(_: impl FnOnce(A) -> P::H<B>, _: Self::H<A>) -> P::H<Self::H<B>>;
72}
73
74pub trait TraversableMut: EndofunctorMut + Traversable {
75    fn traverse_mut<A, B, P: Pointed + ApplicableMut>(_: impl FnMut(A) -> P::H<B>, _: Self::H<A>) -> P::H<Self::H<B>>;
76}
77
78pub trait Traversable: Endofunctor {
79    fn traverse<A, B, P: Pointed + Applicable>(_: impl Fn(A) -> P::H<B>, _: Self::H<A>) -> P::H<Self::H<B>>;
80}
81
82pub struct ArrayW<const N: usize>(Void);
83
84impl<const N: usize> H1 for ArrayW<N> {
85    type H<A> = [A; N];
86}
87
88impl<const N: usize> EndofunctorMut for ArrayW<N> {
89    #[inline]
90    fn map_mut<A, B>(mut f: impl FnMut(A) -> B, a: [A; N]) -> [B; N] { map_array_with_ix_mut(|a, _| f(a), a) }
91}
92
93impl<const N: usize> Endofunctor for ArrayW<N> {
94    #[inline]
95    fn map<A, B>(f: impl Fn(A) -> B, a: [A; N]) -> [B; N] { Self::map_mut(f, a) }
96}
97
98impl<const N: usize> ApplicableMut for ArrayW<N> {
99    #[inline]
100    fn liftA2_mut<A, B, C>(mut f: impl FnMut(A, B) -> C, a: [A; N], b: [B; N]) -> [C; N] { unsafe {
101        let a = mem::ManuallyDrop::new(a);
102        let b = mem::ManuallyDrop::new(b);
103        let mut c = mem::MaybeUninit::<[C; N]>::uninit();
104        for k in 0..N { ptr::write((c.as_mut_ptr() as *mut C).wrapping_add(k), f(ptr::read(&a[k]), ptr::read(&b[k]))) }
105        c.assume_init()
106    } }
107}
108
109impl<const N: usize> Applicable for ArrayW<N> {
110    #[inline]
111    fn liftA2<A, B, C>(f: impl Fn(A, B) -> C, a: [A; N], b: [B; N]) -> [C; N] { Self::liftA2_mut(f, a, b) }
112}
113
114impl<const N: usize> Semimonad for ArrayW<N> {
115    #[inline]
116    fn join<A>(a: [[A; N]; N]) -> [A; N] {
117        map_array_with_ix_mut(|a, k| unsafe { let a = mem::ManuallyDrop::new(a); ptr::read(&a[k]) }, a)
118    }
119}
120
121impl<const N: usize> TraversableMut for ArrayW<N> {
122    #[inline]
123    fn traverse_mut<A, B, P: Pointed + Applicable>(mut f: impl FnMut(A) -> P::H<B>, a: [A; N]) -> P::H<[B; N]> { traverse_array_with_ix_mut::<_, _, P, _, N>(|a, _| f(a), a) }
124}
125
126impl<const N: usize> Traversable for ArrayW<N> {
127    #[inline]
128    fn traverse<A, B, P: Pointed + Applicable>(f: impl Fn(A) -> P::H<B>, a: [A; N]) -> P::H<[B; N]> { traverse_array_with_ix_mut::<_, _, P, _, N>(|a, _| f(a), a) }
129}
130
131impl Pointed for ArrayW<1> {
132    #[inline]
133    fn point<A>(a: A) -> [A; 1] { [a] }
134}
135
136impl EndofunctorOnce for ArrayW<1> {
137    #[inline]
138    fn map_once<A, B>(f: impl FnOnce(A) -> B, [a]: [A; 1]) -> [B; 1] { [f(a)] }
139}
140
141#[inline]
142fn map_array_with_ix_mut<A, B, const N: usize>(mut f: impl FnMut(A, usize) -> B, a: [A; N]) -> [B; N] { unsafe {
143    let a = mem::ManuallyDrop::new(a);
144    let mut b = mem::MaybeUninit::<[B; N]>::uninit();
145    for k in 0..N { ptr::write((b.as_mut_ptr() as *mut B).wrapping_add(k), f(ptr::read(&a[k]), k)); }
146    b.assume_init()
147} }
148
149#[inline]
150fn traverse_array_with_ix_mut<A, B, P: Pointed + Applicable, F: FnMut(A, usize) -> P::H<B>, const N: usize>(mut f: F, a: [A; N]) -> P::H<[B; N]> { unsafe {
151    let a = mem::ManuallyDrop::new(a);
152    let mut bsp = P::point(mem::MaybeUninit::<[B; N]>::uninit());
153    for k in 0..N {
154        let bp = f(ptr::read(&a[k]), k);
155        bsp = P::liftA2(|b, mut bs| {
156            ptr::write((bs.as_mut_ptr() as *mut B).wrapping_add(k), b);
157            bs
158        }, bp, bsp);
159    }
160    P::map(|x| x.assume_init(), bsp)
161} }
162
163#[inline]
164fn zip_arrays_with_ix_mut<A, B, C, F: FnMut(A, B, usize) -> C, const N: usize>(mut f: F, a: [A; N], b: [B; N]) -> [C; N] { unsafe {
165        let a = mem::ManuallyDrop::new(a);
166        let b = mem::ManuallyDrop::new(b);
167    let mut c = mem::MaybeUninit::<[C; N]>::uninit();
168    for k in 0..N { ptr::write((c.as_mut_ptr() as *mut C).wrapping_add(k), f(ptr::read(&a[k]), ptr::read(&b[k]), k)); }
169    c.assume_init()
170} }
171
172#[allow(unused)]
173#[inline]
174fn zipA_arrays_with_ix_mut<A, B, C, P: Pointed + Applicable, F: FnMut(A, B, usize) -> P::H<C>, const N: usize>(mut f: F, a: [A; N], b: [B; N]) -> P::H<[C; N]> { unsafe {
175    let a = mem::ManuallyDrop::new(a);
176    let b = mem::ManuallyDrop::new(b);
177    let mut csp = P::point(mem::MaybeUninit::<[C; N]>::uninit());
178    for k in 0..N {
179        let cp = f(ptr::read(&a[k]), ptr::read(&b[k]), k);
180        csp = P::liftA2(|c, mut cs| {
181            ptr::write((cs.as_mut_ptr() as *mut C).wrapping_add(k), c);
182            cs
183        }, cp, csp);
184    }
185    P::map(|x| x.assume_init(), csp)
186} }
187
188pub struct OptionW(Void);
189
190impl H1 for OptionW {
191    type H<A> = Option<A>;
192}
193
194impl EndofunctorOnce for OptionW {
195    #[inline]
196    fn map_once<A, B>(f: impl FnOnce(A) -> B, a: Option<A>) -> Option<B> { a.map(f) }
197}
198
199impl EndofunctorMut for OptionW {
200    #[inline]
201    fn map_mut<A, B>(f: impl FnMut(A) -> B, a: Option<A>) -> Option<B> { a.map(f) }
202}
203
204impl Endofunctor for OptionW {
205    #[inline]
206    fn map<A, B>(f: impl Fn(A) -> B, a: Option<A>) -> Option<B> { a.map(f) }
207}
208
209impl ApplicableOnce for OptionW {
210    #[inline]
211    fn liftA2_once<A, B, C>(f: impl FnOnce(A, B) -> C, a: Option<A>, b: Option<B>) -> Option<C> { match (a, b) {
212        (Some(a), Some(b)) => Some(f(a, b)),
213        _ => None,
214    } }
215}
216
217impl ApplicableMut for OptionW {
218    #[inline]
219    fn liftA2_mut<A, B, C>(f: impl FnMut(A, B) -> C, a: Option<A>, b: Option<B>) -> Option<C> { Self::liftA2_once(f, a, b) }
220}
221
222impl Applicable for OptionW {
223    #[inline]
224    fn liftA2<A, B, C>(f: impl Fn(A, B) -> C, a: Option<A>, b: Option<B>) -> Option<C> { Self::liftA2_once(f, a, b) }
225}
226
227impl Semimonad for OptionW {
228    #[inline]
229    fn join<A>(a: Option<Option<A>>) -> Option<A> { match a { Some(a) => a, None => None, } }
230}
231
232impl TraversableOnce for OptionW {
233    #[inline]
234    fn traverse_once<A, B, P: Pointed + ApplicableOnce>(f: impl FnOnce(A) -> P::H<B>, a: Option<A>) -> P::H<Option<B>> { match a {
235        None => P::point(None),
236        Some(a) => P::map(Some, f(a)),
237    } }
238}
239
240impl TraversableMut for OptionW {
241    #[inline]
242    fn traverse_mut<A, B, P: Pointed + ApplicableMut>(mut f: impl FnMut(A) -> P::H<B>, a: Option<A>) -> P::H<Option<B>> { match a {
243        None => P::point(None),
244        Some(a) => P::map(Some, f(a)),
245    } }
246}
247
248impl Traversable for OptionW {
249    #[inline]
250    fn traverse<A, B, P: Pointed + Applicable>(f: impl Fn(A) -> P::H<B>, a: Option<A>) -> P::H<Option<B>> { match a {
251        None => P::point(None),
252        Some(a) => P::map(Some, f(a)),
253    } }
254}
255
256pub struct ResultW<E>(PhantomData<E>, Void);
257
258impl<E> H1 for ResultW<E> {
259    type H<A> = Result<A, E>;
260}
261
262impl<E> EndofunctorOnce for ResultW<E> {
263    #[inline]
264    fn map_once<A, B>(f: impl FnOnce(A) -> B, a: Result<A, E>) -> Result<B, E> { a.map(f) }
265}
266
267impl<E> EndofunctorMut for ResultW<E> {
268    #[inline]
269    fn map_mut<A, B>(f: impl FnMut(A) -> B, a: Result<A, E>) -> Result<B, E> { a.map(f) }
270}
271
272impl<E> Endofunctor for ResultW<E> {
273    #[inline]
274    fn map<A, B>(f: impl Fn(A) -> B, a: Result<A, E>) -> Result<B, E> { a.map(f) }
275}
276
277impl<E: Semigroup> ApplicableOnce for ResultW<E> {
278    #[inline]
279    fn liftA2_once<A, B, C>(f: impl FnOnce(A, B) -> C, a: Result<A, E>, b: Result<B, E>) -> Result<C, E> { match (a, b) {
280        (Ok(a), Ok(b)) => Ok(f(a, b)),
281        (Ok(_), Err(y)) => Err(y),
282        (Err(x), Ok(_)) => Err(x),
283        (Err(x), Err(y)) => Err(E::combine(x, y)),
284    } }
285}
286
287impl<E: Semigroup> ApplicableMut for ResultW<E> {
288    #[inline]
289    fn liftA2_mut<A, B, C>(f: impl FnMut(A, B) -> C, a: Result<A, E>, b: Result<B, E>) -> Result<C, E> { Self::liftA2_once(f, a, b) }
290}
291
292impl<E: Semigroup> Applicable for ResultW<E> {
293    #[inline]
294    fn liftA2<A, B, C>(f: impl Fn(A, B) -> C, a: Result<A, E>, b: Result<B, E>) -> Result<C, E> { Self::liftA2_once(f, a, b) }
295}
296
297pub trait Semigroup {
298    fn combine(_: Self, _: Self) -> Self;
299}
300
301impl<A: Semigroup, const N: usize> Semigroup for [A; N] {
302    #[inline]
303    fn combine(a: Self, b: Self) -> Self { zip_arrays_with_ix_mut(|a, b, _| A::combine(a, b), a, b) }
304}
305
306// We not define `Monoid`, for we can rather use `Default + Semigroup`.
307
308macro_rules! impl_Semigroup_etc_tuple {
309    ($($A:ident, $n:tt),*) => {
310        impl<$($A: Semigroup),*> Semigroup for ($($A),*) {
311            #[allow(unused_variables)]
312            #[inline]
313            fn combine(a: Self, b: Self) -> Self { ($($A::combine(a.$n, b.$n)),*) }
314        }
315    }
316}
317
318/*
319pub trait Group: Default + Semigroup {
320    fn invert(_: Self) -> Self;
321}
322
323// stupid standard library has no general impl Default for arrays.
324
325impl<A: Group, const N: usize> Group for [A; N] {
326    #[inline]
327    fn invert(a: Self) -> Self { map_array_with_ix_mut(|a, _| A::invert(a), a) }
328}
329*/
330
331impl_Semigroup_etc_tuple!();
332impl_Semigroup_etc_tuple!(A, 0, B, 1);
333impl_Semigroup_etc_tuple!(A, 0, B, 1, C, 2);
334impl_Semigroup_etc_tuple!(A, 0, B, 1, C, 2, D, 3);
335impl_Semigroup_etc_tuple!(A, 0, B, 1, C, 2, D, 3, E, 4);
336impl_Semigroup_etc_tuple!(A, 0, B, 1, C, 2, D, 3, E, 4, F, 5);
337impl_Semigroup_etc_tuple!(A, 0, B, 1, C, 2, D, 3, E, 4, F, 5, G, 6);
338impl_Semigroup_etc_tuple!(A, 0, B, 1, C, 2, D, 3, E, 4, F, 5, G, 6, H, 7);
339impl_Semigroup_etc_tuple!(A, 0, B, 1, C, 2, D, 3, E, 4, F, 5, G, 6, H, 7, I, 8);
340impl_Semigroup_etc_tuple!(A, 0, B, 1, C, 2, D, 3, E, 4, F, 5, G, 6, H, 7, I, 8, J, 9);
341impl_Semigroup_etc_tuple!(A, 0, B, 1, C, 2, D, 3, E, 4, F, 5, G, 6, H, 7, I, 8, J, 9, K, 10);
342impl_Semigroup_etc_tuple!(A, 0, B, 1, C, 2, D, 3, E, 4, F, 5, G, 6, H, 7, I, 8, J, 9, K, 10, L, 11);
343impl_Semigroup_etc_tuple!(A, 0, B, 1, C, 2, D, 3, E, 4, F, 5, G, 6, H, 7, I, 8, J, 9, K, 10, L, 11, M, 12);
344impl_Semigroup_etc_tuple!(A, 0, B, 1, C, 2, D, 3, E, 4, F, 5, G, 6, H, 7, I, 8, J, 9, K, 10, L, 11, M, 12, N, 13);
345impl_Semigroup_etc_tuple!(A, 0, B, 1, C, 2, D, 3, E, 4, F, 5, G, 6, H, 7, I, 8, J, 9, K, 10, L, 11, M, 12, N, 13, O, 14);
346
347/// Sugar for doing monadically
348///
349/// Example:
350/// ```
351/// use category::rust::ArrayW;
352/// use category::rust::Pointed;
353/// (category::monadically_once! { ArrayW<1>:
354///     x <- [()];
355///     [x]
356/// })[0]
357/// ```
358/// ```
359/// use category::rust::OptionW;
360/// use category::rust::Pointed;
361/// Option::unwrap_or(category::monadically_once! { OptionW:
362///     x <- Some(());
363///     _ <- None;
364///     Some(category::rust::Semigroup::combine(x, y))
365/// }, ())
366/// ```
367#[macro_export]
368macro_rules! monadically_once {
369    // Alas, Rust won't accept `... $p:pat <- ...`, so we must copy the irrefutable pattern syntax here.
370    ($t:ty: _ <- $($r:tt)*) => ($crate::monadically_once!($t: (_) <- $($r)*));
371    ($t:ty: $(ref)? $(mut)? $v:ident <- $($r:tt)*) => ($crate::monadically_once!($t: ($(ref)? $(mut)? $v) <- $($r)*));
372    ($t:ty: $p:path { $($e:tt)* } <- $($r:tt)*) => ($crate::monadically_once!($t: ($p { $($e)* }) <- $($r)*));
373    ($t:ty: ($p:pat,) <- $($r:tt)*) => ($crate::monadically_once!($t: (($p,)) <- $($r)*));
374    ($t:ty: ($($p:pat),+ $(,)?) <- $($r:tt)*) => ($crate::monadically_once!($t: (($($p),+)) <- $($r)*));
375    ($t:ty: ($($p:pat,)* ..) <- $($r:tt)*) => ($crate::monadically_once!($t: (($($p,)* ..)) <- $($r)*));
376    ($t:ty: [$($p:pat),* $(,)?] <- $($r:tt)*) => ($crate::monadically_once!($t: ([$($p),*]) <- $($r)*));
377    ($t:ty: [$($p:pat,)* ..] <- $($r:tt)*) => ($crate::monadically_once!($t: ([$($p,)* ..]) <- $($r)*));
378    ($t:ty: ($p:pat) <- $x:expr; $($r:tt)*) => ($crate::bind_once::<_, _, $t, _>(move |$p| $crate::monadically_once!($t: $($r)*), $x));
379    ($t:ty: $x:expr; $($r:tt)*) => ($crate::monadically_once!($t: _ <- $t; $($r)*));
380    ($t:ty: let $p:pat = $x:expr; $($r:tt)*) => ({ let $p = $x; $crate::monadically_once!($t: $($r)*) });
381    ($t:ty: $x:expr) => ($x);
382}
rs_category/lib.rs

rs_category/
lib.rs
