An iterator cannot return values whose lifetime is tied to the iterator itself. A streamer can. That is the fundamental difference. Removing the lifetime annotation defeats the purpose of a streamer, because the type of the element yielded cannot be parameterized by said lifetime.
Note the docs:
Some form of stream abstraction is inherently required for this crate because elements in a finite state transducer are produced by iterating over the structure. The alternative would be to create a new allocation for each element iterated over, which would be prohibitively expensive.
This hints that the iterator maintains an internal buffer. Each call to next lends a borrow to that buffer, which will prevent subsequent calls to next while that borrow exists. This would mean, for example, that a collect method on a streamer would need to require a Clone bound, which is not necessary for iterators as they exist today.
HKT plays into this because the various adapter methods fundamentally want to speak of the lifetime parameterization generically. But the lifetime is a type variable, which means you need polymorphic code over type constructions. Therefore, HKT.
So how is the example I posted not streaming? Run the code, and the output is interleaved as it should be, so it is operating as a stream processor. What is the additional requirement you are talking about?
To me it looks like it is transferring ownership, so it must return a copy as you cannot move out of a struct?
Regarding the borrowing, it is an additional requirement because it is not necessary in the definition of streaming filters, as you can see from the example posted, I can define a streaming filter without this. To me it seems you are not talking about a general streaming-iterator, but a specific one that has particular requirements regarding buffering.
Edit: I appreciate I asked for motivating examples of HKT, I mean this as an explanation of why what I implemented is not what was wanted. I don't mean to try and suggest the use case is not valid.
Note @keean means higher-ranked types, not higher-kinded types (HKT):
@keean knows this, but for other readers HKT applies to the design case where(1) the return type of trait method needs to match the Self type and where the trait has type parameter(s) (e.g. associated type parametrized by lifetime which is a type parameter of the Self type for an Iterator factory method):
(1) Note HKT generally apply in any case where we parametrize a type parameter of the trait (i.e. higher order constructors), not just when Self (which btw is a type parameter) is parametrized and used as a return type, but this latter case is probably the most prolific use case of HKT.
In Scala which has HKT, we can clearly see Self is a type parameter:
Note after @keean made a strong point as to why iterators are preferred over functors, I replied:
But then the first link in the quoted below on quick perusal hints of a way to combine the best of @keean's corountines insight with the best of composable pure functional composition, to offer a high-level way to manage lifetimes. I need to spend some more time study the information below to see if requires HKT or not, and identify its tradeoffs:
Edit: @BurntSushi's and from the other thread @arielb1's example use cases for iterators are requiring HKT because of the lifetime type parameter. Their type's constructors are not otherwise parametrized. Note collections will be parametrized on their element type, thus the Iterator trait's next method must be parametrized on the element type, so afaics this can also be implemented with a HKT independent of whether we model lifetimes. However, I see this case can also be accomplished with an associated type because Self's type constructor is not parametrized by the element Item type. But this means we have to write a new implementation for every element Item type we want to add to the collection. I don't see how a library of collections can be implemented with iterators without HKTs?
So, in the end higher-kinded typesplayed a smaller role than anticipated and implicits played a much larger role. Nevertheless, type constructor polymorphism did find a useful application niche inthe collections framework, where it came to generate factories for collection classes. This application worked out fine because setting up a factory by inheriting from a factory classwhich takes higher-kinded type parameters is done on a case-by-case basis
Yes, I realised that by having two discussions at once I had slipped from higher rank to higher kind. I was unsure if I should retitle the thread, but I became interested in the lifetime issue of the stream iterator.
There is a very simple solution and that is to switch to using write iterators, instead of read iterators.
In Haskell higher kinded types (for example a monad) would be written "m a" IE both the constructor and parameter are type variables. A generic function on a functor would be (Functor f) => f a -> f () so the type class constraint only applies to the constructor and we discard the type of the parameter replacing with void. We can tell from the signature this throws the data away.
I am sure someone else must have already done this in Rust, but I thought it useful to post the code. The HList paper I wrote with Oleg Kiselyov and Ralf Lemmel in 2004 used a lot of techniques like that in Haskell to do some interesting stuff. There was a follow up paper in 2005 called OOHaskell that I also contributed to, which builds up OO language features from a sound type system base.
I'm not sure what you are asking here? You want me to elaborate on what the simple solution is, or on what higher-kinded-types are? The reason I posted the Haskell signature for a functor is because I find the Rust and Scala syntax for generics where you have T<A> is not very good for HKT because you really want 'T' to be a type variable. This is most easily seen in HM type notation as "forall f a . Functor f => f a -> f a" which would be a function that takes a functor and returns (the same) functor. My understanding is that the higher-kinded part is because 'f' is a type variable so can vary over all functors, which very different from "forall a . MyFunctor a -> MyFunctor a" which is a function takes and returns a specific functor. Note this is all parametric polymorphism with no subtyping, just type constraints (with type-classes / traits). I find it very confusing looking at the Scala stuff with Super and Self mixed in, which I find very confusing as it is mixing models.
pub trait Streamer {
type Item;
fn next<'a>(&'a mut self) -> Option<&'a Self::Item>;
}
struct StreamSource {
counter : i32
}
impl Streamer for StreamSource {
type Item = i32;
fn next<'a>(&'a mut self) -> Option<&'a Self::Item> {
print!("[generate] ");
self.counter += 1;
Some(&self.counter)
}
}
fn stream_sink<S>(mut s : S) where S : Streamer, S::Item : std::fmt::Display {
for _ in 0..10 {
match s.next() {
Some(x) => println!("{}", x),
None => break
}
}
}
fn main() {
struct StreamAdd<S> where S : Streamer {
input : S,
add : S::Item,
buf : S::Item
}
impl<S> Streamer for StreamAdd<S>
where S : Streamer, for<'a> &'a <S as Streamer>::Item : std::ops::Add<Output = S::Item> {
type Item = S::Item;
fn next<'a>(&'a mut self) -> Option<&'a Self::Item> {
print!("[filter] ");
match self.input.next() {
Some(x) => {
self.buf = x + &self.add;
Some(&self.buf)
},
None => None
}
}
}
stream_sink(StreamAdd{input: StreamSource{counter : 0}, add : 10, buf : 0});
}
Each iterator has an internal buffer (in the example its an i32) and "next" lends a reference to the consumer. I have put the code in the playground here: Rust Playground
You're leaving out adapter methods (e.g., map). Without them, the abstraction is unwieldy and barely usable. For example, If I want to take a stream of &T and create a stream of (u32, &T), then that should totally be possible. But your trait definition precludes this by fixing the return type of next to be &U.
A small modification allows any type to be paired with the buffer (which could be a struct or tuple for example):
pub trait Streamer {
type Buffer;
type Item;
fn next<'a>(&'a mut self) -> Option<(Self::Item, &'a Self::Buffer)>;
}
struct StreamSource {
counter : i32
}
impl Streamer for StreamSource {
type Buffer = i32;
type Item = ();
fn next<'b>(&'b mut self) -> Option<(Self::Item, &'b Self::Buffer)> {
print!("[generate] ");
self.counter += 1;
Some(((), &self.counter))
}
}
fn stream_sink<S>(mut s : S)
where S : Streamer, S::Buffer : std::fmt::Display, S::Item : std::fmt::Display {
for _ in 0..10 {
match s.next() {
Some((x, y)) => println!("{} {}", x, y),
None => break
}
}
}
fn main() {
struct StreamAdd<S> where S : Streamer {
input : S,
add : S::Buffer,
}
impl<S> Streamer for StreamAdd<S>
where S : Streamer, for<'a> &'a <S as Streamer>::Buffer : std::ops::Add<Output = S::Buffer> {
type Item = S::Buffer;
type Buffer = S::Buffer;
fn next<'a>(&'a mut self) -> Option<(Self::Item, &'a Self::Buffer)> {
print!("[filter] ");
match self.input.next() {
Some((_, y)) => {
Some((y + &self.add, y))
},
None => None
}
}
}
stream_sink(StreamAdd{input: StreamSource{counter : 0}, add : 10});
}
If you consider the HKT suggested for the value returned from "next" Option<S::Item<'a>> it seems to me that this type must always forward the buffer, as you cannot ignore a lifetime parameter, so "S::Item" must include the buffer reference. On drawback of the above code is that you have to pass "()" if you have nothing other than the buffer to output from the stream filter. Playground link: Rust Playground
No, it doesn't. 'static could be used in the return type since 'static is a subtype of all other lifetimes.
I'm familiar with the work arounds to this problem, and we're falling into precisely the trap I warned about: we're getting into the weeds. My current understanding is that we can't have a streaming abstraction like I outlined with similar ergonomics as Iterator, and this is specifically because we lack HKT.
I also note that this isn't necessarily me arguing in favor of HKT either. Just pointing out one place where I miss it.
I find it interesting to consider where the limitations are, and the point of this was to discuss HKT (and HRT as I got those mixed up having two conversations at the same time). I am a little concerned that HKT or HRT will mess up monomorphisation, which is nicely modelled in Rust by using parametric (not universally quantified) types and traits/type-classes.
My understanding is that the parameterised type "Self::Item<_>" must use the type parameter, and it is an error to pass a parameter to a type that does not need one, and it is an error to create a type that takes a parameter and ignores it. Are you saying this is not true? Do you have an example?
I find the inclusion of subtyping for lifetimes to be somewhat problematic, parametric polymorphism for lifetimes would seem to be more in line with the rest of the type system.
Edit: I see what you are saying regarding subtyping, but Self::Item<'static> would still need a reference in that type to be assigned the 'static lifetime. So I agree its slightly more flexable, but the code I posted should allow map and other filters to be defined.
You're right about the type needing the parameter, yes.
I don't have enough implementation experience to say whether or how HKT will work itself out, my main concern is the complexity that it will add to the language itself and the corresponding libraries that leverage its power.
It's hard to see the syntax for HKT in Rust because you want the constructor (which comes before the parameters) to be a parameter. So:
f(x : Vec<Int>) // vector of ints
f<A>(x : Vec<A>) // type parameter
f<A>(x : A<Int>) // constructor parameter
The last of these is higher-kinded. I don't see how the example you gave is HKT, as there is no constructor parameter. It seems to me there is an implicit requirement for higher-ranked-types in there as well, and there is also some implicit universal quantification going on in Item, which you probably don't want as the default as it would change the meaning of existing programs.
