foldlist/
fold_simplification.rs

1use std::marker::PhantomData;
2
3use crate::{fold_settings::FoldSettings, misc::{Bool, ComposeRefFn, Fun}};
4
5/// The trait for [simplifications](crate#simplification)
6pub trait FoldSimplification<T,D: Clone> : Clone  + Copy {
7    /// The new, simplified version of `D`
8    type D2: Clone;
9
10    /// Apply the original operation, under this simplification
11    fn op(&self, a: Self::D2, b: Self::D2, settings: impl FoldSettings<T,D>) -> Self::D2;
12
13    /// Get the simplified version of a `D`
14    fn simplify(&self, delta: &D) -> Self::D2;
15
16    /// Get the simplified version of the empty `D`
17    fn empty(&self, settings: impl FoldSettings<T,D>) -> Self::D2;
18
19    /// Get the simplified version of the `D` of a `T`
20    fn delta_of(&self, value: &T, settings: impl FoldSettings<T,D>) -> Self::D2;
21
22    /// The type of the simplification that results from applying another simplification after this one
23    type Compose<D3: Clone, 
24        Simplifier: for<'x> Fun<&'x Self::D2,D3> + Copy,
25        OP2: Fun<(D3,D3),D3> + Copy> 
26            : FoldSimplification<T,D,D2 = D3>;
27    /// Apply another simplification after this one
28    fn compose<D3: Clone, 
29        Simplifier: for<'x> Fun<&'x Self::D2,D3> + Copy,
30        OP2: Fun<(D3,D3),D3> + Copy>(self, simplifier: Simplifier, op2: OP2) -> Self::Compose<D3,Simplifier,OP2>;
31
32    /// The type of the simplification that results from applying another simplification after this one, with a shortcut
33    type ComposeWithShortcut<D3: Clone, 
34        Simplifier: for<'x> Fun<&'x Self::D2,D3> + Copy,
35        OP2: Fun<(D3,D3),D3> + Copy,
36        EmptyShortcut: Fun<(),D3> + Copy,
37        DeltaShortcut: for<'x> Fun<&'x T, D3> + Copy>
38            : FoldSimplification<T,D,D2 = D3>;
39    /// Apply another simplification after this one, with a shortcut
40    fn compose_with_shortcut<D3: Clone, 
41        Simplifier: for<'x> Fun<&'x Self::D2,D3> + Copy,
42        OP2: Fun<(D3,D3),D3> + Copy,
43        EmptyShortcut: Fun<(),D3> + Copy,
44        DeltaShortcut: for<'x> Fun<&'x T, D3> + Copy>(self, simplifier: Simplifier, op2: OP2,empty_shortcut: EmptyShortcut, delta_shortcut: DeltaShortcut) -> Self::ComposeWithShortcut<D3,Simplifier,OP2,EmptyShortcut,DeltaShortcut>;
45
46    /// The type of the simplification that results from applying this simplification after another (explicit) one
47    type ComposeAfterOther<D0: Clone,Other: FoldSimplification<T,D0,D2=D>> : FoldSimplification<T,D0,D2=Self::D2>;
48    /// Apply this simplification after another (explicit) one
49    fn compose_after_other<D0: Clone,Other: FoldSimplification<T,D0,D2=D>>(self,other: Other) -> Self::ComposeAfterOther<D0,Other>;
50
51    /// The type of the version of this simplification that also keeps track of size
52    type WithSize : FoldSimplification<T,(usize,D),D2=(usize,Self::D2)>;
53    /// Get the version of this simplification that also keeps track of size
54    fn with_size(self) -> Self::WithSize;
55
56    /// Call `op`, but reverse the order of its inputs if `Reversed` is [`True`](crate::misc::True)
57    fn op_cswap<Reversed: Bool>(&self, a: Self::D2, b: Self::D2,settings: impl FoldSettings<T,D>) -> Self::D2 {
58        if Reversed::b {
59            self.op(b,a,settings)
60        } else {
61            self.op(a,b,settings)
62        }
63    }
64}
65
66impl<T,D: Clone> FoldSimplification<T, D> for () {
67    type D2 = D;
68    fn op(&self, a: Self::D2, b: Self::D2, settings: impl FoldSettings<T,D>) -> Self::D2 {
69        settings.op(a,b)
70    }
71    fn simplify(&self, delta: &D) -> Self::D2 {
72        delta.clone()
73    }
74    fn empty(&self, settings: impl FoldSettings<T,D>) -> Self::D2 {
75        settings.empty()
76    }
77    fn delta_of(&self, value: &T, settings: impl FoldSettings<T,D>) -> Self::D2 {
78        settings.delta_of(value)
79    }
80
81    type Compose<D3: Clone, 
82        Simplifier: for<'x> Fun<&'x Self::D2,D3> + Copy,
83        OP2: Fun<(D3,D3),D3> + Copy> 
84            = SimplificationWithoutShortcut<T,D,D3,Simplifier,OP2>;
85    
86    fn compose<D3: Clone, 
87        Simplifier: for<'x> Fun<&'x Self::D2,D3> + Copy,
88        OP2: Fun<(D3,D3),D3> + Copy>(self, simplifier: Simplifier, op2: OP2) -> Self::Compose<D3,Simplifier,OP2> {
89        SimplificationWithoutShortcut { simplifier, op2, _m: PhantomData }
90    }
91
92    type ComposeWithShortcut<D3: Clone, 
93        Simplifier: for<'x> Fun<&'x Self::D2,D3> + Copy,
94        OP2: Fun<(D3,D3),D3> + Copy,
95        EmptyShortcut: Fun<(),D3> + Copy,
96        DeltaShortcut: for<'x> Fun<&'x T, D3> + Copy>
97            = SimplificationWithShortcut<T,D,D3,Simplifier,OP2,EmptyShortcut,DeltaShortcut>;
98            
99
100    fn compose_with_shortcut<D3: Clone, 
101        Simplifier: for<'x> Fun<&'x Self::D2,D3> + Copy,
102        OP2: Fun<(D3,D3),D3> + Copy,
103        EmptyShortcut: Fun<(),D3> + Copy,
104        DeltaShortcut: for<'x> Fun<&'x T, D3> + Copy>(self, simplifier: Simplifier, op2: OP2,empty_shortcut: EmptyShortcut, delta_shortcut: DeltaShortcut) -> Self::ComposeWithShortcut<D3,Simplifier,OP2,EmptyShortcut,DeltaShortcut> {
105        SimplificationWithShortcut{ simplifier, op2, empty_shortcut, delta_shortcut, _m: PhantomData }
106    }
107    
108    type ComposeAfterOther<D0: Clone,Other: FoldSimplification<T,D0,D2=D>> = Other;
109    fn compose_after_other<D0: Clone,Other: FoldSimplification<T,D0,D2=D>>(self,other: Other) -> Self::ComposeAfterOther<D0,Other> {
110        other
111    }
112    
113    type WithSize = ();
114    fn with_size(self) -> Self::WithSize {}
115}
116
117/// A struct which implements [`FoldSimplification`] via two closures, which can be [named](crate#nameable-type).
118pub struct SimplificationWithoutShortcut<T,D: Clone, D2: Clone, 
119    Simplifier: for<'x> Fun<&'x D,D2> + Copy, 
120    OP2: Fun<(D2,D2),D2> + Copy> {
121    /// The closure for [`FoldSimplification::simplify`]
122    pub simplifier: Simplifier,
123    /// The closure for [`FoldSimplification::op`]
124    pub op2: OP2,
125    #[allow(missing_docs)]
126    pub _m: PhantomData<(fn(&D)->D2,fn(&T)->D2)>
127}
128
129impl<T, D: Clone, D2: Clone, Simplifier: for<'x> Fun<&'x D,D2> + Copy, OP2: Fun<(D2,D2),D2> + Copy> Copy for SimplificationWithoutShortcut<T, D, D2, Simplifier, OP2> {}
130impl<T, D: Clone, D2: Clone, Simplifier: for<'x> Fun<&'x D,D2> + Copy, OP2: Fun<(D2,D2),D2> + Copy> 
131Clone for SimplificationWithoutShortcut<T, D, D2, Simplifier, OP2> {
132    fn clone(&self) -> Self {
133        Self { simplifier: self.simplifier.clone(), op2: self.op2.clone(), _m: self._m.clone() }
134    }
135}
136
137impl<T, D: Clone, D2: Clone, Simplifier: for<'x> Fun<&'x D,D2> + Copy, OP2: Fun<(D2,D2),D2> + Copy> 
138FoldSimplification<T,D> for SimplificationWithoutShortcut<T, D, D2, Simplifier, OP2> {
139    type D2 = D2;
140    fn op(&self, a: Self::D2, b: Self::D2, _: impl FoldSettings<T,D>) -> Self::D2 {
141        self.op2.apply((a,b))
142    }
143    fn simplify(&self, delta: &D) -> Self::D2 {
144        self.simplifier.apply(delta)
145    }
146    fn empty(&self, settings: impl FoldSettings<T,D>) -> Self::D2 {
147        self.simplifier.apply(&settings.empty())
148    }
149    fn delta_of(&self, value: &T, settings: impl FoldSettings<T,D>) -> Self::D2 {
150        self.simplifier.apply(&settings.delta_of(value))
151    }
152    type Compose<D3: Clone, 
153        Simplifier2: for<'x> Fun<&'x Self::D2,D3> + Copy,
154        OP3: Fun<(D3,D3),D3> + Copy> 
155            = SimplificationWithoutShortcut<T,D,D3,ComposeRefFn<Simplifier2,Simplifier,D2>,OP3>;
156
157    fn compose<D3: Clone, 
158        Simplifier2: for<'x> Fun<&'x Self::D2,D3> + Copy,
159        OP3: Fun<(D3,D3),D3> + Copy>(self, simplifier2: Simplifier2, op3: OP3) -> Self::Compose<D3,Simplifier2,OP3> {
160        SimplificationWithoutShortcut {
161            simplifier: ComposeRefFn(simplifier2,self.simplifier,PhantomData),
162            op2: op3,
163            _m: PhantomData,
164        }
165    }
166
167    type ComposeWithShortcut<D3: Clone, 
168        Simplifier2: for<'x> Fun<&'x Self::D2,D3> + Copy,
169        OP3: Fun<(D3,D3),D3> + Copy,
170        EmptyShortcut: Fun<(),D3> + Copy,
171        DeltaShortcut: for<'x> Fun<&'x T, D3> + Copy>
172            = SimplificationWithShortcut<T,D,D3,
173                ComposeRefFn<Simplifier2,Simplifier,D2>,
174                OP3,
175                EmptyShortcut,
176                DeltaShortcut>;
177            
178
179    fn compose_with_shortcut<D3: Clone, 
180        Simplifier2: for<'x> Fun<&'x Self::D2,D3> + Copy,
181        OP3: Fun<(D3,D3),D3> + Copy,
182        EmptyShortcut: Fun<(),D3> + Copy,
183        DeltaShortcut: for<'x> Fun<&'x T, D3> + Copy>(self, simplifier: Simplifier2, op2: OP3, empty_shortcut: EmptyShortcut, delta_shortcut: DeltaShortcut) -> Self::ComposeWithShortcut<D3,Simplifier2,OP3,EmptyShortcut,DeltaShortcut> {
184        SimplificationWithShortcut { 
185            simplifier: ComposeRefFn(simplifier, self.simplifier, PhantomData), 
186            op2, 
187            empty_shortcut, 
188            delta_shortcut, 
189            _m: PhantomData 
190        }
191    }
192    
193    type ComposeAfterOther<D0: Clone,Other: FoldSimplification<T,D0,D2=D>> = Other::Compose<D2,Simplifier,OP2>;
194    fn compose_after_other<D0: Clone,Other: FoldSimplification<T,D0,D2=D>>(self,other: Other) -> Self::ComposeAfterOther<D0,Other> {
195        other.compose(self.simplifier,self.op2)
196    }
197    
198    type WithSize = SimplificationWithoutShortcut<T,(usize,D),(usize,D2),KeepSizeAnd<Simplifier>,AddSizesAnd<OP2>>;
199    fn with_size(self) -> Self::WithSize {
200        SimplificationWithoutShortcut {
201            simplifier: KeepSizeAnd(self.simplifier),
202            op2: AddSizesAnd(self.op2),
203            _m: PhantomData,
204        }
205    }
206}
207
208/// A struct which implements [`FoldSimplification`] via four closures, which can be [named](crate#nameable-type).
209pub struct SimplificationWithShortcut<T,D: Clone, D2: Clone, 
210    Simplifier: for<'x> Fun<&'x D,D2> + Copy, 
211    OP2: Fun<(D2,D2),D2> + Copy,
212    EmptyShortcut: Fun<(),D2> + Copy,
213    DeltaShortcut: for<'x> Fun<&'x T, D2> + Copy> {
214        /// The closure for [`FoldSimplification::simplify`]
215        pub simplifier: Simplifier,
216        /// The closure for [`FoldSimplification::op`]
217        pub op2: OP2,
218        /// The closure for [`FoldSimplification::empty`]
219        pub empty_shortcut: EmptyShortcut,
220        /// The closure for [`FoldSimplification::delta_of`]
221        pub delta_shortcut: DeltaShortcut,
222        #[allow(missing_docs)]
223        pub _m: PhantomData<(fn(&D)->D2,fn(&T)->D2)>
224}
225
226impl<T, D: Clone, D2: Clone, Simplifier: for<'x> Fun<&'x D,D2> + Copy, OP2: Fun<(D2,D2),D2> + Copy, EmptyShortcut: Fun<(),D2> + Copy, DeltaShortcut: for<'x> Fun<&'x T, D2> + Copy> 
227Clone for SimplificationWithShortcut<T, D, D2, Simplifier, OP2, EmptyShortcut, DeltaShortcut> {
228    fn clone(&self) -> Self {
229        Self { simplifier: self.simplifier.clone(), op2: self.op2.clone(), empty_shortcut: self.empty_shortcut.clone(), delta_shortcut: self.delta_shortcut.clone(), _m: self._m.clone() }
230    }
231}
232
233impl<T, D: Clone, D2: Clone, Simplifier: for<'x> Fun<&'x D,D2> + Copy, OP2: Fun<(D2,D2),D2> + Copy, EmptyShortcut: Fun<(),D2> + Copy, DeltaShortcut: for<'x> Fun<&'x T, D2> + Copy> Copy for SimplificationWithShortcut<T, D, D2, Simplifier, OP2, EmptyShortcut, DeltaShortcut> {}
234
235
236impl<T, D: Clone, D2: Clone, Simplifier: for<'x> Fun<&'x D,D2> + Copy, OP2: Fun<(D2,D2),D2> + Copy, EmptyShortcut: Fun<(),D2> + Copy, DeltaShortcut: for<'x> Fun<&'x T, D2> + Copy> 
237FoldSimplification<T,D> for SimplificationWithShortcut<T, D, D2, Simplifier, OP2, EmptyShortcut, DeltaShortcut> {
238    type D2 = D2;
239    fn op(&self, a: Self::D2, b: Self::D2, _: impl FoldSettings<T,D>) -> Self::D2 {
240        self.op2.apply((a,b))
241    }
242    fn simplify(&self, delta: &D) -> Self::D2 {
243        self.simplifier.apply(delta)
244    }
245    fn empty(&self, _: impl FoldSettings<T,D>) -> Self::D2 {
246        self.empty_shortcut.apply(())
247    }
248    fn delta_of(&self, value: &T, _: impl FoldSettings<T,D>) -> Self::D2 {
249        self.delta_shortcut.apply(value)
250    }
251
252    type Compose<D3: Clone, 
253        Simplifier2: for<'x> Fun<&'x Self::D2,D3> + Copy,
254        OP3: Fun<(D3,D3),D3> + Copy> 
255            = SimplificationWithShortcut<T,D,D3,
256                ComposeRefFn<Simplifier2,Simplifier,D2>,
257                OP3,
258                ComposeRefFn<Simplifier2,EmptyShortcut,D2>,
259                ComposeRefFn<Simplifier2,DeltaShortcut,D2>>;
260
261    fn compose<D3: Clone, 
262        Simplifier2: for<'x> Fun<&'x Self::D2,D3> + Copy,
263        OP3: Fun<(D3,D3),D3> + Copy>(self, simplifier: Simplifier2, op2: OP3) -> Self::Compose<D3,Simplifier2,OP3> {
264        SimplificationWithShortcut { 
265            simplifier: ComposeRefFn(simplifier, self.simplifier, PhantomData), 
266            op2: op2, 
267            empty_shortcut: ComposeRefFn(simplifier, self.empty_shortcut, PhantomData),
268            delta_shortcut: ComposeRefFn(simplifier, self.delta_shortcut, PhantomData), 
269            _m: PhantomData 
270        }
271    }
272
273    type ComposeWithShortcut<D3: Clone, 
274        Simplifier2: for<'x> Fun<&'x Self::D2,D3> + Copy,
275        OP3: Fun<(D3,D3),D3> + Copy,
276        EmptyShortcut2: Fun<(),D3> + Copy,
277        DeltaShortcut2: for<'x> Fun<&'x T, D3> + Copy>
278            = SimplificationWithShortcut<T,D,D3,
279                ComposeRefFn<Simplifier2,Simplifier,D2>,
280                OP3,
281                EmptyShortcut2,
282                DeltaShortcut2>;
283
284    fn compose_with_shortcut<D3: Clone, 
285        Simplifier2: for<'x> Fun<&'x Self::D2,D3> + Copy,
286        OP3: Fun<(D3,D3),D3> + Copy,
287        EmptyShortcut2: Fun<(),D3> + Copy,
288        DeltaShortcut2: for<'x> Fun<&'x T, D3> + Copy>(self, simplifier: Simplifier2, op2: OP3,empty_shortcut: EmptyShortcut2, delta_shortcut: DeltaShortcut2) -> Self::ComposeWithShortcut<D3,Simplifier2,OP3,EmptyShortcut2,DeltaShortcut2> {
289        SimplificationWithShortcut{ 
290            simplifier: ComposeRefFn(simplifier, self.simplifier, PhantomData), 
291            op2, 
292            empty_shortcut,
293            delta_shortcut, 
294            _m: PhantomData 
295        }
296    }
297    
298    type ComposeAfterOther<D0: Clone,Other: FoldSimplification<T,D0,D2=D>> = Other::ComposeWithShortcut<D2,Simplifier,OP2,EmptyShortcut,DeltaShortcut>;
299    fn compose_after_other<D0: Clone,Other: FoldSimplification<T,D0,D2=D>>(self,other: Other) -> Self::ComposeAfterOther<D0,Other> {
300        other.compose_with_shortcut(self.simplifier, self.op2, self.empty_shortcut, self.delta_shortcut)
301    }
302    
303    type WithSize = SimplificationWithShortcut<T,(usize,D),(usize,D2),
304        KeepSizeAnd<Simplifier>,
305        AddSizesAnd<OP2>,
306        AlwaysAnd<0,EmptyShortcut>,
307        AlwaysAnd<1,DeltaShortcut>>;
308    
309    fn with_size(self) -> Self::WithSize {
310        SimplificationWithShortcut {
311            simplifier: KeepSizeAnd(self.simplifier),
312            op2: AddSizesAnd(self.op2),
313            empty_shortcut: AlwaysAnd(self.empty_shortcut),
314            delta_shortcut: AlwaysAnd(self.delta_shortcut),
315            _m: PhantomData,
316        }
317    }
318}
319
320
321/// A named closure which ignores the first element of a 2-tuple, and clones the other
322#[derive(Clone,Copy)]
323pub struct SizeIgnoreFn;
324impl<'a,U,D: Clone> Fun<&'a (U,D),D> for SizeIgnoreFn {
325    fn apply(&self,a: &'a (U,D)) -> D {
326        a.1.clone()
327    }
328}
329
330/// A wrapper around a [`FoldSettings`] which extracts its `op` behavior into a closure
331pub struct OpFromSettings<T,D: Clone,S: FoldSettings<T,D>> {
332    /// The settings value
333    pub settings: S,
334    #[allow(missing_docs)]
335    pub _m: PhantomData<(T,fn(D,D)->D)>
336}
337
338impl<T, D: Clone, S: FoldSettings<T,D>> Copy for OpFromSettings<T, D, S> {}
339
340impl<T, D: Clone, S: FoldSettings<T,D>> Fun<(D,D),D> for OpFromSettings<T, D, S> {
341    fn apply(&self,(a,b): (D,D)) -> D {
342        self.settings.op(a,b)
343    }
344}
345impl<T, D: Clone, S: FoldSettings<T,D>> Clone for OpFromSettings<T, D, S> {
346    fn clone(&self) -> Self {
347        Self { settings: self.settings.clone(), _m: self._m.clone() }
348    }
349}
350
351/// An alias for a simplification that ignores the `usize` part of `(usize,D)`
352pub type IgnoringSize<T,D,Settings> = SimplificationWithoutShortcut<T,(usize,D),D,SizeIgnoreFn,OpFromSettings<T,D,Settings>>;
353
354/// A wrapper around a closure which applies it to just the second element of a 2-tuple
355#[derive(Clone,Copy)]
356pub struct KeepSizeAnd<F>(pub F);
357impl<'x,U: Copy,D: Clone, D2: Clone, F: for<'a> Fun<&'a D,D2>> Fun<&'x (U,D),(U,D2)> for KeepSizeAnd<F> {
358    fn apply(&self,a: &'x (U,D)) -> (U,D2) {
359        (a.0,self.0.apply(&a.1))
360    }
361}
362
363/// A wrapper around an operator closure which transforms it in the same way [`SettingsWithSize`](crate::fold_settings::SettingsWithSize) does
364#[derive(Clone,Copy)]
365pub struct AddSizesAnd<OP>(pub OP);
366impl<U: core::ops::Add<Output = U> + Copy,D, OP: Fun<(D,D),D>> Fun<((U,D),(U,D)),(U,D)> for AddSizesAnd<OP> {
367    fn apply(&self,((n1,d1),(n2,d2)): ((U,D),(U,D))) -> (U,D) {
368        (n1 + n2, self.0.apply((d1,d2)))
369    }
370}
371
372/// A wrapper around a closure which pairs a constant `usize` with its output
373#[derive(Clone,Copy)]
374pub struct AlwaysAnd<const N: usize, F>(pub F);
375impl<const N: usize, D, I, F: Fun<I,D>> Fun<I,(usize,D)> for AlwaysAnd<N,F> {
376    fn apply(&self,a: I) -> (usize,D) {
377        (N,self.0.apply(a))
378    }
379}
foldlist/fold_simplification.rs

foldlist/
fold_simplification.rs
