fp_library/classes/filterable.rs
1//! Filterable type class.
2//!
3//! This module defines the [`Filterable`] trait, which represents data structures that can be filtered and partitioned.
4//!
5//! ### Examples
6//!
7//! ```
8//! use fp_library::{brands::*, functions::*};
9//!
10//! let x = Some(5);
11//! let y = filter::<OptionBrand, _, _>(|a| a > 2, x);
12//! assert_eq!(y, Some(5));
13//! ```
14
15use crate::{
16 Apply,
17 classes::{compactable::Compactable, functor::Functor},
18 kinds::*,
19 types::Pair,
20};
21
22/// A type class for data structures that can be filtered and partitioned.
23///
24/// `Filterable` extends [`Compactable`] and [`Functor`], adding methods for:
25/// * `filter`: Keeping elements that satisfy a predicate.
26/// * `filter_map`: Mapping and filtering in one step.
27/// * `partition`: Splitting elements based on a predicate.
28/// * `partition_map`: Mapping and partitioning in one step.
29///
30/// ### Minimal Implementation
31///
32/// A minimal implementation of `Filterable` requires no specific method implementations, as all methods have default implementations based on [`Compactable`] and [`Functor`].
33///
34/// However, it is recommended to implement [`Filterable::partition_map`] and [`Filterable::filter_map`] to avoid the intermediate structure created by the default implementations (which use [`Functor::map`] followed by [`Compactable::separate`] or [`Compactable::compact`]).
35///
36/// * If [`Filterable::partition_map`] is implemented, [`Filterable::partition`] is derived from it.
37/// * If [`Filterable::filter_map`] is implemented, [`Filterable::filter`] is derived from it.
38pub trait Filterable: Compactable + Functor {
39 /// Partitions a data structure based on a function that returns a `Result`.
40 ///
41 /// The default implementation uses [`Functor::map`] and [`Compactable::separate`].
42 ///
43 /// ### Type Signature
44 ///
45 /// `forall f o e a. Filterable f => (a -> Result o e, f a) -> Pair (f o) (f e)`
46 ///
47 /// ### Type Parameters
48 ///
49 /// * `O`: The type of the success values.
50 /// * `E`: The type of the error values.
51 /// * `A`: The type of the elements in the input structure.
52 /// * `Func`: The type of the function to apply.
53 ///
54 /// ### Parameters
55 ///
56 /// * `func`: The function to apply to each element, returning a `Result`.
57 /// * `fa`: The data structure to partition.
58 ///
59 /// ### Returns
60 ///
61 /// A pair of data structures: the first containing the `Ok` values, and the second containing the `Err` values.
62 ///
63 /// ### Examples
64 ///
65 /// ```
66 /// use fp_library::{brands::*, functions::*, types::*};
67 ///
68 /// let x = Some(5);
69 /// let Pair(oks, errs) = partition_map::<OptionBrand, _, _, _, _>(|a| if a > 2 { Ok(a) } else { Err(a) }, x);
70 /// assert_eq!(oks, Some(5));
71 /// assert_eq!(errs, None);
72 /// ```
73 fn partition_map<'a, O: 'a, E: 'a, A: 'a, Func>(
74 func: Func,
75 fa: Apply!(<Self as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>),
76 ) -> Pair<
77 Apply!(<Self as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, O>),
78 Apply!(<Self as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, E>),
79 >
80 where
81 Func: Fn(A) -> Result<O, E> + 'a,
82 {
83 Self::separate::<O, E>(Self::map::<Result<O, E>, A, Func>(func, fa))
84 }
85
86 /// Partitions a data structure based on a predicate.
87 ///
88 /// The default implementation uses [`partition_map`].
89 ///
90 /// **Note**: The return order is `(satisfied, not_satisfied)`, matching Rust's `Iterator::partition`.
91 /// This is achieved by mapping satisfied elements to `Ok` and unsatisfied elements to `Err` internally,
92 /// as `separate` returns `(Oks, Errs)`.
93 ///
94 /// ### Type Signature
95 ///
96 /// `forall f a. Filterable f => (a -> bool, f a) -> Pair (f a) (f a)`
97 ///
98 /// ### Type Parameters
99 ///
100 /// * `A`: The type of the elements in the structure.
101 /// * `Func`: The type of the predicate function.
102 ///
103 /// ### Parameters
104 ///
105 /// * `func`: The predicate function.
106 /// * `fa`: The data structure to partition.
107 ///
108 /// ### Returns
109 ///
110 /// A pair of data structures: the first containing elements that satisfy the predicate, and the second containing elements that do not.
111 ///
112 /// ### Examples
113 ///
114 /// ```
115 /// use fp_library::{brands::*, functions::*, types::*};
116 ///
117 /// let x = Some(5);
118 /// let Pair(satisfied, not_satisfied) = partition::<OptionBrand, _, _>(|a| a > 2, x);
119 /// assert_eq!(satisfied, Some(5));
120 /// assert_eq!(not_satisfied, None);
121 /// ```
122 fn partition<'a, A: 'a + Clone, Func>(
123 func: Func,
124 fa: Apply!(<Self as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>),
125 ) -> Pair<
126 Apply!(<Self as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>),
127 Apply!(<Self as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>),
128 >
129 where
130 Func: Fn(A) -> bool + 'a,
131 {
132 Self::partition_map(move |a| if func(a.clone()) { Ok(a) } else { Err(a) }, fa)
133 }
134
135 /// Maps a function over a data structure and filters out `None` results.
136 ///
137 /// The default implementation uses [`Functor::map`] and [`Compactable::compact`].
138 ///
139 /// ### Type Signature
140 /// ### Type Signature
141 ///
142 /// `forall f b a. Filterable f => (a -> Option b, f a) -> f b`
143 ///
144 /// ### Type Parameters
145 ///
146 /// * `B`: The type of the elements in the output structure.
147 /// * `A`: The type of the elements in the input structure.
148 /// * `Func`: The type of the function to apply.
149 /// ### Parameters
150 ///
151 /// * `func`: The function to apply to each element, returning an `Option`.
152 /// * `fa`: The data structure to filter and map.
153 ///
154 /// ### Returns
155 ///
156 /// A new data structure containing only the values where the function returned `Some`.
157 ///
158 /// ### Examples
159 ///
160 /// ```
161 /// use fp_library::{brands::*, functions::*};
162 ///
163 /// let x = Some(5);
164 /// let y = filter_map::<OptionBrand, _, _, _>(|a| if a > 2 { Some(a * 2) } else { None }, x);
165 /// assert_eq!(y, Some(10));
166 /// ```
167 fn filter_map<'a, B: 'a, A: 'a, Func>(
168 func: Func,
169 fa: Apply!(<Self as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>),
170 ) -> Apply!(<Self as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, B>)
171 where
172 Func: Fn(A) -> Option<B> + 'a,
173 {
174 Self::compact::<B>(Self::map::<Option<B>, A, Func>(func, fa))
175 }
176
177 /// Filters a data structure based on a predicate.
178 ///
179 /// The default implementation uses [`filter_map`].
180 ///
181 /// ### Type Signature
182 ///
183 /// `forall f a. Filterable f => (a -> bool, f a) -> f a`
184 ///
185 /// ### Type Parameters
186 ///
187 /// * `A`: The type of the elements in the structure.
188 /// * `Func`: The type of the predicate function.
189 ///
190 /// ### Parameters
191 ///
192 /// * `func`: The predicate function.
193 /// * `fa`: The data structure to filter.
194 ///
195 /// ### Returns
196 ///
197 /// A new data structure containing only the elements that satisfy the predicate.
198 ///
199 /// ### Examples
200 ///
201 /// ```
202 /// use fp_library::{brands::*, functions::*};
203 ///
204 /// let x = Some(5);
205 /// let y = filter::<OptionBrand, _, _>(|a| a > 2, x);
206 /// assert_eq!(y, Some(5));
207 /// ```
208 fn filter<'a, A: 'a + Clone, Func>(
209 func: Func,
210 fa: Apply!(<Self as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>),
211 ) -> Apply!(<Self as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>)
212 where
213 Func: Fn(A) -> bool + 'a,
214 {
215 Self::filter_map(move |a| if func(a.clone()) { Some(a) } else { None }, fa)
216 }
217}
218
219/// Partitions a data structure based on a function that returns a `Result`.
220///
221/// Free function version that dispatches to [the type class' associated function][`Filterable::partition_map`].
222///
223/// ### Type Signature
224///
225/// `forall f o e a. Filterable f => (a -> Result o e, f a) -> Pair (f o) (f e)`
226///
227/// ### Type Parameters
228///
229/// * `Brand`: The brand of the filterable structure.
230/// * `O`: The type of the success values.
231/// * `E`: The type of the error values.
232/// * `A`: The type of the elements in the input structure.
233/// * `Func`: The type of the function to apply.
234///
235/// ### Parameters
236///
237/// * `func`: The function to apply to each element, returning a `Result`.
238/// * `fa`: The data structure to partition.
239///
240/// ### Returns
241///
242/// A pair of data structures: the first containing the `Ok` values, and the second containing the `Err` values.
243///
244/// ### Examples
245///
246/// ```
247/// use fp_library::{brands::*, functions::*, types::*};
248///
249/// let x = Some(5);
250/// let Pair(oks, errs) = partition_map::<OptionBrand, _, _, _, _>(|a| if a > 2 { Ok(a) } else { Err(a) }, x);
251/// assert_eq!(oks, Some(5));
252/// assert_eq!(errs, None);
253/// ```
254pub fn partition_map<'a, Brand: Filterable, O: 'a, E: 'a, A: 'a, Func>(
255 func: Func,
256 fa: Apply!(<Brand as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>),
257) -> Pair<
258 Apply!(<Brand as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, O>),
259 Apply!(<Brand as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, E>),
260>
261where
262 Func: Fn(A) -> Result<O, E> + 'a,
263{
264 Brand::partition_map::<O, E, A, Func>(func, fa)
265}
266
267/// Partitions a data structure based on a predicate.
268///
269/// Free function version that dispatches to [the type class' associated function][`Filterable::partition`].
270///
271/// **Note**: The return order is `(satisfied, not_satisfied)`, matching Rust's `Iterator::partition`.
272///
273/// ### Type Signature
274///
275/// `forall f a. Filterable f => (a -> bool, f a) -> Pair (f a) (f a)`
276///
277/// ### Type Parameters
278///
279/// * `Brand`: The brand of the filterable structure.
280/// * `A`: The type of the elements in the structure.
281/// * `Func`: The type of the predicate function.
282///
283/// ### Parameters
284///
285/// * `func`: The predicate function.
286/// * `fa`: The data structure to partition.
287///
288/// ### Returns
289///
290/// A pair of data structures: the first containing elements that satisfy the predicate, and the second containing elements that do not.
291///
292/// ### Examples
293///
294/// ```
295/// use fp_library::{brands::*, functions::*, types::*};
296///
297/// let x = Some(5);
298/// let Pair(satisfied, not_satisfied) = partition::<OptionBrand, _, _>(|a| a > 2, x);
299/// assert_eq!(satisfied, Some(5));
300/// assert_eq!(not_satisfied, None);
301/// ```
302pub fn partition<'a, Brand: Filterable, A: 'a + Clone, Func>(
303 func: Func,
304 fa: Apply!(<Brand as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>),
305) -> Pair<
306 Apply!(<Brand as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>),
307 Apply!(<Brand as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>),
308>
309where
310 Func: Fn(A) -> bool + 'a,
311{
312 Brand::partition(func, fa)
313}
314
315/// Maps a function over a data structure and filters out `None` results.
316///
317/// Free function version that dispatches to [the type class' associated function][`Filterable::filter_map`].
318///
319/// ### Type Signature
320///
321/// `forall f b a. Filterable f => (a -> Option b, f a) -> f b`
322///
323/// ### Type Parameters
324///
325/// * `Brand`: The brand of the filterable structure.
326/// * `B`: The type of the elements in the output structure.
327/// * `A`: The type of the elements in the input structure.
328/// * `Func`: The type of the function to apply.
329///
330/// ### Parameters
331///
332/// * `func`: The function to apply to each element, returning an `Option`.
333/// * `fa`: The data structure to filter and map.
334///
335/// ### Returns
336///
337/// A new data structure containing only the values where the function returned `Some`.
338///
339/// ### Examples
340///
341/// ```
342/// use fp_library::{brands::*, functions::*};
343///
344/// let x = Some(5);
345/// let y = filter_map::<OptionBrand, _, _, _>(|a| if a > 2 { Some(a * 2) } else { None }, x);
346/// assert_eq!(y, Some(10));
347/// ```
348pub fn filter_map<'a, Brand: Filterable, B: 'a, A: 'a, Func>(
349 func: Func,
350 fa: Apply!(<Brand as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>),
351) -> Apply!(<Brand as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, B>)
352where
353 Func: Fn(A) -> Option<B> + 'a,
354{
355 Brand::filter_map::<B, A, Func>(func, fa)
356}
357
358/// Filters a data structure based on a predicate.
359///
360/// Free function version that dispatches to [the type class' associated function][`Filterable::filter`].
361///
362/// ### Type Signature
363///
364/// `forall f a. Filterable f => (a -> bool, f a) -> f a`
365///
366/// ### Type Parameters
367///
368/// * `Brand`: The brand of the filterable structure.
369/// * `A`: The type of the elements in the structure.
370/// * `Func`: The type of the predicate function.
371///
372/// ### Parameters
373///
374/// * `func`: The predicate function.
375/// * `fa`: The data structure to filter.
376///
377/// ### Returns
378///
379/// A new data structure containing only the elements that satisfy the predicate.
380///
381/// ### Examples
382///
383/// ```
384/// use fp_library::{brands::*, functions::*};
385///
386/// let x = Some(5);
387/// let y = filter::<OptionBrand, _, _>(|a| a > 2, x);
388/// assert_eq!(y, Some(5));
389/// ```
390pub fn filter<'a, Brand: Filterable, A: 'a + Clone, Func>(
391 func: Func,
392 fa: Apply!(<Brand as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>),
393) -> Apply!(<Brand as Kind!( type Of<'a, T: 'a>: 'a; )>::Of<'a, A>)
394where
395 Func: Fn(A) -> bool + 'a,
396{
397 Brand::filter(func, fa)
398}