Does rust really need higher kinded types?

[BurntSushi]

@keean

What is the additional requirement you are talking about?

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

[keean]

So I am confused by the type signature of next:

fn next(&mut self) -> Option<Self::Item>;

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.

[BurntSushi]

That is not the right definition. You removed the lifetime annotation. Here's the trait:

pub trait Streamer<'a> {
    type Item: 'a;
    fn next(&'a mut self) -> Option<Self::Item>;
}

In some world where HKT exists, the trait definition might look like:

pub trait Streamer {
    type Item;
    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
}

But this is polymorphic code on type constructors, where Self::Item is a type constructor.

@keean

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.

You asked for examples where HKT was needed. I gave you a link to a use case. Your code does not apply to my use case.

@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.

[shelby3]

@keean

A number of threads (including the most desired features thread) have suggested that Rust needs higher-kinded-types.

Note @keean means higher-ranked types, not higher-kinded types (HKT):

@shelby3

I think you mean higher-ranked, not higher-kinded (refer to the quoted linked Scala example):

@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):

@shelby3

If I am not mistaken, a higher-kinded type is parametrization of a type parameter. The reason your first example is higher-kinded is because you require that the type parameter Iterator's lower bound Self::Iterator<'a> is a member of the implementating type Self. Thus you have parametrized the type parameter Self with the type parameter Iterator. If you had not required that Iterator to have a lower bound incorporating Self, then your example would not be higher-kinded.

@shelby3

Let's review why functors require higher-kinded types. Seems you are requiring something like the following (apologies if the Rust syntax isn't correct):

trait Functor {
type T;
fn map<A>(&self, T -> A) -> Self<T=A>;
}

We might contemplate to do instead the following which is not higher-kinded:

trait Functor {
type T;
fn map<A>(&self, T -> A) -> &Functor<T=A>;
}

So in other words, the trait object would maintain the runtime knowledge about what the implementing Self type is, which is not checked at compile time.

However, you are correct on this point, because the type signature of the alternative is not constrained to a functor.map operation, because there is no requirement that the return value have the same Self type. For example, the implementation could employ monoid.append to return a Functor which has a different Self type, e.g. convert from a Vec<T> to List<A>, which would violate the invariants of the category theory for a functor.

So thus you have pointed out an example of where we must have higher-kinded types.

I think we have shown that higher-kinded types are required when either we must restrict a trait type to a parametrization of the Self type for reasons of conformance to invariants (e.g. category theory for functors) or because we wish to forsake some generality in order to get more optimization (e.g. not using a trait object for an iterator, but where it is possible to get similar optimization using functors but these require higher-kinded types also and we might gain some other higher-level functional composition abstraction and control over resource management to avoid the low-level imperative approach).

---

(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:

trait Super[Self <: Super]

And can be HKT:

trait Super[T, Self[T] <: Super[T, Self]]

[shelby3]

@keean

Reposting the example from the linked discussion:

Friendly note, your example is the same solution I had posted earlier:

@shelby3

I understand we can emulate rank-2 (higher ranked) types in a language which doesn't explicitly support them via forall, by employing a trait with a method for generic parameter A, as explained in an example for Scala.

Compared to that linked Scala example, the example in this thread is not requiring a higher ranked type, because the Read trait lower bound is constant throughout the function f. Also afaics, the example in this thread does not require a higher-kinded type on the trait Fn in order to parameterize the lower bound on the type parameter A of Fn, i.e. requires a trait Fn<A> to be of the type trait Fn<Read>. Higher-kinded types are of the form trait HK<A, B<A>>.

[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

[keean]

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.

[keean]

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.

[shelby3]

@keean

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 genetic 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.

Could you elaborate? I am not following what is you are pointing out to us specifically and its relevance to the prior discussion.

[shelby3]

@keean

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.

I had cited that paper in my 2011 Stackoverflow Q & A on the Expression Problem. Just search for "HList".

[keean]

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.

[keean]

Here's my second attempt

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

[BurntSushi]

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.

[keean]

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

[BurntSushi]

@keean

If you consider the HKT suggested for the value returned from "next" Option> it seems to me that this type must always forward the buffer

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.

[keean]

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.

fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;

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.

[BurntSushi]

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.

[keean]

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.

[withoutboats]

@keean

I don't see how the example you gave is HKT, as there is no constructor parameter.

I have a little trouble following these threads, because people get a bit prolix, but I believe you're referring to this trait definition:

trait StreamingIterator {
    type Item;
    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
}

The associated type operator Item has the kind lifetime -> type. Item is applied to the lifetime 'a in its use during the next function, to create the type Item<'a>.

Obviously the syntax for declaring the "associated type operator" here is a bit dubious, but we have no syntax for this feature because this feature is not implemented!

Some of my own opinions about HKTs in Rust follow.

• It is interesting that Rust has two base kinds, type and lifetime. It introduces questions about making higher-kinded polymorphism practical, as in my next bullet point.
• The most serious outstanding questions about higher-kinded polymorphism in Rust have to do with how partial application would be handled, because currying is probably not a sufficient answer; there's a comment from Niko Matsakis about this somewhere which is enlightening.
• lifetime -> type associated type operators like StreamingIterator are the only use case for higher-kinded polymorphism I've seen that are uniquely useful for Rust; they also raise less implementation challenges than full-on higher-kinded polymorphism. The other use cases are just the standard Haskell/Scala Monad/Applicative/Functor chainsaw, which is powerful but empirically difficult pedagogically for many programmers. I think working on the minimal proposal for associated type operators would be a good use of someone's time.

[keean]

Okay I see where this came from now: " & " is a constuctor of kind " lifetime -> * -> * " and could be perhaps be written " Ref 'a b " in a more Haskell like way where constructors are capitalised and type variables a lower case (and borrowing the single quote prefix from Rust for a lifetime variable). " * " is traditional for the kind of a type, you might use " & " for the kind of a lifetime. So you would probably want to write something like:

trait StreamingIterator {
    type Item<'a>;
    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
}

impl StreamingIterator {
    type Item<'a> = &'a i32;
    fn next<'a>(&'a mut self) -> Option<Self::Item<'a>>;
}

So we require a type constructor with a lifetime parameter for Item, and we provide it by parameterising the implementation by a lifetime variable. Now I can understand what is going on

This works:

type Test<'a> = &'a i32;

fn test1<'a>(x : Test<'a>) -> Test<'a> {
    x
}

fn main() {
    println!("{}", test1(&42));
}

So it needs a way to have a higher kinded type as an associated type, it doesn't require full HKT as you don't need to pass the constructor to a function.