How to use adapters/closures for IntoIterator implementation?

help
1

Edit: Lots of good solutions are downthread, but the software only lets me select one:

  • steffahn lists the ideal solution, but it only works on nightly;
  • Yandros gave a lot of workarounds for stable;
  • My ulitmate solution is a hybrid that can switch between the two approaches with a cfg option.

I'm trying to write some newtypes that change the iteration behavior of the values they're wrapping. Normally, I'd lean on the adapters provided by Iterator to do this efficiently, but the use of closures makes their return types unnameable.

NB: In practice, the closure passed to the adapter will probably dispatch to a different closure stored inside the wrapper struct, so entirely eliminating closures isn't a viable path.

What's the best practice for dealing with this sort of situation? Do I need to hand-write the iterator with a bespoke next() implementation?

struct Evens(Vec<u32>);

impl IntoIterator for Evens {
    type Item=u32;
    type IntoIter=std::iter::Filter<<Vec<u32> as IntoIterator>::IntoIter, _>;
    
    fn into_iter(self)->Self::IntoIter {
        let f = self.1;
        self.0.into_iter().filter(|x| *x % 2 == 0)
    }
}

fn main() {
    for x in Evens(vec![1,2,3,4,5,6,7,8,9,10]) {
        println!("{:?}", x);
    } 
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0121]: the type placeholder `_` is not allowed within types on item signatures
 --> src/main.rs:5:75
  |
5 |     type IntoIter=std::iter::Filter<<Vec<u32> as IntoIterator>::IntoIter, _>;
  |                                                                           ^ not allowed in type signatures

error: aborting due to previous error

For more information about this error, try `rustc --explain E0121`.
error: could not compile `playground`.

To learn more, run the command again with --verbose.
1 Like
2

Eventually we’ll have type_alias_impl_trait for this kind of problem

#![feature(type_alias_impl_trait)]
struct Evens(Vec<u32>);

type EvensIntoIterClosure = impl FnMut(&u32) -> bool;

impl IntoIterator for Evens {
    type Item=u32;
    type IntoIter=std::iter::Filter<<Vec<u32> as IntoIterator>::IntoIter, EvensIntoIterClosure>;
    
    fn into_iter(self)->Self::IntoIter {
        self.0.into_iter().filter(|x| *x % 2 == 0)
    }
}

fn main() {
    for x in Evens(vec![1,2,3,4,5,6,7,8,9,10]) {
        println!("{:?}", x);
    } 
}

(playground)

1 Like
3

Two additional remarks: This approach does work with proper closures (i.e. ones that actually capture variables) and you don’t actually need to give the type a name:

#![feature(type_alias_impl_trait)]
struct Evens(Vec<u32>);

impl IntoIterator for Evens {
    type Item=u32;
    type IntoIter=std::iter::Filter<<Vec<u32> as IntoIterator>::IntoIter, impl FnMut(&u32) -> bool>;
    
    fn into_iter(self)->Self::IntoIter {
        let y = 2;
        self.0.into_iter().filter(move |x| *x % y == 0)
    }
}

fn main() {
    for x in Evens(vec![1,2,3,4,5,6,7,8,9,10]) {
        println!("{:?}", x);
    } 
}
1 Like
4

What about storing a Box<dyn FnMut(...)> inside your newtype? That way you sidestep the unnameable closures problem by using dynamic dispatch.

Also, keep in mind that anything implementing Iterator gets an IntoIterator implementation for free. Could just you implement Iterator for Evens and pass that around?

5

The other option is to use the fn() pointer type, which could have a negligible performance impact w.r.t. the empty closure type, but in practice the compiler is smart enough to optimize that out:

use ::core::iter::{self, Filter};
use ::std::vec;

struct Evens /* = */ (
    Vec<u32>,
);

impl IntoIterator for Evens {
    type Item = u32;
    type IntoIter = Filter<vec::IntoIter, fn(&u32) -> bool>;
    
