recursion_schemes/
functor.rs

1#[cfg(feature = "backcompat")]
2use recursion::map_layer::MapLayer;
3#[cfg(feature = "backcompat")]
4use std::marker::PhantomData;
5
6pub trait Functor // where
7//     Self: Self::Layer<PartiallyApplied>,
8{
9    type Layer<X>;
10
11    fn fmap<F, A, B>(input: Self::Layer<A>, f: F) -> Self::Layer<B>
12    where
13        F: FnMut(A) -> B;
14}
15
16pub struct Compose<F1, F2>(std::marker::PhantomData<F1>, std::marker::PhantomData<F2>);
17
18impl<F1: Functor, F2: Functor> Functor for Compose<F1, F2> {
19    type Layer<X> = F1::Layer<F2::Layer<X>>;
20
21    fn fmap<F, A, B>(input: Self::Layer<A>, mut f: F) -> Self::Layer<B>
22    where
23        F: FnMut(A) -> B,
24    {
25        #[allow(clippy::redundant_closure)] // this lint is wrong here
26        F1::fmap(input, move |x| F2::fmap(x, |x| f(x)))
27    }
28}
29
30pub enum PartiallyApplied {}
31
32// used to represent partial expansion
33impl Functor for Option<PartiallyApplied> {
34    type Layer<X> = Option<X>;
35
36    fn fmap<F, A, B>(input: Self::Layer<A>, f: F) -> Self::Layer<B>
37    where
38        F: FnMut(A) -> B,
39    {
40        input.map(f)
41    }
42}
43
44// used to represent partial expansion
45impl<Fst> Functor for (Fst, PartiallyApplied) {
46    type Layer<X> = (Fst, X);
47
48    fn fmap<F, A, B>(input: Self::Layer<A>, mut f: F) -> Self::Layer<B>
49    where
50        F: FnMut(A) -> B,
51    {
52        (input.0, f(input.1))
53    }
54}
55
56pub trait FunctorExt: Functor {
57    fn expand_and_collapse<Seed, Out>(
58        seed: Seed,
59        expand_layer: impl FnMut(Seed) -> <Self as Functor>::Layer<Seed>,
60        collapse_layer: impl FnMut(<Self as Functor>::Layer<Out>) -> Out,
61    ) -> Out;
62}
63
64impl<X> FunctorExt for X
65where
66    X: Functor,
67{
68    fn expand_and_collapse<Seed, Out>(
69        seed: Seed,
70        mut expand_layer: impl FnMut(Seed) -> <X as Functor>::Layer<Seed>,
71        mut collapse_layer: impl FnMut(<X as Functor>::Layer<Out>) -> Out,
72    ) -> Out {
73        enum State<Seed, CollapsableInternal> {
74            Expand(Seed),
75            Collapse(CollapsableInternal),
76        }
77
78        let mut vals: Vec<Out> = vec![];
79        let mut stack = vec![State::Expand(seed)];
80
81        while let Some(item) = stack.pop() {
82            match item {
83                State::Expand(seed) => {
84                    let node = expand_layer(seed);
85                    let mut seeds = Vec::new();
86                    let node = Self::fmap(node, |seed| seeds.push(seed));
87
88                    stack.push(State::Collapse(node));
89                    stack.extend(seeds.into_iter().map(State::Expand));
90                }
91                State::Collapse(node) => {
92                    let node = Self::fmap(node, |_: ()| vals.pop().unwrap());
93                    vals.push(collapse_layer(node))
94                }
95            };
96        }
97        vals.pop().unwrap()
98    }
99}
100
101#[cfg(feature = "backcompat")]
102pub struct MapLayerFromFunctor<Layer, Unwrapped, F: Functor>(
103    Layer,
104    PhantomData<Unwrapped>,
105    PhantomData<F>,
106);
107
108#[cfg(feature = "backcompat")]
109impl<F: Functor, A, B> MapLayer<B> for MapLayerFromFunctor<F::Layer<A>, A, F> {
110    type Unwrapped = A;
111
112    type To = F::Layer<B>;
113
114    fn map_layer<FF: FnMut(Self::Unwrapped) -> B>(self, f: FF) -> Self::To {
115        F::fmap(self.0, f)
116    }
117}
118
119#[cfg(feature = "backcompat")]
120impl<L, U, F: Functor> MapLayerFromFunctor<L, U, F> {
121    pub fn new(x: L) -> Self {
122        MapLayerFromFunctor(x, PhantomData, PhantomData)
123    }
124}
recursion_schemes/functor.rs

recursion_schemes/
functor.rs
