CODEWITHSUNDEEP
rustiterator
Callum Rogers
Callum Rogers

Reputation: 15829

Extending Iterator over pairs with map_keys

I'm trying to write some simple extension methods for Rust's Iterator when it's iterating over (K, V) pairs. The simplest implementation I can come up with for mapping keys involves reusing Iterator::map like so: 

use std::iter::Map;

trait KeyedIterator<K, V>: Iterator<Item = (K, V)> {
    fn map_keys<R, F, G>(self, f: F) -> Map<Self, G>
    where
        Self: Sized,
        F: FnMut(K) -> R,
        G: FnMut((K, V)) -> (R, V),
    {
        self.map(|(key, value): (K, V)| (f(key), value))
    }
}

impl<I, K, V> KeyedIterator<K, V> for I where I: Iterator<Item = (K, V)> {}

However, it has this error:

error[E0308]: mismatched types
  --> src/lib.rs:10:18
   |
10 |         self.map(|(key, value): (K, V)| (f(key), value))
   |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter, found closure
   |
   = note: expected type `G`
              found type `[closure@src/lib.rs:10:18: 10:56 f:_]`

Shouldn't the closure implement G as it is a function from (K, V) to (R, V)? What am I missing here?

Upvotes: 2

Views: 447

Answers (2)

Peter Hall
Peter Hall

Reputation: 58735

If you declare a type parameter for a type or a function, that type must be provided by the caller. However, in your code, you are attempting to determine the type G in the body of map_keys, based on the type of the closure that is defined there.

Usually, the way to have a function body determine a type is with an existential return type (e.g. Map<Self, impl FnMut((K, V)) -> (R, V)>. However, this is not permitted in trait methods.

The pattern that is used for all the built-in iterator adapters will work for your use case though. That is, define a struct, which is returned by your method and make it an iterator:

// Struct to hold the state of the iterator
struct KeyedIter<I, F> {
    iter: I,
    f: F,
}

// Make KeyedIter an iterator whenever `I` is an iterator over tuples and `F` has the 
// correct signature
impl<K, V, R, I, F> Iterator for KeyedIter<I, F>
where
    I: Iterator<Item = (K, V)>,
    F: FnMut(K) -> R,
{
    type Item = R;
    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next().map(|(k, _v)| (self.f)(k))
    }
}

// A trait for adding the `map_keys` method
trait KeyedIterator<K, V> {
    fn map_keys<R, F>(self, f: F) -> KeyedIter<Self, F>
    where
        F: FnMut(K) -> R,
        Self: Sized;
}

// implement the trait for all iterators over tuples
impl<I, K, V> KeyedIterator<K, V> for I
where
    I: Iterator<Item = (K, V)>,
{
    fn map_keys<R, F>(self, f: F) -> KeyedIter<Self, F>
    where
        F: FnMut(K) -> R,
        Self: Sized,
    {
        KeyedIter { iter: self, f }
    }
}

The KeyedIter struct is parameterised by types that the caller knows about: the previous iterator, and the mapping function. There is no need to try to express the type of an intermediate closure - instead it's handled lazily in the iterator's next() method.

See also:

Upvotes: 4

Caio
Caio

Reputation: 3215

G is tied by the method and abstracts over the concrete type being passed in for each function call. For example:

fn print<T: core::fmt::Debug>(t: T) {
    println!("{:?}", t);
}

fn main() {
    print(1);
    print(1f64);
    print("1");
}

This means that it is not possible to return an arbitrary fixed G implementation but there are some workarounds.

1 - Static dispatch. The code must be modified to receive and return the same generic:

use core::iter::Map;

trait KeyedIterator<K, V>: Iterator<Item = (K, V)> {
    fn map_keys<R, F>(self, f: F) -> Map<Self, F>
    where
        Self: Sized,
        F: FnMut((K, V)) -> (R, V),
    {
        self.map(f)
    }
}

impl<I, K, V> KeyedIterator<K, V> for I where I: Iterator<Item = (K, V)> {}

fn main() {
    let vec = vec![(1u32, 2i32), (3, 4), (5, 6)];
    println!("{:?}", vec.into_iter().map_keys(|(k, v)| (k as f64 + 0.8, v)).collect::<Vec<(f64, i32)>>());
}

2 - Dynamic dispatch. With a little of run-time overhead, you can use Box.

trait KeyedIterator<K, V>: Iterator<Item = (K, V)> {
    fn map_keys<'a, R, F: 'a>(self, mut f: F) -> Box<Iterator<Item = (R, V)> + 'a>
    where
        Self: Sized + 'a,
        F: FnMut(K) -> R
    {
        Box::new(self.map(move |(key, value): (K, V)| (f(key), value)))
    }
}

impl<I, K, V> KeyedIterator<K, V> for I where
    I: Iterator<Item = (K, V)> {}

fn main() {
    let vec = vec![(1u32, 2i32), (3, 4), (5, 6)];
    println!(
        "{:?}",
        vec.into_iter()
            .map_keys(|k| k as f64 + 0.8)
            .collect::<Vec<(f64, i32)>>()
    );
}

Upvotes: 0

Related Questions