2 releases

0.1.1 Feb 25, 2024
0.1.0 Feb 25, 2024

#146 in Caching

43 downloads per month

MIT license

33KB
656 lines

lazy_list

This is a Rust crate that provides lazily-populated lists, finite or infinite.

See the documentation for usage info.


lib.rs:

This crate provides LazyList, A lazily-populated potentially-infinite list.

An LazyList<T, I> can be indexed and have its elements modified, similarly to a Vec<T>. However, elements are produced on-demand by a potentially-infinite iterator with type I which is specified upon creation of the LazyList. Once an element is produced, it is cached for later access.

If you don't want to specify an iterator type as a type parameter, you can use the LazyListBoxed or LazyListOwned type aliases.

LazyList is currently invariant, as opposed to covariant, if that matters to you.

An immutable LazyList is thread-safe.

Internally, LazyList stores elements in 64-element chunks. This is so that we can hand out references to elements, and not have them be invalidated as more elements are added to the cache.

Examples

Basic usage:

use lazy_list::LazyList;

// Finite list
let list: LazyList<i32, _> = LazyList::new(0..100);
assert_eq!(list.into_iter().sum::<i32>(), 4950);
// Infinite list
let list: LazyList<i32, _>  = LazyList::new(0..);
assert_eq!(list.into_iter().take(100).sum::<i32>(), 4950);

Mutation of an LazyList:

use lazy_list::LazyList;

let mut list = LazyList::new(0..);
assert_eq!(
    list.iter().take(10).copied().collect::<Vec<_>>(),
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
);
list[3] = 100;
assert_eq!(
    list.iter().take(10).copied().collect::<Vec<_>>(),
    [0, 1, 2, 100, 4, 5, 6, 7, 8, 9]
);

Reusing a static LazyList:

use lazy_list::{LazyList, LazyListOwned, IteratorLazyExt};
use once_cell::sync::Lazy;

// Note that each element will only ever be produced once.
static EVENS: Lazy<LazyListOwned<i32>> =
    Lazy::new(|| (0..).map(|x| x * 2).collect_lazy().boxed());

fn evens_with_property(mut predicate: impl FnMut(i32) -> bool) -> impl Iterator<Item = i32> {
    EVENS.iter().copied().filter(move |&x| predicate(x))
}

assert_eq!(
    evens_with_property(|x| x % 3 == 0)
        .take(5)
        .collect::<Vec<_>>(),
    [0, 6, 12, 18, 24]
);
assert_eq!(
    evens_with_property(|x| x % 5 == 0)
        .take(5)
        .collect::<Vec<_>>(),
    [0, 10, 20, 30, 40]
);

Recursive LazyList:

use lazy_list::{LazyList, LazyListBoxed};
use std::sync::Arc;

let fibonacci: Arc<LazyListBoxed<i32>> = LazyList::recursive(|fibonacci_ref, i| {
    if i < 2 {
        Some(1)
    } else {
        Some(fibonacci_ref[i - 1] + fibonacci_ref[i - 2])
    }
});
assert_eq!(
    fibonacci.iter().take(10).copied().collect::<Vec<_>>(),
    [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
);

No runtime deps