recursion_schemes/
recursive.rs

1use std::sync::Arc;
2
3#[cfg(feature = "backcompat")]
4use recursion::Collapse;
5
6use crate::functor::{Compose, Functor, FunctorExt, PartiallyApplied};
7
8pub trait Recursive
9where
10    Self: Sized,
11{
12    type FunctorToken: Functor;
13
14    fn into_layer(self) -> <Self::FunctorToken as Functor>::Layer<Self>;
15}
16
17/// heap allocated fix point of some Functor
18pub struct Fix<F: Functor>(pub Box<F::Layer<Fix<F>>>);
19
20impl<F: Functor> Fix<F> {
21    pub fn new(x: F::Layer<Self>) -> Self {
22        Self(Box::new(x))
23    }
24}
25
26// recursing over a fix point structure is free
27impl<F: Functor> Recursive for Fix<F> {
28    type FunctorToken = F;
29
30    fn into_layer(self) -> <Self::FunctorToken as Functor>::Layer<Self> {
31        *self.0
32    }
33}
34
35// TODO: futumorphism to allow for partial non-async expansion? yes! but (I think) needs to be erased for collapse phase
36// TODO: b/c at that point there's no need for that info..
37
38pub struct WithContext<R: Recursive>(pub R);
39
40impl<R: Recursive + Copy> Recursive for WithContext<R> {
41    type FunctorToken = Compose<R::FunctorToken, (R, PartiallyApplied)>;
42
43    fn into_layer(self) -> <Self::FunctorToken as Functor>::Layer<Self> {
44        let layer = R::into_layer(self.0);
45        R::FunctorToken::fmap(layer, move |wrapped| (wrapped, WithContext(wrapped)))
46    }
47}
48
49pub struct PartialExpansion<R: Recursive> {
50    pub wrapped: R,
51    #[allow(clippy::type_complexity)]
52    pub f: Arc<
53        // TODO: probably doesn't need to be an arc but (shrug emoji)
54        dyn Fn(
55            <<R as Recursive>::FunctorToken as Functor>::Layer<R>,
56        ) -> <<R as Recursive>::FunctorToken as Functor>::Layer<Option<R>>,
57    >,
58}
59
60impl<R: Recursive> Recursive for PartialExpansion<R> {
61    type FunctorToken = Compose<R::FunctorToken, Option<PartiallyApplied>>;
62
63    fn into_layer(self) -> <Self::FunctorToken as Functor>::Layer<Self> {
64        let partially_expanded = (self.f)(self.wrapped.into_layer());
65        Self::FunctorToken::fmap(partially_expanded, move |wrapped| PartialExpansion {
66            wrapped,
67            f: self.f.clone(),
68        })
69    }
70}
71
72pub trait RecursiveExt: Recursive {
73    fn fold_recursive<
74        Out,
75        F: FnMut(<<Self as Recursive>::FunctorToken as Functor>::Layer<Out>) -> Out,
76    >(
77        self,
78        collapse_layer: F,
79    ) -> Out;
80
81    fn expand_and_collapse<Seed, Out>(
82        seed: Seed,
83        expand_layer: impl FnMut(Seed) -> <<Self as Recursive>::FunctorToken as Functor>::Layer<Seed>,
84        collapse_layer: impl FnMut(<<Self as Recursive>::FunctorToken as Functor>::Layer<Out>) -> Out,
85    ) -> Out;
86}
87
88impl<X> RecursiveExt for X
89where
90    X: Recursive,
91{
92    fn fold_recursive<
93        Out,
94        F: FnMut(<<X as Recursive>::FunctorToken as Functor>::Layer<Out>) -> Out,
95    >(
96        self,
97        collapse_layer: F,
98    ) -> Out {
99        Self::expand_and_collapse(self, Self::into_layer, collapse_layer)
100    }
101
102    fn expand_and_collapse<Seed, Out>(
103        seed: Seed,
104        expand_layer: impl FnMut(Seed) -> <<X as Recursive>::FunctorToken as Functor>::Layer<Seed>,
105        collapse_layer: impl FnMut(<<X as Recursive>::FunctorToken as Functor>::Layer<Out>) -> Out,
106    ) -> Out {
107        <X as Recursive>::FunctorToken::expand_and_collapse(seed, expand_layer, collapse_layer)
108    }
109}
110
111#[cfg(feature = "backcompat")]
112struct CollapseViaRecursive<X>(X);
113
114#[cfg(feature = "backcompat")]
115impl<Out, R: RecursiveExt> Collapse<Out, <<R as Recursive>::FunctorToken as Functor>::Layer<Out>>
116    for CollapseViaRecursive<R>
117{
118    fn collapse_layers<F: FnMut(<<R as Recursive>::FunctorToken as Functor>::Layer<Out>) -> Out>(
119        self,
120        collapse_layer: F,
121    ) -> Out {
122        self.0.fold_recursive(collapse_layer)
123    }
124}
recursion_schemes/recursive.rs

recursion_schemes/
recursive.rs
