Not clear that EntryMap can be used in generic contexts

[Gankra]

I think it needs HKT or something loopy like that. For instance I tried implementing a super generic "categorize":

    extern crate eclectic;

    use eclectic::*;
    use std::hash::Hash;

    pub fn categorize<'a, D, B, F, O, M>(data: D, mut f: F) where
        D: IntoIterator + Sized,
        B: Default + Extend<D::Item> + 'static,
        F: FnMut(&D::Item) -> O,
        O: Hash + Eq,
        M: EntryMap<Key=O, Value=B> + Default,
    {
        let map = M::default();
        for x in data {
            match map.entry(f(&x)) {
                Entry::Vacant(v) => v.insert(B::default()),
                Entry::Occupied(o) => o.into_mut(),
            }.extend(Some(x));
        }
        map
    }

But it's not clear that a lifetime can be supplied for EntryMap.

[apasel422]

Interesting. I wonder if associated lifetimes would help. I'm looking into this now.

[apasel422]

The following appears to work:

extern crate eclectic;

use eclectic::*;
use std::hash::Hash;

pub fn categorize<D, F, M>(data: D, mut f: F) -> M where
    D: IntoIterator,
    F: FnMut(&D::Item) -> M::Key,
    M: Default + for<'a> EntryMap<'a>,
    M::Key: Eq + Hash,
    M::Value: Default + Extend<D::Item>,
{
    let mut map = M::default();

    for datum in data {
        match map.entry(f(&datum)) {
            Entry::Vacant(e) => e.insert(M::Value::default()),
            Entry::Occupied(e) => e.into_mut(),
        }.extend(Some(datum));
    }

    map
}

[apasel422]

With the entry API I just added in 0.0.3, this can be written as:

extern crate eclectic;

use eclectic::*;
use std::hash::Hash;

pub fn categorize<D, F, M>(data: D, mut f: F) -> M where
    D: IntoIterator,
    F: FnMut(&D::Item) -> M::Key,
    M: Default + for<'a> EntryMap<'a>,
    M::Key: Eq + Hash,
    M::Value: Default + Extend<D::Item>,
{
    let mut map = M::default();

    for datum in data {
        map.entry(f(&datum)).or_insert_with(M::Value::default).extend(Some(datum));
    }

    map
}

[apasel422]

There's also no need for the key to implement Eq + Hash here.

[Gankra]

Oh yeah sorry that was legacy from the port. See: http://www.reddit.com/r/rust/comments/38oa85/more_generic_partition_method_how_would_it_look/

I'm confused that you can talk about the associated types of a for<'a> bound? When I tried that with Fn I got an exotic error explaining that this can't be done.

[apasel422]

Yeah, that's kind of mysterious. Might be a bug in rustc that only applies that restriction to the Fn traits?

[apasel422]

Although, to be fair, those associated types are actually defined on Map, not EntryMap, so they are independent of the lifetime.

[apasel422]

(Adding something like M::Occupied: Copy to the where clause yields the expected cannot extract an associated type from a higher-ranked trait bound in this context error.)

[Gankra]

I don't think this is actually instantiable:

extern crate eclectic;

use eclectic::*;

pub fn categorize<D, F, M>(data: D, mut f: F) -> M where
    D: IntoIterator,
    F: FnMut(&D::Item) -> M::Key,
    M: Default + for<'a> EntryMap<'a>,
    M::Value: Default + Extend<D::Item>,
{
    let mut map = M::default();

    for datum in data {
        map.entry(f(&datum)).or_insert_with(M::Value::default).extend(Some(datum));
    }

    map
}

#[test]
fn test() {
    use std::collections::*;

    let x: HashMap<i32, Vec<i32>> = categorize(vec![1,2,3,4,5,6,7], |&x| x % 4);
    let y: BTreeMap<i32, VecDeque<i32>> = categorize((1..10).take(10), |&x| x);
}

test2::cargo test
   Compiling test2 v0.1.0 (file:///Users/ABeingessner/dev/test2)
src/lib.rs:24:33: 24:43 error: the requirement `for<'a> collections::vec::Vec<_> : 'a` is not satisfied [E0280]
src/lib.rs:24     let x: HashMap<_, Vec<_>> = categorize(vec![1,2,3,4,5,6,7], |&x| x % 4);
                                              ^~~~~~~~~~
src/lib.rs:25:39: 25:49 error: the requirement `for<'a> collections::vec_deque::VecDeque<_> : 'a` is not satisfied [E0280]
src/lib.rs:25     let y: BTreeMap<_, VecDeque<_>> = categorize((1..10).take(10), |&x| x);
                                                    ^~~~~~~~~~

[apasel422]

Hmm. I don't know why that bound is a requirement. Investigating...

[Gankra]

CC @nikomatsakis @aturon

[apasel422]

It seems to me that

for<'a> collections::vec::Vec<i32>: 'a

should be met, as i32: 'static.

[nikomatsakis]

The code around for<'a> T: 'a is not particularly smart. I think I just tried to make it ultra conservative for now. I agree that we can treat for<'a> T: 'a as basically equivalent to T: 'static.

[jroesch]

cc me

[apasel422]

Note that we will want to replace the lifetime parameter in {OccupiedEntry, VacantEntry} with an associated lifetime.

[apasel422]

After rust-lang/rust#27096 landed, the following now works:

extern crate eclectic;

use eclectic::map::EntryMap;

pub fn categorize<D, F, M>(data: D, mut f: F) -> M
where
    D: IntoIterator,
    F: FnMut(&D::Item) -> M::Key,
    M: Default + for<'a> EntryMap<'a>,
    M::Value: Default + Extend<D::Item>,
{
    let mut map = M::default();

    for datum in data {
        map.entry(f(&datum)).or_insert_with(M::Value::default).extend(Some(datum));
    }

    map
}

#[test]
fn test() {
    use std::collections::*;

    let x: HashMap<i32, Vec<i32>> = categorize(1..8, |&x| x % 4);
    assert_eq!(x[&0], [4]);
    assert_eq!(x[&1], [1, 5]);
    assert_eq!(x[&2], [2, 6]);
    assert_eq!(x[&3], [3, 7]);

    let _: BTreeMap<i32, VecDeque<i32>> = categorize(1..10, |&x| x);
}

[Gankra]

Daaang 👏