alux_traversable/traversable.rs
1use extend::ext;
2
3/// Extends optional values with traversal operations.
4#[ext(name = OptionTraversableExt)]
5pub impl<T> Option<T> {
6 /// Sequencing operation on [Option] type when inner type is `Applicative` or `Monad` like [Result].
7 /// See [sequence](OptionResultExt::sequence) for traverse with identity closure.
8 /// Defined by [Conor McBride](https://doi.org/10.1017/S0956796807006326) (2005) in Haskell2010 base
9 /// [Data.Traversable](https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html).
10 /// > **Traversable** structures support element-wise **sequencing** of **Applicative** effects
11 /// (thus also **Monad** effects) to construct new structures of the **same shape** as the input.
12 ///
13 /// ```hs
14 /// class (Functor t, Foldable t) => Traversable t where
15 /// traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
16 /// ```
17 /// From this Haskell definition `t` is [Option] and `f` is [Result].
18 ///
19 /// # Examples
20 ///
21 /// ```
22 /// use alux_traversable::*;
23 ///
24 /// let r: Result<_, ()> = Some(42).traverse(|x| Ok(x + 100));
25 ///
26 /// assert_eq!(r, Ok(Some(142)));
27 /// ```
28 #[inline]
29 fn traverse<F, R, E>(self, f: F) -> Result<Option<R>, E>
30 where
31 F: FnOnce(T) -> Result<R, E>,
32 {
33 // Traverse defined in terms of `sequence`.
34 // NOTE: Traversable minimal definition is `traverse` or `sequence` so only one needs to be
35 // implemented and other can be derived.
36 // https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html
37 // self.map(f).sequence()
38
39 // Or defined directly by pattern matching.
40 match self {
41 Some(t) => f(t).map(Some),
42 None => Ok(None),
43 }
44 }
45
46 /// Similar to [traverse](OptionTraversableExt::traverse), but with inner value wrapped inside
47 /// [Option] so it has effect of filtering None values.
48 ///
49 /// # Examples
50 ///
51 /// ```
52 /// use alux_traversable::*;
53 ///
54 /// let r: Result<_, ()> = Some(42).traverse_opt(|x| Ok(Some(x + 100)));
55 ///
56 /// assert_eq!(r, Ok(Some(142)));
57 /// ```
58 #[inline]
59 fn traverse_opt<F, R, E>(self, f: F) -> Result<Option<R>, E>
60 where
61 F: FnOnce(T) -> Result<Option<R>, E>,
62 {
63 // Traverse (opt) defined in terms of `sequence` (opt).
64 // NOTE: Traversable minimal definition is `traverse` or `sequence` so only one needs to be
65 // implemented and other can be derived.
66 // https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html
67 // self.map(f).sequence_opt()
68
69 // Or defined directly by pattern matching.
70 match self {
71 Some(t) => f(t),
72 None => Ok(None),
73 }
74 }
75}
76
77/// Extends optional results with sequencing.
78#[ext(name = OptionResultExt)]
79pub impl<T, E> Option<Result<T, E>> {
80 /// An alias for [transpose](Option::transpose), a _correct_ name for this function, although written for
81 /// the fixed data types ([Option] and [Result]). See also [traverse](OptionTraversableExt::traverse) variant
82 /// that accepts a mapping closure.
83 /// Defined by [Conor McBride](https://doi.org/10.1017/S0956796807006326) (2005) in Haskell2010 base
84 /// [Data.Traversable](https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html).
85 /// > **Traversable** structures support element-wise **sequencing** of **Applicative** effects
86 /// (thus also **Monad** effects) to construct new structures of the **same shape** as the input.
87 ///
88 /// ```hs
89 /// class (Functor t, Foldable t) => Traversable t where
90 /// sequence :: Applicative f => t (f a) -> f (t a)
91 /// ```
92 /// From this Haskell definition `t` is [Option] and `f` is [Result].
93 ///
94 /// # Examples
95 ///
96 /// ```
97 /// use alux_traversable::*;
98 ///
99 /// let r: Result<_, ()> = Some(Ok(42)).sequence();
100 ///
101 /// assert_eq!(r, Ok(Some(42)));
102 /// ```
103 #[inline]
104 fn sequence(self) -> Result<Option<T>, E> {
105 // 1. Sequence defined in terms of `traverse`.
106 // NOTE: Traversable minimal definition is `traverse` or `sequence` so only one needs to be
107 // implemented and other can be derived.
108 // https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html
109 // self.traverse(identity)
110
111 // 2. Sequence defined as alias for `Option::transpose`.
112 self.transpose()
113
114 // 3. Similar implementation as `Option::transpose`.
115 // match self {
116 // Some(r) => r.map(Some),
117 // // ^- Result::map (Functor)
118 // None => Ok(None),
119 // // ^- Result::pure (Applicative)
120 // }
121
122 // Other implementations using _fold_.
123
124 // 4. Using `fold` on [Option] type.
125 // self.into_iter().fold(Ok(None), |_, r| r.map(Some))
126
127 // 5. Using `unwrap` on [Option] type. Unwrap is fold in disguise!
128 // self.map(|r| r.map(Some)).unwrap_or_else(|| Ok(None))
129 }
130}
131
132/// Extends optional results containing optional values with filtered sequencing.
133#[ext(name = OptionResultOptionExt)]
134pub impl<T, E> Option<Result<Option<T>, E>> {
135 /// Similar to [sequence](OptionResultExt::sequence), but with inner value wrapped inside
136 /// [Option] so it has effect of filtering None values.
137 ///
138 /// # Examples
139 ///
140 /// ```
141 /// use alux_traversable::*;
142 ///
143 /// let r: Result<_, ()> = Some(Ok(Some(42))).sequence_opt();
144 ///
145 /// assert_eq!(r, Ok(Some(42)));
146 /// ```
147 #[inline]
148 fn sequence_opt(self) -> Result<Option<T>, E> {
149 // Sequence (opt) defined in terms of `traverse` (opt).
150 // NOTE: Traversable minimal definition is `traverse` or `sequence` so only one needs to be
151 // implemented and other can be derived.
152 // https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html
153 // self.traverse_opt(identity)
154
155 // Or defined directly by pattern matching.
156 match self {
157 Some(r) => Ok(r?),
158 None => Ok(None),
159 }
160 }
161}
162
163/// Extends iterators with traversal and sequencing operations.
164#[ext(name = IterTraversableExt)]
165pub impl<This> This
166where
167 This: Iterator,
168{
169 /// Sequencing operation on [Iterator] type when inner type is `Applicative` or `Monad` like [Result].
170 /// See [`IterTraversableExt::sequence`] for traverse with identity closure.
171 /// Defined by [Conor McBride](https://doi.org/10.1017/S0956796807006326) (2005) in Haskell2010 base
172 /// [Data.Traversable](https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html).
173 /// > **Traversable** structures support element-wise **sequencing** of **Applicative** effects
174 /// (thus also **Monad** effects) to construct new structures of the **same shape** as the input.
175 ///
176 /// ```hs
177 /// class (Functor t, Foldable t) => Traversable t where
178 /// traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
179 /// ```
180 /// From this Haskell definition `t` is [Iterator] and `f` is [Result].
181 ///
182 /// # Examples
183 ///
184 /// ```
185 /// use alux_traversable::*;
186 ///
187 /// let r: Result<_, ()> = [1, 2, 3].into_iter().traverse(|x| Ok(x + x));
188 ///
189 /// assert_eq!(r, Ok(vec![2, 4, 6]));
190 ///
191 /// let r: Result<_, ()> = Some(42).into_iter().traverse(|x| Ok(x + x));
192 ///
193 /// assert_eq!(r, Ok(vec![84]));
194 /// ```
195 #[inline]
196 fn traverse<F, T, R, E>(self, f: F) -> Result<Vec<R>, E>
197 where
198 This: Iterator<Item = T>,
199 F: FnMut(T) -> Result<R, E>,
200 {
201 // Traverse defined in terms of `sequence`.
202 // NOTE: Traversable minimal definition is `traverse` or `sequence` so only one needs to be
203 // implemented and other can be derived.
204 // https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html
205 // self.map(f).sequence()
206
207 // Or defined directly, which is what `sequence` here is anyway: collecting into one
208 // `Result` stops at the first error and sizes the vector from the iterator's own hint.
209 self.map(f).collect()
210 }
211
212 /// Sequencing operation on [Iterator] type when inner type is `Applicative` or `Monad` like [Result].
213 /// See [`IterTraversableExt::sequence`] for traverse with identity closure.
214 /// Defined by [Conor McBride](https://doi.org/10.1017/S0956796807006326) (2005) in Haskell2010 base
215 /// [Data.Traversable](https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html).
216 /// > **Traversable** structures support element-wise **sequencing** of **Applicative** effects
217 /// (thus also **Monad** effects) to construct new structures of the **same shape** as the input.
218 ///
219 /// ```hs
220 /// class (Functor t, Foldable t) => Traversable t where
221 /// traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
222 /// ```
223 /// From this Haskell definition `t` is [Iterator] and `f` is [Result].
224 ///
225 /// # Examples
226 ///
227 /// ```
228 /// use alux_traversable::*;
229 ///
230 /// let r: Result<_, ()> = [1, 2, 3].into_iter().traverse_iter(|x| Ok(Some(x + x)));
231 ///
232 /// assert_eq!(r, Ok(vec![2, 4, 6]));
233 ///
234 /// let r: Result<_, ()> = Some(42).into_iter().traverse_iter(|x| Ok(Some(x + x)));
235 ///
236 /// assert_eq!(r, Ok(vec![84]));
237 /// ```
238 #[inline]
239 fn traverse_opt<F, T, R, E>(self, mut f: F) -> Result<Vec<R>, E>
240 where
241 This: Iterator<Item = T>,
242 F: FnMut(T) -> Result<Option<R>, E>,
243 {
244 // Traverse defined in terms of `sequence`.
245 // NOTE: Traversable minimal definition is `traverse` or `sequence` so only one needs to be
246 // implemented and other can be derived.
247 // https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html
248 // self.map(f).sequence_opt()
249
250 // Or defined directly by pattern matching.
251 let mut acc = vec![];
252 for x in self {
253 if let Some(r) = f(x)? {
254 acc.push(r);
255 }
256 }
257 Ok(acc)
258 }
259
260 /// The same as [`IterTraversableExt::traverse_opt`], but accepts more general result
261 /// value as `Iterator`.
262 ///
263 /// NOTE: The end goal is to have general definition like this for traverse/sequence of Traversable interface (API).
264 ///
265 /// # Examples
266 ///
267 /// ```
268 /// use alux_traversable::*;
269 ///
270 /// let r: Result<_, ()> = [1, 2, 3].into_iter().traverse_iter(|x| Ok(Some(x + x)));
271 ///
272 /// assert_eq!(r, Ok(vec![2, 4, 6]));
273 ///
274 /// let r: Result<_, ()> = [1, 2, 3].into_iter().traverse_iter(|x| Ok(vec![x, x + x]));
275 ///
276 /// assert_eq!(r, Ok(vec![1, 2, 2, 4, 3, 6]));
277 /// ```
278 #[inline]
279 fn traverse_iter<F, T, I, R, E>(self, mut f: F) -> Result<Vec<R>, E>
280 where
281 This: Iterator<Item = T>,
282 F: FnMut(T) -> Result<I, E>,
283 I: IntoIterator<Item = R>,
284 {
285 // Traverse defined in terms of `sequence`.
286 // NOTE: Traversable minimal definition is `traverse` or `sequence` so only one needs to be
287 // implemented and other can be derived.
288 // https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html
289 // self.map(f).sequence_iter()
290
291 // Or defined directly by pattern matching.
292 let mut acc = vec![];
293 for x in self {
294 acc.extend(f(x)?);
295 }
296 Ok(acc)
297 }
298
299 /// Sequencing operation on [Iterator] type when inner type is `Applicative` or `Monad` like [Result].
300 /// See [`IterTraversableExt::sequence`] for traverse with identity closure.
301 /// Defined by [Conor McBride](https://doi.org/10.1017/S0956796807006326) (2005) in Haskell2010 base
302 /// [Data.Traversable](https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html).
303 /// > **Traversable** structures support element-wise **sequencing** of **Applicative** effects
304 /// (thus also **Monad** effects) to construct new structures of the **same shape** as the input.
305 ///
306 /// ```hs
307 /// class (Functor t, Foldable t) => Traversable t where
308 /// traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
309 /// ```
310 /// From this Haskell definition `t` is [Iterator] and `f` is [Result].
311 ///
312 /// # Examples
313 ///
314 /// ```
315 /// use alux_traversable::*;
316 ///
317 /// let r: Result<_, ()> = [Ok(1), Ok(2), Ok(3)].into_iter().sequence();
318 ///
319 /// assert_eq!(r, Ok(vec![1, 2, 3]));
320 /// ```
321 #[inline]
322 fn sequence<T, E>(self) -> Result<Vec<T>, E>
323 where
324 This: Iterator<Item = Result<T, E>>,
325 {
326 // Sequence defined in terms of `traverse`.
327 // NOTE: Traversable minimal definition is `traverse` or `sequence` so only one needs to be
328 // implemented and other can be derived.
329 // https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html
330 // self.traverse(identity)
331
332 self.collect()
333 }
334
335 /// Sequencing operation on [Iterator] type when inner type is `Applicative` or `Monad` like [Result].
336 /// See [`IterTraversableExt::sequence`] for traverse with identity closure.
337 /// Defined by [Conor McBride](https://doi.org/10.1017/S0956796807006326) (2005) in Haskell2010 base
338 /// [Data.Traversable](https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html).
339 /// > **Traversable** structures support element-wise **sequencing** of **Applicative** effects
340 /// (thus also **Monad** effects) to construct new structures of the **same shape** as the input.
341 ///
342 /// ```hs
343 /// class (Functor t, Foldable t) => Traversable t where
344 /// traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
345 /// ```
346 /// From this Haskell definition `t` is [Iterator] and `f` is [Result].
347 ///
348 /// # Examples
349 ///
350 /// ```
351 /// use alux_traversable::*;
352 ///
353 /// let r: Result<_, ()> = [Ok(Some(1)), Ok(Some(2)), Ok(None), Ok(Some(3))].into_iter().sequence_opt();
354 ///
355 /// assert_eq!(r, Ok(vec![1, 2, 3]));
356 /// ```
357 #[inline]
358 fn sequence_opt<T, E>(self) -> Result<Vec<T>, E>
359 where
360 This: Iterator<Item = Result<Option<T>, E>>,
361 {
362 // Sequence (opt) defined in terms of `traverse` (opt).
363 // NOTE: Traversable minimal definition is `traverse` or `sequence` so only one needs to be
364 // implemented and other can be derived.
365 // https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html
366 // self.traverse_opt(identity)
367
368 let mut acc = vec![];
369 for x in self {
370 if let Some(r) = x? {
371 acc.push(r);
372 }
373 }
374 Ok(acc)
375 }
376
377 /// The same as [`IterTraversableExt::sequence_opt`], but accepts more general result
378 /// value as `Iterator`.
379 ///
380 /// NOTE: The end goal is to have general definition like this for traverse/sequence of Traversable interface (API).
381 ///
382 /// # Examples
383 ///
384 /// ```
385 /// use alux_traversable::*;
386 ///
387 /// let r: Result<_, ()> = [Ok(Some(1)), Ok(Some(2)), Ok(None), Ok(Some(3))].into_iter().sequence_iter();
388 ///
389 /// assert_eq!(r, Ok(vec![1, 2, 3]));
390 ///
391 /// let r: Result<_, ()> = [Ok(vec![1, 2]), Ok(vec![]), Ok(vec![3])].into_iter().sequence_iter();
392 ///
393 /// assert_eq!(r, Ok(vec![1, 2, 3]));
394 /// ```
395 #[inline]
396 fn sequence_iter<T, I, E>(self) -> Result<Vec<T>, E>
397 where
398 This: Iterator<Item = Result<I, E>>,
399 I: IntoIterator<Item = T>,
400 {
401 // Sequence defined in terms of `traverse`.
402 // NOTE: Traversable minimal definition is `traverse` or `sequence` so only one needs to be
403 // implemented and other can be derived.
404 // https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Traversable.html
405 // self.traverse_iter(identity)
406
407 // Or defined directly by pattern matching.
408 let mut acc = vec![];
409 for x in self {
410 acc.extend(x?);
411 }
412 Ok(acc)
413 }
414}
415
416#[cfg(test)]
417mod tests {
418 use super::*;
419
420 #[test]
421 fn test_traverse() {
422 // Result Ok
423
424 for input in [Some(42), None] {
425 let res: Result<_, ()> = input.traverse(Ok);
426
427 assert_eq!(res, Ok(input));
428 }
429
430 let res: Result<Option<i32>, ()> = None.traverse(|()| Err(()));
431
432 assert_eq!(res, Ok(None));
433
434 // Result Err
435
436 let res: Result<Option<i32>, ()> = Some(42).traverse(|_| Err(()));
437
438 assert_eq!(res, Err(()));
439 }
440
441 #[test]
442 fn test_traverse_opt() {
443 // Result Ok
444
445 let res: Result<_, ()> = Some(42).traverse_opt(|x| Ok(Some(x + x)));
446
447 assert_eq!(res, Ok(Some(84)));
448
449 let res: Result<_, ()> = Option::<i32>::None.traverse_opt(|x| Ok(Some(x + x)));
450
451 assert_eq!(res, Ok(None));
452
453 let res: Result<Option<i32>, ()> = Some(42).traverse_opt(|_| Ok(None));
454
455 assert_eq!(res, Ok(None));
456
457 let res: Result<Option<i32>, ()> = None.traverse_opt(|_: u32| Err(()));
458
459 assert_eq!(res, Ok(None));
460
461 // Result Err
462
463 let res: Result<Option<i32>, ()> = Some(42).traverse_opt(|_| Err(()));
464
465 assert_eq!(res, Err(()));
466 }
467
468 #[test]
469 fn test_traverse_iter() {
470 // Result Ok
471 let input_vec = [vec![1, 2], vec![], vec![3]];
472 let input_opt = [Some(1), Some(2), None, Some(3)];
473
474 let res_vec: Result<Vec<i32>, ()> =
475 input_vec.clone().into_iter().traverse_iter(|xs| Ok(xs.into_iter().map(|x| x + x)));
476
477 let res_opt: Result<Vec<i32>, ()> = input_opt.into_iter().traverse_iter(|_| Ok(vec![].into_iter()));
478
479 assert_eq!(res_vec, Ok(vec![2, 4, 6]));
480 assert_eq!(res_opt, Ok(vec![]));
481
482 // Simplest error
483 let err = Result::<Vec<i32>, ()>::Err(());
484
485 // Traverse empty
486 let res_vec: Result<Vec<i32>, ()> = [].into_iter().traverse_iter(|_: i32| err.clone());
487 let res_opt: Result<Vec<i32>, ()> = None.into_iter().traverse_iter(|_: i32| err.clone());
488
489 assert_eq!(res_vec, Ok(vec![]));
490 assert_eq!(res_opt, Ok(vec![]));
491
492 // Result Err
493
494 let res_vec: Result<Vec<i32>, ()> = [1].into_iter().traverse_iter(|_| err.clone());
495 let res_opt: Result<Vec<i32>, ()> = Some(1).into_iter().traverse_iter(|_| err.clone());
496
497 assert_eq!(res_vec, Err(()));
498 assert_eq!(res_opt, Err(()));
499 }
500
501 #[test]
502 fn test_sequence() {
503 for (input, expected) in [
504 // Result Ok
505 (Some(Ok(42)), Ok(Some(42))),
506 (None, Ok(None)),
507 // Result Err
508 (Some(Err(())), Err(())),
509 ] {
510 let res = input.sequence();
511
512 assert_eq!(res, expected);
513 }
514 }
515
516 #[test]
517 fn test_sequence_opt() {
518 for (input, expected) in [
519 // Result Ok
520 (Some(Ok(Some(42))), Ok(Some(42))),
521 (Some(Ok(None)), Ok(None)),
522 (None, Ok(None)),
523 // Result Err
524 (Some(Err(())), Err(())),
525 ] {
526 let res = input.sequence_opt();
527
528 assert_eq!(res, expected);
529 }
530 }
531
532 #[test]
533 fn test_sequence_iter() {
534 for (input_vec, input_opt, expected) in [
535 // Result Ok
536 (
537 // Input Vec
538 vec![Ok(vec![1, 2]), Ok(vec![]), Ok(vec![3])],
539 // Input Option
540 vec![Ok(Some(1)), Ok(Some(2)), Ok(None), Ok(Some(3))],
541 // Expected result
542 Ok(vec![1, 2, 3]),
543 ),
544 (vec![Ok(vec![])], vec![Ok(None)], Ok(vec![])),
545 // Result Err
546 (vec![Err(())], vec![Err(())], Err(())),
547 ] {
548 let res_vec = input_vec.into_iter().sequence_iter();
549 let res_opt = input_opt.into_iter().sequence_iter();
550
551 assert_eq!(res_vec, expected);
552 assert_eq!(res_opt, expected);
553 }
554 }
555}
556
557#[cfg(test)]
558mod iterator_instance_tests {
559 use super::IterTraversableExt;
560
561 #[test]
562 fn iterator_traverse_preserves_shape_and_error() {
563 let success: Result<Vec<_>, ()> = [1, 2, 3].into_iter().traverse(|x| Ok(x + x));
564 assert_eq!(success, Ok(vec![2, 4, 6]));
565
566 let empty: Result<Vec<i32>, ()> = [].into_iter().traverse(|x: i32| Ok(x));
567 assert_eq!(empty, Ok(vec![]));
568
569 let failure: Result<Vec<i32>, ()> = [1].into_iter().traverse(|_| Err(()));
570 assert_eq!(failure, Err(()));
571
572 let mut total = 0;
573 let stateful: Result<Vec<_>, ()> = [1, 2, 3].into_iter().traverse(|value| {
574 total += value;
575 Ok(total)
576 });
577 assert_eq!(stateful, Ok(vec![1, 3, 6]));
578 }
579
580 #[test]
581 fn iterator_traverse_opt_filters_none_and_preserves_error() {
582 let success: Result<Vec<_>, ()> = [Some(1), None, Some(3)].into_iter().traverse_opt(Ok);
583 assert_eq!(success, Ok(vec![1, 3]));
584
585 let failure: Result<Vec<i32>, ()> = [1].into_iter().traverse_opt(|_| Err(()));
586 assert_eq!(failure, Err(()));
587 }
588
589 #[test]
590 fn iterator_sequence_preserves_shape_and_error() {
591 let success = [Ok(1), Ok(2), Ok(3)].into_iter().sequence();
592 assert_eq!(success, Ok::<_, ()>(vec![1, 2, 3]));
593
594 let failure = [Ok(1), Err(()), Ok(3)].into_iter().sequence();
595 assert_eq!(failure, Err(()));
596 }
597
598 #[test]
599 fn iterator_sequence_opt_filters_none_and_preserves_error() {
600 let success = [Ok(Some(1)), Ok(None), Ok(Some(3))].into_iter().sequence_opt();
601 assert_eq!(success, Ok::<_, ()>(vec![1, 3]));
602
603 let failure = [Ok(Some(1)), Err(())].into_iter().sequence_opt();
604 assert_eq!(failure, Err(()));
605 }
606}