Don't require `T: Copy` for `T: Enumerable`

[tyilo]

It doesn't seem necessary. For instance Vec<bool> could be enumerable even though it is not Copy.

[aarkegz]

The reason requiring T: Copy for T: Enumerable is to simplify the implementation for plain enums.

[aarkegz]

Could you tell me what's your expected result for <Vec<bool> as Enumerable>::enumerator()? Maybe vec![], vec![false], vec![true], vec![false, false], ...?

[tyilo]

Could you tell me what's your expected result for <Vec<bool> as Enumerable>::enumerator()? Maybe vec![], vec![false], vec![true], vec![false, false], ...?

Yes

[aarkegz]

Yes

That makes sense. However it's an Indefinite-Enumerable type so I think it requires much more effort to make things right. For example:

struct A {
    field_a: bool,
    field_b: Vec<bool>,
}

struct B {
    field_a: Vec<bool>,
    field_b: Vec<bool>,
}

these types are quite hard to enumerate.

[aarkegz]

The reason requiring T: Copy for T: Enumerable is to simplify the implementation for plain enums.

Bench shows that implementing Enumerable for plain-enums with const array is faster that conversion from index:

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum LargePlainEnum {
    Var0,
    Var1,
    Var2,
    // ... more variants here
    Var99,
}


fn enumerate_large_plain_enum_array() -> impl Iterator<Item = LargePlainEnum> {
    [
        LargePlainEnum::Var0,
        LargePlainEnum::Var1,
        LargePlainEnum::Var2,
        // ...
        LargePlainEnum::Var99,
    ]
    .iter()
    .copied()
}

#[inline(always)]
fn large_plain_enum_from_index(index: usize) -> LargePlainEnum {
    match index {
        0 => LargePlainEnum::Var0,
        1 => LargePlainEnum::Var1,
        2 => LargePlainEnum::Var2,
        // ...
        99 => LargePlainEnum::Var99,
        _ => unreachable!(),
    }
}

fn enumerate_large_plain_enum_index() -> impl Iterator<Item = LargePlainEnum> {
    (0..100).map(large_plain_enum_from_index)
}

#[cfg(test)]
mod test {
    extern crate test;
    use super::*;
    use test::black_box;

    #[bench]
    fn large_plain_enum_array(b: &mut test::Bencher) {
        b.iter(|| {
            let iter = enumerate_large_plain_enum_array();
            for e in iter {
                black_box(e);
            }
        });
    }

    #[bench]
    fn large_plain_enum_index(b: &mut test::Bencher) {
        b.iter(|| {
            let iter = enumerate_large_plain_enum_index();
            for e in iter {
                black_box(e);
            }
        });
    }
}

And the result is:

test tests::large_plain_enum_array ... bench:          28.83 ns/iter (+/- 0.12)
test tests::large_plain_enum_index ... bench:         111.36 ns/iter (+/- 0.22)

[tyilo]

Yes

That makes sense. However it's an Indefinite-Enumerable type so I think it requires much more effort to make things right. For example:

struct A {
    field_a: bool,
    field_b: Vec<bool>,
}

struct B {
    field_a: Vec<bool>,
    field_b: Vec<bool>,
}

these types are quite hard to enumerate.

Example code for doing this: https://github.com/tyilo/infinite-enumerable

[tyilo]

The reason requiring T: Copy for T: Enumerable is to simplify the implementation for plain enums.

Bench shows that implementing Enumerable for plain-enums with const array is faster that conversion from index:

What if you used cloned() instead of copied() and just required T: Clone?

[tyilo]

The reason requiring T: Copy for T: Enumerable is to simplify the implementation for plain enums.

Bench shows that implementing Enumerable for plain-enums with const array is faster that conversion from index:

What if you change the implementation to:

#[inline(always)]
fn large_plain_enum_from_index(index: usize) -> LargePlainEnum {
    const ALL: [LargePlainEnum; 100] = [
        LargePlainEnum::Var0,
        LargePlainEnum::Var1,
        LargePlainEnum::Var2,
        // ...
        LargePlainEnum::Var99,
    ];

    ALL[index] // Add .clone if needed
}

[aarkegz]

The reason requiring T: Copy for T: Enumerable is to simplify the implementation for plain enums.

Bench shows that implementing Enumerable for plain-enums with const array is faster that conversion from index:

What if you used cloned() instead of copied() and just required T: Clone?

That sounds better! I think Clone is really essential as both enums and tuples need it.

[aarkegz]

The reason requiring T: Copy for T: Enumerable is to simplify the implementation for plain enums.

Bench shows that implementing Enumerable for plain-enums with const array is faster that conversion from index:

What if you change the implementation to:

#[inline(always)]
fn large_plain_enum_from_index(index: usize) -> LargePlainEnum {
    const ALL: [LargePlainEnum; 100] = [
        LargePlainEnum::Var0,
        LargePlainEnum::Var1,
        LargePlainEnum::Var2,
        // ...
        LargePlainEnum::Var99,
    ];

    ALL[index] // Add .clone if needed
}

That's actually a little bit faster than the iter().copied() version (in release profile):

test tests::large_plain_enum_array        ... bench:          33.00 ns/iter (+/- 3.11)
test tests::large_plain_enum_index_access ... bench:          28.69 ns/iter (+/- 0.41)
test tests::large_plain_enum_index_match  ... bench:         131.72 ns/iter (+/- 0.09)

Thank you very much!

[aarkegz]

Yes

That makes sense. However it's an Indefinite-Enumerable type so I think it requires much more effort to make things right. For example:

struct A {
    field_a: bool,
    field_b: Vec<bool>,
}

struct B {
    field_a: Vec<bool>,
    field_b: Vec<bool>,
}

these types are quite hard to enumerate.

Example code for doing this: https://github.com/tyilo/infinite-enumerable

That's awesome! Yes it definitely gives all possible values of indefinite types. It's kind of like the construction of a bijection between rationals and naturals, right?

What I'm worrying about is that this algorithm, though being able to enumerate infinite types, breaks the current guarantee that all possible values are generated in a lexicographical order, for finite types. A very good guarantee. So I'm thinking about the possibility of using different methods for finite and infinite types.