Remove type parameter from Natural (WIP)

[apasel422]

The only reason this type parameter is currently necessary is because of the design of the comparator adaptors. Without the parameter (and replacing the natural function with a unit struct), the extremely common

let cmp = Natural.rev();
assert_eq!(cmp.compare(&1, &2), Greater);

fails type inference:

error: type annotations required: cannot resolve `_ : core::cmp::Ord` [E0283]
     let cmp = Natural.rev();
                       ^~~~~

This is because the rev method is defined on the Compare trait itself, which has two type parameters (for the left- and right-hand sides of the comparison), and the specific impl to use here is unconstrained.

However, the behavior of the rev method is always the same, regardless of the concrete comparator type or the type parameters involved. Therefore, there should really only be one way (impl) to reverse a comparator, which leads to a few possible solutions. They cannot involve type parameters on Compare.

1. Use separate constructors

1. Freestanding function:

   pub struct Rev<C>(C);
   pub fn rev<C>(cmp: C) -> Rev<C>);

2. Constructor method:

   pub struct Rev<C>(C);
   impl<C> Rev<C> {
       pub fn new(cmp: C) -> Rev<C> { Rev(cmp) }
   }

3. Public field:

   pub struct Rev<C>(pub C);

This approach has the following downsides:

• The user must import an additional type or function for each adaptor. (This is potentially negated by the custom prelude RFC).

• Chaining is no longer possible, which can make things confusing. For example:

  let cmp = then(extract(SliceExt::len, rev(Natural))), extract(SliceExt::first, Natural));

  versus

  let cmp = Natural.rev().extract(SliceExt::len).then(Natural.extract(SliceExt::first));

2. Use a separate trait

pub trait CompareExt: Sized { // note that it does not extend `Compare`
    fn rev(self) -> Rev<C> { Rev(self) }
    ... // methods for other adaptors
}

1. With a blanket impl:

   impl<C> CompareExt for C {} // note that we cannot specify `C: Compare<L, R>`

2. With specific impls:

   impl CompareExt for Natural {}
   impl<C> CompareExt for Rev<C> {}
   ...

TODO: Other options.

[Gankra]

CC me (need to think about this a bit more...)

[bluss]

I've only looked at this crate for a very short while. How to handle the .get<Q: ?Sized>() model that maps have?

Without a type parameter on Natural, at least it is fine to use with both Compare<K> and Compare<Q>

I tried the following, which fails because the default comparator is C = Natural<K> so the restriction C: Compare<Q> forces K == Q :(

    pub fn contains<Q: ?Sized>(&self, key: &Q) -> bool
        where K: Borrow<Q>,
              C: Compare<Q>,
    {

With this said, I think for this use case a phantom-type based approach works better. Custom closure comparators can't cope with the Q vs K scheme anyway.

[Gankra]

This is super out of cache but I think the Borrow adaptor is supposed to be for that...?

https://github.com/contain-rs/compare/blob/master/src/lib.rs#L215-L234

[bluss]

aha thanks!

[bluss]

Hm I can't figure out how to use it. I don't think I can, if I require my Bmap<K, V, C> to have a C: Compare<K>, then that can't be converted in any way into something that can compare two borrowed Q values (where K: Borrow<Q>).