    fn into_iter (self) -> Self::IntoIter
    {
        self.0.into_iter().filter(|&x| x % 2 == 0)
    }
}
  • If the closure does carry some state, and the performance cost of an allocation and virtual dispatch is acceptable for your project (e.g., if you wouldn't have cared using new if within C++), then you can use the Box<dyn FnMut(&u32) -> bool> type (which, in the case of a stateless closure, is "equivalent" to the fn(&u32) -> bool type).

Another option is to be Iterator rather than IntoIterator (the former implies the latter):

mod evens {
    use ::core::iter::Filter;
    use ::std::vec;

    pub
    struct Evens<F> /* = */ (
        Filter<vec::IntoIter<u32>, F>,
    );
    
    pub
    fn evens (vec: Vec<u32>)
      -> Evens<impl 'static + FnMut(&u32) -> bool>
    {
        Evens(vec.into_iter().filter(|&x| x % 2 == 0))
    }

    impl<F> Iterator for Evens<F>
    where
        F : FnMut(&u32) -> bool,
    {
        type Item = u32;
    
        fn next (self: &'_ mut Self) -> Option<Self::Item>
        {
            self.0.next()
        }
    }
}
use evens::*;

fn main ()
{
    for x in evens((1 ..= 10).collect()) {
        println!("{:?}", x);
    } 
}
3 Likes
6

Is it my impression or this is very similar to this question of mine?

1 Like
7

As a matter of fact, in your situation I would just write a function

fn evens<I>(iterable: I) -> impl Iterator<Item = u32>
where
    I: IntoIterator<Item = u32>,
{
    iterable.into_iter().filter(|&x| x % 2 == 0)
}

and use it like

fn main() {
    for x in evens(vec![1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) {
        println!("{:?}", x);
    }
}

My other question was about how to make it a method in order to use it like this

fn main() {
    for x in vec![1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().evens() {
        println!("{:?}", x);
    }
}

and enable further chaining. I still don't have a nice solution to that (one that relies on iterator adaptors and does not involve implementing next()). The reason is that AFAIK we can use impl Trait in the return type of functions, but not in associated types (yet).

8

@Michael-F-Bryan, @Yandros: Thanks for the suggestions, this looks like it’ll take some careful thought to decide the right design. I’m working on writing relational algebra primitives that can work with most Rust types, and hope to keep the runtime cost comparable to writing the same operations by hand.

I’ve got all the single-record manipulations working entirely at compile-time, and without any dynamic dispatch or or heap allocation. I’m now trying to extend this to handle relations (collections of homogeneous records), and would like to keep it as lean as possible.

Implementing Iterator directly is an interesting option; I need to think about what effects there would be having partially-consumed relations around.

The real code I’m working with right now is more like this (from memory; not at my computer right now):

trait Relation : IntoIterator
where <Self as IntoIterator>::Item = Self::Row {
    type Row: Record;

    fn join_fn<I,O,F>(self, f:F)->JoinFnRel<Self,I,O,F>
    where JoinFnRel<I,O,F>: Relation
    { JoinFnRel(self, f, PhantomData) }

    /* other Relation adapter methods here */
}

struct JoinFnRel<R,I,O,F> ( R, F, PhantomData<fn(I)->O>);

impl<R,I,O,F> Relation for JoinFnRel<R,I,O,F> 
where ... { ... }

impl<R,I,O,F> IntoIterator for JoinFnRel<R,I,O,F>
where R: Relation,
      F: Fn(I)->O,
      I: for<‘a> FromRecord<Lazy<&’a R::AsOwned >>,
      O: Relation,
      Join<R::Row, O::Row>: Record,
      R::Row::Header: DisjointTo<O::Row::Header>,
{
    type Item: Join<R::Row::AsOwned, O::Row>;
    fn into_iter(self)->...
    {
        let f = self.1;
        self.0.into_iter().flat_map(move |row| {
            let row=row.to_owned();
            f(row.lazy_ref().project())
                .into_iter()
                .map(move |x| Join(row.clone(), x))
        })
    }
}
9

In my attempt to boil down my problem into a minimal case, I may have inadvertently removed some key details. In particular, the newtype isn’t only altering the iteration, it also implements a trait that depends on IntoIterator (see my previous reply).

1 Like
10

Yes I understand that in general a new type is required, if you need to implement some other traits. Sorry for my silly suggestion then :slight_smile:

11

Where I ultimately ended up is a config switch to change between Box<dyn Iterator<...>> and impl Iterator<...>. The former works on stable now, and the latter should give better performance on nightly (and when type_alias_impl_trait stabilizes).

The macro should be generic enough for as many of these as I need to implement:

#![cfg_attr(feature="use_type_alias_impl_trait", feature(type_alias_impl_trait))]

macro_rules! into_iter_body{
    ($item:ty) => {
        type Item=$item;
        
        #[cfg(feature="use_type_alias_impl_trait")]
        type IntoIter=impl Iterator<Item=$item>;

        #[cfg(not(feature="use_type_alias_impl_trait"))]
        type IntoIter=Box<dyn Iterator<Item=$item>>;
        
        fn into_iter(self)->Self::IntoIter {
            let result = self.into_iter_raw();
            
            #[cfg(not(feature="use_type_alias_impl_trait"))]
            let result = Box::new(result);
            
            result
        }
    }
}

struct Evens(Vec<u32>);
impl Evens {
    fn into_iter_raw(self) -> impl Iterator<Item=u32> {
        self.0.into_iter().filter(|x| *x %2 == 0)
    }
}

impl IntoIterator for Evens { into_iter_body!{u32} }

fn main() {
    for x in Evens(vec![1,2,3,4,5,6,7,8,9,10]) {
        println!("{:?}", x);
    } 
}

(Playground)

12

If you are lazy, you can use rustc-version in a build script to detect when the user is compiling with nightly and automatically activate a cargo feature.

I've also seen these sorts of feature flags named nightly or unstable by convention. This has the added bonus that it's less typing than use_type_alias_impl_trait :stuck_out_tongue:

1 Like
13

Ideally, the compiler would expose available #[feature(...)]s as cfg items, so that crate features can get automatically activated once the stable compiler supports them.

14

Nah, the problem is that unstable features are unstable. This means, they can change. If you use and cfg on a feature and that feature changes and then gets stabilized (while you’re in vacation or whatever and not updating the code when it breaks on nightly) it will break your code on stable. Code breakage coming from stable-to-stable upgrade of the compiler is not desirable.

2 Likes
15

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.