As an example of collection that doesn't have iterator, it could be a proxy collection backed by database, where iterator just useless, you could check the size, but iterator could be useless itself.
For stack data structure, technically you can implement iterator, but it meaningless.
I can think of several NoSQL databases that do offer iterators over every entry of the database. For stacks... why would it be meaningless to, say, iterate over the stack by repeatedly popping and returning the top element until none are left?
Is something like the following what you wanted?
trait Collection {
type Iter<'a>: Iterator
where
Self: 'a;
fn size(&self) -> usize {
self.iterator().count()
}
fn iterator(&self) -> Self::Iter<'_>;
}
impl<T, const N: usize> Collection for [T; N] {
type Iter<'a> = core::slice::Iter<'a, T>
where
T: 'a;
fn size(&self) -> usize {
N
}
fn iterator(&self) -> Self::Iter<'_> {
self.iter()
}
}
Though, truly, this particular trait has no reason to exist. The following suffices:
fn size<T: IntoIterator>(collection: T) -> usize {
let iter = collection.into_iter();
if let (min, Some(max)) = iter.size_hint() && min == max {
min
} else {
iter.count()
}
}
(or, of course, rely on the fact that Vec<T>, [T; N], etc, override the implementation of .count() to be performant exactly like the C++ code.)
That's a lie. Base class couldn't have any “knowledge” thus I would assume that creator of base class has limited knowledge about concrete implementation… and I would say that LSP demands that creator of such class should be able to list any and all properties in any and all programs that said class would participate in. Only then you can list all these ϕ that are critical for LSP.
That's, of course, outrageous and impossible demand and thus OOP tutorials and coaches say that “you will get it in a time”, and “practice would help you”.
This works, to some extend, but that's far cry from saying that “OOP requires limited knowledge”. OOP requires faith not knowledge, in practice. Sometimes that faith is justified, often it's not working… but that's always blamed on the lack of experience, OOP believer never are allowed to look on the elephant in the room.
Maybe, but the main question: do you even want that flexibility or not. I had similar discussion with one developer who was telling me that statically typed languages are completely unsuitable for enterprise applications because they don't allow you to write code that would satisfy contradictory requirements — and according to said guy real business requirements are often contradictory and you need “soft skills” to implement them (as in: no matter what you write program would be violating something if requirements are contradictory and you have to convince the business that what you have done is what business wanted).
OOP, in practice, is precisely that: we ignore requirements that can make it sound and start builging the Jenga tower of classes before we know all the requirements — then try to shoehorn what we got from business into that.
Rust,. for better or for worse, is different. The main idea of the Rust is “you have to know what you want to build before you start building… if you have no idea where you are going then don't even start”.
Collection is a wrong design approach for Rust. Traits are not abstract base classes.
Traits don't describe what an object is. Traits describe what functionality is required by generic functions - what can you do with a type.
A function with a requirement of "I need a collection" is vague and inflexible, because it can only use the lowest common denominator functionality of any collection. Rust functions make it more specific, like "I need something cloneable that I can iterate over" or "I need a type that can be sent to another thread and serialized" or "I need a type that can be constructed from key-value pairs" or "I need a type that stores data as a contiguous slice of bytes".
Yes, because you are checking at compile time if something has a size method, right?
This sort of typing isn't supported in Rust, but probably supported in Rust macros.
What you are saying is basicly: There is something that might have method size or methods begin and end. We call size if it does or manually iterate over to get a size (which can be pretty slow by the way: imagine you've got an iterator for the whole filesystem, there is one in C++).
So what do we call "A collection"? It is something that has:
Are you agree with this defintion?
In Rust you could create a enum to describe both cases or use polymorphism e.g:
trait CollectionWithLen {
fn get_len(&mut self) -> usize;
}
struct VectorCollection<T>(Vec<T>);
impl<T> CollectionWithLen for VectorCollection<T> {
fn get_len(&mut self) -> usize {
self.0.len()
}
}
struct IterBasedCollection<T, I: Iterator<Item = T>>(I);
impl<T, I: Iterator<Item = T>> CollectionWithLen for IterBasedCollection<T, I> {
fn get_len(&mut self) -> usize {
let mut n = 0usize;
while self.0.next().is_some() {
n += 1;
}
n
}
}
fn do_all(col: &mut dyn CollectionWithLen) {
println!("We have {} items", col.get_len());
}
fn main() {
let vec1 = vec![1, 2, 3];
let mut len_based_coll = VectorCollection { 0: vec![1, 2, 3] };
let mut iter_based_coll = IterBasedCollection { 0: vec1.iter() };
do_all(&mut len_based_coll);
do_all(&mut iter_based_coll);
}
You example not complete, you simplified that, but enterprise about managing complexity, when it is unavoidable.
You written this:
trait CollectionWithLen {
fn get_len(&mut self) -> usize;
}
But what I did in my example:
interface Collection {
int size();
Iterator iterator();
}
You made a shortcut by removing Iterator iterator(); from your trait.
If you try to bring back Iterator iterator(); - you'll see the difference.
what do you mean by Iterator iterator() ?
do you mean
into_iter(self) -> impl Iterator<Item = T>>,iter(&self) -> impl Iterator<Item = &T>>,iter_mut(&mut self) -> impl Iterator<Item = &mut T>>,Just in case there's any confusion... you're aware that ExactSizeIterator::len is supposed to be O(1), and Iterator::count is sometimes O(1) instead of O(n)?
Maybe you were using size and iterator as toy examples, but otherwise, this case really can just be solved through iterator interfaces alone.
Something close to this: Iterator (Java Platform SE 8 )
Why is it bad? If you really, truly, care, you could make a Collection wrapper interface whose sole implementation uses IntoIterator to implement it, but ???
Abstraction for the point of abstraction is not good enterprise code. Throwing in extra interfaces is not free; at the very least it increases the complexity of the code (thereby hurts readability), and it isn't guaranteed to stop different parts of the codebase from being coupled together.
Is Itertools an example of bad design, because it offers more utilities than raw iteration?
Iterator should be used only to iterate - everything else are examples of bad design.
https://en.wikipedia.org/wiki/Unix_philosophy#Do_One_Thing_and_Do_It_Well
https://en.wikipedia.org/wiki/Single-responsibility_principle
https://en.wikipedia.org/wiki/SOLID#Single_responsibility_principle
If you don't believe me, that check this article about what iterator is:
https://en.wikipedia.org/wiki/Iterator
Definition from Wikipedia:
In computer programming, an iterator is an object that progressively provides access to each item of a collection, in order.[1][2][3]
Similar definition can be find in GoF design patterns by Erich Gamma
i am very worried that your lack of knowledge of mutability, traits, and the place of iterators in rust is hindering the current conversation, so i wouldadvise that you try to read the book to understand more.
that being said, an implementation that would do roughly what you want would be :
trait Collection {
type ItemRef<'a> where Self : 'a;
type ItemMut<'a> where Self : 'a;
type Iter<'a> : Iterator<Item = Self::ItemRef<'a>> where Self : 'a;
type IterMut<'a> : Iterator<Item = Self::ItemMut<'a>> where Self : 'a;
fn size(&self) -> usize;
fn iter(&self) -> Self::Iter<'_>;
fn iter_mut(&mut self) -> Self::IterMut<'_>;
}
i added both iter and iter_mut because all good rust collections (at least all the ones in std) have both
simply adding
impl<C : ?Sized> Collection for C
where
for<'a> &'a C : IntoIterator,
for<'a> &'a mut C : IntoIterator,
{
type ItemRef<'a> = <&'a C as IntoIterator>::Item where Self : 'a;
type ItemMut<'a> = <&'a mut C as IntoIterator>::Item where Self : 'a;
type Iter<'a> = <&'a C as IntoIterator>::IntoIter where Self : 'a;
type IterMut<'a> = <&'a mut C as IntoIterator>::IntoIter where Self : 'a;
fn size(&self) -> usize { self.iter().count() }
fn iter(&self) -> Self::Iter<'_> { self.into_iter() }
fn iter_mut(&mut self) -> Self::IterMut<'_> { self.into_iter() }
}
would give you an optimal implementation for all collections i am aware of
I value performance, ergonomics, and low coupling above splitting things into different interfaces. (Of course, splitting things into different interfaces can be necessary for those three goals.) Note that the goal of the single responsibility principle, as far as I'm aware, is to reduce coupling. If two interfaces are still extremely linked together, then the single responsibility principle shouldn't be used to blindly justify splitting what could be one interface into two.
Using size as property of iterator is example of bad design.
Already replied why so:
https://users.rust-lang.org/t/rust-for-enterprise-grade-systems/142643/33?u=amid.ukr
How would you implement same problem, but you iterator do only what iterator intended to do, to iterate only.
Definition from Wikipedia:
In computer programming, an iterator is an object that progressively provides access to each item of a collection, in order.[1][2][3]
https://en.wikipedia.org/wiki/Iterator
Let's not make another shortcuts, by adding properties that not supposed to be there, but work with exact definitions of things.
But what I did in my example:
interface Collection {
int size();
Iterator iterator();
}
So every collection has both an iterator and a size, right?
Why not use size then?
But let's get back to my original question:
What is a collection and which operations does it support?
no it is not. rust is not java. you clearly have no idea what you are talking about, and i would again advise you to read the book.
you say you want a trait that combines iterator and size.
if a type implements for<'a> &'a Self : IntoIterator, then the most efficient way to get the size is always <&Self as IntoIterator>::into_iter(&self).count(), so that is what we should do.
but if you want to make your life harder for yourself to follow what you read wikipedia without actually understanding how rust works, you can just not have the implementation block i share, and just implement the trait manually yourself, like so
impl<T> Collection for Vec<T>
{
type ItemRef<'a> = &'a T where T : 'a;
type ItemMut<'a> = &'a mut T where T : 'a;
type Iter<'a> = std::slice::Iter<'a, T> where T : 'a;
type IterMut<'a> = std::slice::IterMut<'a, T> where T : 'a;
fn size(&self) -> usize { self.len() /* no iterator */ }
fn iter(&self) -> Self::Iter<'_> { self.into_iter() }
fn iter_mut(&mut self) -> Self::IterMut<'_> { self.into_iter() }
}
impl<T> Collection for [T]
{
type ItemRef<'a> = &'a T where T : 'a;
type ItemMut<'a> = &'a mut T where T : 'a;
type Iter<'a> = std::slice::Iter<'a, T> where T : 'a;
type IterMut<'a> = std::slice::IterMut<'a, T> where T : 'a;
fn size(&self) -> usize { self.len() /* no iterator */ }
fn iter(&self) -> Self::Iter<'_> { self.into_iter() }
fn iter_mut(&mut self) -> Self::IterMut<'_> { self.into_iter() }
}
impl<K,V> Collection for std::collections::HashMap<K,V>
{
type ItemRef<'a> = (&'a K, &'a V) where (K,V) : 'a;
type ItemMut<'a> = (&'a K, &'a mut V) where (K,V) : 'a;
type Iter<'a> = std::collections::hash_map::Iter<'a, K,V> where (K,V) : 'a;
type IterMut<'a> = std::collections::hash_map::IterMut<'a, K,V> where (K,V) : 'a;
fn size(&self) -> usize { self.len() /* no iterator */ }
fn iter(&self) -> Self::Iter<'_> { self.into_iter() }
fn iter_mut(&mut self) -> Self::IterMut<'_> { self.into_iter() }
}
You can read from it as much as you want until you write to it, so it isn't a sink either.
You're getting a lot of feedback about why this is not true in Rust. My opinion is a little different. I think you're right that creating an iterator to get the size for generic collections is awkward. I can understand why you say it's bad design.
The reason this isn't considered a problem, is that the need to use collections generically rarely, if ever, comes up. Of course, one obvious need is to have an "interface" for sets of values that are iterable. However, Rust does have this via the IntoIterator trait. The question is, what is needed beyond that? I don't think just getting the size is enough to justify a use case for a generic collection interface. Perhaps there is a corner case for this, but I think the more important question is: what about other methods that would be useful?
You probably wouldn't normally want to treat maps and lists generically, for example. In Java (which I used for over 20 years), I almost never used collections generically. I did (2 or 3 times) use the Collection interface, but then it was just to avoid naming a concrete class for sake of OO purity, i.e., I did not actually ever have a need to use a Collection method with two different concrete collection classes.
So I suggest asking yourself the same question and posting here: what specific use cases did you have in Java for using collections generically? If you list these, it may be productive to discuss how these are accomplished in Rust, and try to identify the cases that are not possible.