Dynamic collection

code review
1

Is this an appropriate implementation of a dynamic collection? I'm aiming for a collection I can hold in some structs but where the struct is not generic over the collection. I had it previously implemented generically, but it really didn't make sense with e.g. this PowerSeries I have stubbed below.

I'm happy enough with a boxed iterator in the general Sequence trait and with boxing the trait itself in DynSequence. I would love if I could avoid the lifetimes especially in PowerSeries, but I can live with them. I just don't want them leaking too far.

use num::{One, Zero};

// Sequence

pub trait Sequence {

    /// Type for the terms of the `Sequence`
    type Term: Clone;

    /// Returns an iterator of Sequence terms
    fn terms(&self) -> Box<dyn Iterator<Item=Self::Term> + '_>;

    /// Is a finite sequence
    fn is_finite_sequence(&self) -> bool;

    // /// Truncates a Sequence and returns a Vec
    fn truncation(&self, len: usize) -> Vec<Self::Term>
    where Self: Clone {
        self.terms().take(len).collect::<Vec<_>>()
    }

}

// Sequence impls

impl<T> Sequence for Vec<T>
where T: Clone {
    type Term = T;
    fn terms(&self) -> Box<dyn Iterator<Item=T> + '_> {
        Box::new(self.iter().cloned())
    }
    fn is_finite_sequence(&self) -> bool {
        true
    }
}

impl<F, T> Sequence for F
where F: Fn(usize) -> T, T: Clone {
    type Term = T;
    fn terms(&self) -> Box<dyn Iterator<Item=T> + '_> {
        Box::new((0..).map(self))
    }
    fn is_finite_sequence(&self) -> bool {
        false
    }
}

// Dynamic Sequence

struct DynSequence<'a, T>(Box<dyn Sequence<Term=T> + 'a>) where T: Clone;

impl<'a, T> DynSequence<'a, T>
where T: Clone + 'a {
    pub fn new<S>(s: S) -> Self
    where S: Sequence<Term=T> + 'a {
        Self(Box::new(s))
    }
}

impl<'a, T> Sequence for DynSequence<'a, T>
where T: Clone {
    type Term = T;
    fn terms(&self) -> Box<dyn Iterator<Item=Self::Term> + '_> {
        self.0.terms()
    }
    fn is_finite_sequence(&self) -> bool {
        self.0.is_finite_sequence()
    }
}

// Client: PowerSeries

struct PowerSeries<'a, T>
where T: Clone + 'a {
    coefficients: DynSequence<'a, T>
}

impl<'a, T> PowerSeries<'a, T>
where T: Clone + 'a {

    /// Constructs a new `PowerSeries` with the given coefficients
    pub fn new<S>(coefficients: S) -> Self
    where S: Sequence<Term = T> + 'a {
        Self {
            coefficients: DynSequence::new(coefficients),
        }
    }

    pub fn is_finite(&self) -> bool {
        self.coefficients.is_finite_sequence()
    }

    /// Truncates the `PowerSeries` and returns a [`Polynomial`] with the given number of terms
    pub fn truncate(&self, num_terms: usize) -> PowerSeries<'_, T> {
        PowerSeries::new(self.coefficients.terms().take(num_terms).collect::<Vec<_>>())
    }

    fn eval(&self, x: T) -> Result<T, MyError>
    where T: Clone + Zero + One + std::ops::Mul<T, Output=T> {

        if (!self.coefficients.is_finite_sequence()) { return Err(MyError::InfiniteOperation) }

        let mut x_n = T::one();
        let mut sum = T::zero();
        for coefficient in self.coefficients.terms() {
            sum = sum + x_n.clone() * coefficient;
            x_n = x_n * x.clone();
        }

        Ok(sum)
    }

}


// Stubbed for the prototype

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
pub enum MyError {
    InfiniteOperation,
}
impl std::fmt::Display for MyError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::InfiniteOperation => write!(f, "Infinite operation"),
        }
    }
}
impl std::error::Error for MyError { }


// Usage

#[derive(Debug, Clone)]
struct Blah;
fn main() {
    let ps = PowerSeries::new(vec![Blah]);
    assert!(ps.is_finite());
    let ps = PowerSeries::new(vec![1; 5]);
    assert_eq!(ps.eval(2), Ok(1+2+4+8+16));
    assert_eq!(ps.truncate(3).eval(2), Ok(1+2+4));
}
2

There's a number of Clone and 'a bounds that could be removed.

You don't seem to need the coefficients field of PowerSeries to implement Sequence<..>. That is, you could replace DynSequence<'a, T> with Box<dyn Sequence<Term = T> + 'a> directly, and dispatch to the dyn Sequence<..>. I think all you'd lose is some potential ergonomics around DynSequence::new. And future compatibility if it's publically exposed, I suppose. Not a big deal either way.

Box<dyn Sequence<..> + '_> could implement Sequence<..> too, if that is required.

This:

    //              v---------------------------------------vv
    pub fn truncate(&self, num_terms: usize) -> PowerSeries<'_, T>

means "keep *self borrowed so long as the returned PowerSeries<..> is in use". But the current implementation doesn't actually need that, since it collects the iterator (it returns an erased Vec<T>). So this is more flexible for the caller...

    pub fn truncate<'t>(&self, num_terms: usize) -> PowerSeries<'t, T>
    where
        T: 't,

...but is a promise that you'll never capture self in the returned PowerSeries<..>, so consider if you want to make that promise or not.[1]

You need the lifetime in the iterator (if you want it to actually be lazy).

You could use 'static in PowerSeries instead. It will limit you to implementors of Sequence which are 'static (which implies Term: 'static too). On the other hand, if this is typically the case, consumers can just use 'static themselves (especially if you make the change to PowerSeries::truncate).

You could

struct PowerSeries<T, S = Vec<T>>
where
    S: Sequence<Term = T>,
{
    coefficients: S,
}

to "transform" the lifetime parameter into a type parameter, but that sounds like what you wanted to avoid.

  1. Maybe you want to return something that wraps the iterator and implements Sequence some day. ↩ī¸Ž

2 Likes
3

This is so great, I'll look through it carefully. Thanks!

4

The Box<dyn...> alternative was very helpful. I did want to call some other Sequence methods in PowerSeries, so I did impl Sequence for Box as you suggested. I started to have Sized trouble, but that impl cleaned up everything, it was great!

Great point about truncate, being more careful than me about it. I actually return a different struct there instead of PowerSeries but just turned it into PowerSeries for the post.