Does rust really need higher kinded types?

[shelby3]

@BurntSushi

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.

@BurntSushi

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.

@BurntSushi

Yielded elements must be able to borrow from the streamer. (This is not an "additional" requirement. It's the requirement.)

@BurntSushi

@keean

To me it seems you are not talking about a general streaming-iterator, but a specific one that has particular requirements regarding buffering.

I want an abstraction that lets me write iterators whose elements can be borrowed from the iterator.

Note after @keean made a strong point as to why iterators are preferred over functors, I replied:

@shelby3

On superficial reading, that seems to be an excellent, composable abstraction which solves both the uncontrollable implicit side-effects of laziness and the inefficiency of an eager functor.

So thus a functor is not a granular enough abstraction and thus premature specialization.

[...]I now see that the low-level generality is the only abstraction will solves all the algorithmic issues. So thus while a functor gives us some higher-level insight/transparency on the composability of the operations driving the result and shields us from managing the lifetimes of the iteration structures in user land code, it loses the granularity to control the laziness locally and optimize the efficiency of the eager locality. The co-routine can abstract the eagerness to laziness while retaining the locality between some and find without infecting the type system or collections with lazy versus eagerness.

So although we would no longer need higher-kinds for functors, we might need them for iterator factories on the collection trait.

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:

@kirillkh

There is some work on ways to iterate collections that might be relevant to the discussion:
http://okmij.org/ftp/papers/LL3-collections-enumerators.txt
Generators: yield = exceptions + non-determinism
Streams and Incremental Processing

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?

Even with all the hackery in Scala's collection class library (which has proven to be brittle with corner cases), they still had to use HKT's for the factories:

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