Does rust really need higher kinded types?


#1

Continuing the discussion from High Order Function with Type Parameter:

A number of threads (including the most desired features thread) have suggested that Rust needs higher-kinded-types. I want to challenge that, by pointing out that polymorphic functions can already be passed as function arguments using traits. I think the following is quite an elegant solution and is fully monomorphisable for optimum performance, which is a property not necessarily shared by higher-kinded-types, and of course can also be used with runtime polymorphism using trait-objects.

Reposting the example from the linked discussion:

    use std::io::{Read, Cursor};
    use std::fs::{File};
    trait ReadFn {
        fn read<T : Read>(&mut self, T) -> ();
    }
    fn read_test<G>(mut g : G, pred : bool) where G : ReadFn {
        if pred {
            g.read(File::open("foo").unwrap());
        } else {
            g.read(Cursor::new(b"foo"));
        }
    }
    fn main() {
        struct MyFn<'a> {
            buf : &'a mut String
        }
        impl<'a> ReadFn for MyFn<'a> {
            fn read<T : Read>(&mut self, mut a : T) -> () {
                println!("{}", a.read_to_string(self.buf).ok().unwrap());
            }
        }
        let mut s = String::from("");
        read_test(MyFn{buf : &mut s}, false); // passing mutable 'closure' variable
        println!("{}", s);
    }

This is a friendly challenge, in that I actually like HKT in languages like Haskell, but my concern is that the type system should be as simple as possible. As such adding HKT to Rust to save a few lines of code seems excessive. What I would like is for people to post any code they feel is a motivating example for HKT in Rust, so I can have a go at encoding it with traits, to see how well this encoding copes with the cases people think need HKT.


Most coveted Rust features
High Order Function with Type Parameter
Most coveted Rust features
#2

My pet feature is streaming iterators. A bare bones trait (as shown in the link) can be defined and used with while let easy enough, but where I’ve failed is in defining adapter methods on that trait like what the Iterator trait has. e.g., map, filter, zip, etc… I don’t even mind loss of use of for loops, getting the adapter methods to work would be fantastic.

I think one thing to be cautious of in this endeavor is to avoid getting caught in the weeds. There may exist solutions to the problem, but what’s important is whether they are practical to use and easy to comprehend. (Because I think that’s invariably what will motivate the addition of HKT to the language proper.)

In any case, I share your fear of HKT. It is simultaneously terrifying and exciting.


#3

Here’s a first attempt. I had to remove the lifetime annotations from the Streamer trait definition as it was causing lifetimes to be needed everywhere, and the compiler seems to do better without it:

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

// A source is a struct of 'closure' variables for the generator plus the implementation of the Streamer trait
struct StreamSource {
    counter : i32
}

impl Streamer for StreamSource {
    type Item = i32;
    fn next(&mut self) -> Option<Self::Item> {
        print!("[generate] ");
        let t = self.counter;
        self.counter += 1;
        Some(t)
    }
}

// A sink is just a normal generic function that takes a Streamer
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() {
    // A filter is a struct for 'closure' variables and an implementation of Streamer
    // with a type parameter for the type of the source streamer and a value "input"
    // for the value of the actual streamer passed.
    struct StreamAdd<S> where S : Streamer {
        input : S,
        add : S::Item
    }

    impl<S> Streamer for StreamAdd<S> where S : Streamer, <S as Streamer>::Item : std::ops::Add<Output = S::Item> + Clone {
        type Item = S::Item;
        fn next(&mut self) -> Option<Self::Item> {
            print!("[filter] ");
            match self.input.next() {
                Some(x) => Some(x + self.add.clone()),
                None => None
            }
        }
    }
    
    stream_sink(StreamAdd{input: StreamSource{counter : 0}, add : 10});
}

Leaving out the plumbing of the Streamer source and sink, the important part is the definition of a filter:

struct StreamAdd<S> where S : Streamer {
    input : S
    add : S::Item
}

impl<S> Streamer for StreamAdd<S> where S : Streamer, <S as Streamer>::Item : std::ops::Add<Output = S::Item> + Clone {
    type Item = S::Item;
    fn next(&mut self) -> Option<Self::Item> {
        print!("[filter] ");
        match self.input.next() {
            Some(x) => Some(x + self.add.clone()),
            None => None
        }
    }
}

Personally I think its fairly simple to understand, StreamAdd is a record with fields for the input and any local data needed by the filter. The filter itself is an implementation of Streamer that has another streamer as its type parameter, but this can be inferred from the value put in ‘input’. If you read the final line the filter reads somewhat like a function with named parameters. I also think there is no difference between a Streamer and a normal Iterator, the ‘concept’ is the same it is the algorithms that are different. So an Iterator is a Streamer, but an eager_filter is a different algorithm than a lazy_filter.


#4

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. :slight_smile:


#5

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?


#6

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


#7

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.


#8

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.

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.

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


#9

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:

trait Super[Self <: Super]

And can be HKT:

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


Design patterns for composability with traits (i.e. typeclasses)?
#10

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


#11

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?

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


#12

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.


#13

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.


High Order Function with Type Parameter
High Order Function with Type Parameter
#14

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


#15

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


#16

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.


#17

Here’s my second attempt :slight_smile:

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: http://is.gd/RE3K7q


#18

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.


#19

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: http://is.gd/S5ctuO


#20

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.