rspl/streams/
infinite_lists.rs

1//! This module provides the standard implementation of streams as infinite lists (the greatest fixpoint of `cons`ing).
2
3use super::Stream;
4
5use alloc::boxed::Box;
6
7/// [`Lazy<T>`] types thunks of type `T`.
8type Lazy<'a, T> = dyn FnOnce() -> T + 'a;
9
10/// [`InfiniteList<X>`] defines non-well-founded lists of type `X`.
11pub enum InfiniteList<'a, X: 'a> {
12    /// Constructing a new infinite list by prepending a new entry to an existing (lazy) infinite list.
13    Cons(X, Box<Lazy<'a, InfiniteList<'a, X>>>),
14}
15
16impl<'a, X> InfiniteList<'a, X> {
17    /// The same as [`InfiniteList::Cons`] but with boxing of `lazy_inflist` hidden to make the resulting code less verbose.
18    #[inline]
19    pub fn cons<T>(x: X, lazy_inflist: T) -> Self
20    where
21        T: FnOnce() -> Self + 'a,
22    {
23        InfiniteList::Cons(x, Box::new(lazy_inflist))
24    }
25}
26
27impl<'a, X> InfiniteList<'a, X> {
28    /// Create an infinte list of a certain constant.
29    /// - `x` is the constant.
30    ///
31    /// # Examples
32    ///
33    /// Creating an infinite list of `true`s:
34    ///
35    /// ```
36    /// let trues = rspl::streams::infinite_lists::InfiniteList::constant(true);
37    /// ```
38    pub fn constant(x: X) -> Self
39    where
40        X: Copy,
41    {
42        Self::Cons(x, Box::new(move || Self::constant(x)))
43    }
44}
45
46impl<'a, X> Stream<X> for InfiniteList<'a, X> {
47    /// Make the first list entry of `self` the head.
48    fn head(&self) -> &X {
49        match self {
50            Self::Cons(head, _) => head,
51        }
52    }
53
54    /// Make all but the first list entry of `self` the tail.
55    fn tail(self) -> Self {
56        match self {
57            Self::Cons(_, tail) => tail(),
58        }
59    }
60}
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    use crate::assert_head_eq;
67    use crate::assert_tail_starts_with;
68
69    #[test]
70    fn test_cons() {
71        assert!(matches!(
72            InfiniteList::cons((), || InfiniteList::constant(())),
73            InfiniteList::Cons(_, _)
74        ));
75    }
76
77    #[test]
78    fn test_constant() {
79        const X: bool = true;
80
81        let mut xs = InfiniteList::constant(X);
82        assert_head_eq!(xs, X);
83        assert_tail_starts_with!(xs, [X, X]);
84    }
85
86    #[test]
87    fn test_head() {
88        let inflist = InfiniteList::cons(true, || InfiniteList::constant(false));
89        assert!(inflist.head());
90    }
91
92    #[test]
93    fn test_tail() {
94        let inflist = InfiniteList::cons(false, || {
95            InfiniteList::cons(true, || InfiniteList::constant(true))
96        });
97        assert!(inflist.tail().head());
98    }
99}
rspl/streams/infinite_lists.rs

rspl/streams/
infinite_lists.rs
