How do I make a structure generic in Rust without higher kinded type (HKT) support?

Question

I am trying to make the Iteratee structure generic so I can pass in a different parsing function and get an different Iteratee. This is the non-generic version that works:

use std::io::{BufRead, BufReader};
use std::str::{from_utf8, Utf8Error};

#[derive(PartialEq, Debug)]
struct Cat<'a> {
    name: &'a str,
}

fn parse<'a>(slice: &'a [u8]) -> Result<Cat<'a>, Utf8Error> {
    from_utf8(slice).map(|name| Cat { name: name })
}

struct Iteratee<R>
    where R: BufRead + Sized
{
    read: R,
}

impl<R> Iteratee<R>
    where R: BufRead + Sized
{
    fn next<'a, F>(&'a mut self, fun: F)
        where F: Fn(Option<Result<Cat<'a>, Utf8Error>>) -> () + Sized
    {
        let slice = self.read.fill_buf().unwrap();
        fun(Some(parse(slice)))
        //       ^^^^^^^^^^^ How do I pull 'parse' up as a function of Iteratee
    }
}

fn main() {
    let data = &b"felix"[..];
    let read = BufReader::new(data);
    let mut iterator = Iteratee { read: read };
    iterator.next(|cat| assert_eq!(cat.unwrap().unwrap(), Cat { name: "felix" }));
}

This is my attempt at making it generic, but I can't construct IterateeFun with either a reference to the function or passing in a closure.

struct IterateeFun<R, P, T>
    where R: BufRead + Sized,
          P: Fn(&[u8]) -> (Result<T, Utf8Error>) + Sized
{
    read: R,
    parser: P,
}

impl<R, P, T> IterateeFun<R, P, T>
    where R: BufRead + Sized,
          P: Fn(&[u8]) -> (Result<T, Utf8Error>) + Sized
{
    fn next<'a, F>(&'a mut self, fun: F)
        where F: Fn(Option<Result<T, Utf8Error>>) -> () + Sized
    {
        let slice = self.read.fill_buf().unwrap();
        fun(Some((self.parser)(slice)))
    }
}


fn main() {
    let data = &b"felix"[..];
    let read = BufReader::new(data);
    let mut iterator = IterateeFun {
        read: read,
        parser: parse, // What can I put here?
        // I've tried a closure but then I get error[E0495]/ lifetime issues
    };

    iterator.next(|cat| assert_eq!(cat.unwrap().unwrap(), Cat { name: "felix" }));
}

I'd like to know how to pass a function into a structure as shown. Or should I be doing this as a trait instead?

That's a fair point, at the moment I'm not even sure what the correct terms are to describe the problem I have. Error[E0495] isn't the actual problem, it's how do I restructure my code in such a way that I can pass a function in or at least create a generic version of the code. Maybe I'm just not thinking about this in an idiomatic Rust way, which was what I was trying to allude to with the trait comment. In summary I don't know what I don't know ;) — Daniel Worthington-Bodart, Jan 21 '17 at 21:17
How about such questions as [How do I store a closure in Rust?](http://stackoverflow.com/q/27831944/155423), [Storing a closure in a HashMap](http://stackoverflow.com/q/29202137/155423), or [Storing a closure in a structure — cannot infer an appropriate lifetime](http://stackoverflow.com/q/21510694/155423) (I've not reviewed any in particular, they are just early search results). — Shepmaster, Jan 21 '17 at 21:22
I've posted an answer that uses [higher-rank trait bounds](https://doc.rust-lang.org/beta/nomicon/hrtb.html), see [example in playground](https://gist.github.com/07a68fd62b03ae54659716e118d2b1da). But this is still not as generic as your second snippet, it assumes that the closure returns `Result>` rather than `T<'a>`. I'm afraid the latter might not be possible to express in current Rust which doesn't have [higher-kinded types](https://users.rust-lang.org/t/does-rust-really-need-higher-kinded-types/5531). As this is beyond my understanding of the type system, I've removed my answer. — user4815162342, Jan 21 '17 at 21:52
I was wondering if higher-rank trait bounds was the answer. Maybe I could do some thing a bit like http://burntsushi.net/rustdoc/fst/trait.Streamer.html — Daniel Worthington-Bodart, Jan 21 '17 at 22:05

score 3 · Accepted Answer · edited Jan 22 '17 at 14:54

As with most problems I just needed another level of indirection! Higher kinded types (HKT) would obviously help but I actually only need to be able to associate a lifetime parameter with my parsing function.

Inspired by user4815162342 and Streamer I realised I could create two traits Iteratee<'a> and Parser<'a> each with an associated type and then when I create an implementation that combines them I would be able to combine the associated types to give me a form of HKTs:

trait Parser<'a> {
    type Output: 'a;

    fn parse(&self, &'a [u8]) -> Result<Self::Output, Utf8Error>;
}

struct CatParser;

impl<'a> Parser<'a> for CatParser{
    type Output = Cat<'a>;

    fn parse(&self, slice: &'a [u8]) -> Result<Self::Output, Utf8Error> {
        parse(slice)
    }
}

trait Iteratee<'a> {
    type Item: 'a;

    fn next<F>(&'a mut self, fun: F) where F: Fn(Option<Self::Item>) -> () + Sized;
}

struct IterateeParser<R, P> {
    read: R,
    parser: P,
}

impl<'a, R, P> Iteratee<'a> for IterateeParser<R,P> where R: BufRead + Sized, P: Parser<'a> {
    type Item = Result<P::Output, Utf8Error>;
    //                 ^^^^^^^^^ This is the magic!

    fn next<F>(&'a mut self, fun: F) where F: Fn(Option<Self::Item>) -> () + Sized {
        let slice = self.read.fill_buf().unwrap();
        fun(Some(self.parser.parse(slice)))
    }
}

fn main() {
    let data = &b"felix"[..];
    let read = BufReader::new(data);
    let mut iterator = IterateeParser { read: read, parser: CatParser };
    iterator.next(|cat| assert_eq!(cat.unwrap().unwrap(), Cat { name: "felix" }));
}

The magic line is type Item = Result<P::Output, Utf8Error>;

How do I make a structure generic in Rust without higher kinded type (HKT) support?

1 Answers1

Linked