Algoritms agnostic to kind of reference


#1

So I have an algorithm that should work on iterables over some kind of item. Say:

fn best_match<I>(self, iter: I) -> Option<I::Item>
    where I: IntoIterator<Item = Tag>;

(Tag is some type in the crate). However, this way it will work only on iterators returning Tag by value (or reference or whatever the Item = condition is). But I don’t care whether it is a value or reference or what. I just need to call some methods the type has.

Normally, I can call a method on that type and anything that will Deref to that type. Unfortunately

fn best_match<I>(self, iter: I) -> Option<I::Item>
    where I: IntoIterator, I::Item: Deref<Target = Tag>

will not do, because while this includes all the smart pointers, it does not include Tag itself, because there is no blanket Deref for type to itself. Obviously, because a type can only Deref to one type and if all types Derefed to themselves via blanket implementation, they couldn’t Deref to what they should.

The closest I came about is using Borrow. Anything that is Deref<Target = T> will also Borrow<T> and there is a blanket impl Borrow<T> for T, so this time values are covered.

Is this the best current practice or is there some better suited condition for it?

And then my other problem is with traits of T. For the moment, I only needed std::cmp::Ord and all standard types that implement Borrow<T> also #[derive(Ord)] from T, so I just wrote

fn best_match<I>(self, iter: I) -> Option<I::Item>
    where I: IntoIterator, I::Item: Borrow<Tag> + Ord

and called it a day hoping that anything that implements Borrow<Tag> will also derive Ord from it.

But if I had my own trait, it would cause further complication, because, for obvious reasons,

fn best_match<I>(self, iter: I) -> Option<I::Item>
    where I: IntoIterator, I::Item: Borrow<Tag>
{
    iter.into_iter().map(|x| x.borrow())…
}

does not typecheck due to lifetimes and Borrow<Tag> is not considered to impl T's traits. So to use a trait (say Tags) I would either have to explicitly derive it for something, either anything that Derefs like

impl<D, T> Tags for D where D: Deref<Target = T>, T: Tags { … }

which is not otherwise needed as Deref is used automagically for calling methods, or for a “newtype” wrapper, which can be done inside the function.

I actually what I first tried to do just that with a wrapper type for the Ord case, but in the Ord it is particularly verbose, because Ord: Eq + PartialOrd and I would have to implement those two even though the implementation should be obvious from the Ord one.

So, how should I use traits of types possibly wrapped in smart pointers from generic code where the code should be generic with respect to what kind of pointer (including directly the value) the generic function gets?


#2

I had exactly the same problem. So far I have decided the best approach is to consider a ‘borrow’ as an argument passing convention rather than a reference. This fits with Rusts handing of l-values which cannot be returned from functions. Currently to pass a single value to a generic function you would have to pass it as a one-tuple, and define Deref on it.


#3

I’m not sure I follow your point about traits… you obviously can’t use map() the way you’re suggesting, but that doesn’t stop you from performing interesting operations:

use std::borrow::Borrow;
struct S;
#[derive(PartialEq, Eq, PartialOrd, Ord)]
struct Tag;

impl S {
    fn best_match<I>(self, iter: I) -> Option<I::Item>
        where I: IntoIterator, I::Item: Borrow<Tag>
    {
        iter.into_iter().fold(None, |max, cur| {
            if let Some(max) = max {
                if max.borrow() > cur.borrow() {
                    Some(max)
                } else {
                    Some(cur)
                }
            } else {
                Some(cur)
            }
        })
    }
}

#4

Well, that’s not any shorter than the corresponding for loop. Of course I can do that, but the functional stuff isn’t helping any more.


#5

Well, for my example in particular is a little ugly because of missing bits in the standard library, in particular a max_by function which takes a closure for the comparison, and fold1 from itertools.


#6

Yes, that’s the one I would have needed too. And there are more places like that that would need a variant taking a functor, but do not have it.