Container trait with GATs

Please, can someone help me? I'm already tired of fighting with the compiler. There is a certain trait that has a method that returns an iterator (everything works here). Next, I want to implement this trait on an array of elements, each of which implements this trait. It is necessary that the returned iterator be flattened. But it doesn't work:

use core::iter::{Flatten, Map};
use core::slice::Iter;
use std::collections;
use core::borrow::Borrow;
use core::hash::Hash;

pub trait Container<E: ?Sized> {
    type Key;
    type Value;
    type Keys<'a>: Iterator<Item = &'a Self::Key>
    where
        Self: 'a,
        Self::Key: 'a,
        Self::Value: 'a;

    fn keys<'a>(&'a self) -> Self::Keys<'a>;
}

impl<K, V, Q> Container<Q> for collections::HashMap<K, V>
where
    K: Hash + Eq + Borrow<Q>,
    Q: Hash + Eq,
{
    type Key = K;
    type Value = V;
    type Keys<'a> = collections::hash_map::Keys<'a, K, V> where Self: 'a, K: 'a, V: 'a;

    fn keys<'a>(&'a self) -> Self::Keys<'a> {
        self.keys()
    }
}

impl<E, T: Container<E>, const N: usize> Container<E> for [T; N] {
    type Key = T::Key;
    type Value = T::Value;

    type Keys<'a> = Flatten<Map<Iter<'a, T>, fn(&T) -> T::Keys<'a>>> //Flatten<Map<Iter<'a, T>, for<'b> fn(&'b T) -> T::Keys<'b>>>
    where
        Self: 'a,
        Self::Key: 'a,
        Self::Value: 'a;

    fn keys<'a>(&'a self) -> Self::Keys<'a> {
        fn keys_iter<'a, E1, T1: Container<E1>>(item: &'a T1) -> T1::Keys<'a> {
            item.keys()
        }
        self.iter().map(keys_iter).flatten()
    }
}

Here is the compilation error:

error[E0308]: mismatched types                                                                                                                                           
   --> src\lib.rs:488:9
    |
484 |     fn keys<'a>(&'a self) -> Self::Keys<'a> {
    |                              -------------- expected `Flatten<Map<std::slice::Iter<'a, T>, for<'b> fn(&'b T) -> <T as Container<E>>::Keys<'a>>>` because of return 
type
...
488 |         self.iter().map(keys_iter).flatten()
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected fn pointer, found fn item
    |
    = note: expected struct `Flatten<Map<std::slice::Iter<'a, _>, for<'b> fn(&'b T) -> <T as Container<E>>::Keys<'a>>>`
               found struct `Flatten<Map<std::slice::Iter<'_, _>, for<'a> fn(&'a T) -> <T as Container<E>>::Keys<'a> {keys_iter::<E, T>}>>`

For more information about this error, try `rustc --explain E0308`.
error: could not compile `container` due to previous error

Doesn't work with closures or function pointers :frowning:

The compiler can't figure out how to coerce keys_iter (a function item; every functions in Rust has a distinct unique type) into the function pointer type required. Sometimes it's just a matter of helping the compiler out by providing an explicit as fn(X) -> Y coercion, but I have no idea if there actually exists any valid coercion in this case.

1 Like

It seems to work, I'll test it right now

If anyone needs it, here is the working version of the code (renamed the trait method a little so that there was no confusion with the standard hash table method):

use core::iter::{Flatten, Map};
use core::slice::Iter;
use std::collections;
use core::borrow::Borrow;
use core::hash::Hash;

pub trait Container<E: ?Sized> {
    type Key;
    type Value;
    type Keys<'a>: Iterator<Item = &'a Self::Key>
    where
        Self: 'a,
        Self::Key: 'a,
        Self::Value: 'a;

    fn keys_iterator<'a>(&'a self) -> Self::Keys<'a>;
}

impl<K, V, Q> Container<Q> for collections::HashMap<K, V>
where
    K: Hash + Eq + Borrow<Q>,
    Q: Hash + Eq,
{
    type Key = K;
    type Value = V;
    type Keys<'a> = collections::hash_map::Keys<'a, K, V> where Self: 'a, K: 'a, V: 'a;

    fn keys_iterator<'a>(&'a self) -> Self::Keys<'a> {
        self.keys()
    }
}

impl<E, T: Container<E>, const N: usize> Container<E> for [T; N] {
    type Key = T::Key;
    type Value = T::Value;

    type Keys<'a> = Flatten<Map<Iter<'a, T>, fn(&'a T) -> T::Keys<'a>>>
    where
        Self: 'a,
        Self::Key: 'a,
        Self::Value: 'a;

    fn keys_iterator<'a>(&'a self) -> Self::Keys<'a> {
        fn keys_iter<'a, E1, T1: Container<E1>>(item: &'a T1) -> T1::Keys<'a> {
            item.keys_iterator()
        }
        self.iter().map(keys_iter as fn(&'a T) -> T::Keys<'a>).flatten()
    }
}

#[test]
fn test() {
    let mut map1 = collections::HashMap::new();
    let mut map2 = collections::HashMap::new();
    let mut map3 = collections::HashMap::new();
    for i in 0..10 {
        map1.insert(i, i);
        map2.insert(i + 10, i + 10);
        map3.insert(i + 20, i + 20);
    }

    let array = [map1, map2, map3];

    let mut vec = array.keys_iterator().cloned().collect::<Vec<_>>();
    vec.sort_unstable();

    for (item, count) in vec.into_iter().zip(0..30) {
        assert_eq!(item, count);
    }
}