Extending Vec Iterator with Custom Iterator Adaptor

#1

I’ve the following code, which I am trying to simplify by writing my own min_or_max() method:

if depth % 2 == 0 {
    children.iter()
        .map(|child| TreeNode::score_depth(child, depth + 1))
        .max()
        .unwrap()
} else {
    children.iter()
        .map(|child| TreeNode::score_depth(child, depth + 1))
        .min()
        .unwrap()
}

children is a Vec<TreeNode> and I’ve attempted to implement a custom trait for Iterator:

trait MinMax {
    type Item;
    
    fn min_or_max(self, max: bool) -> Option<Self::Item> where Self: Sized, Self::Item: Ord;
}

impl MinMax for Iterator {
    type Item = Self;
    
    fn min_or_max(self, max: bool) -> Option<Self::Item> where Self: Sized, Self::Item: Ord {
        if max {
            self.max()
        } else {
            self.min()
        }
    }
}

However, I can’t work out what I actually need to implement this trait on or what the correct method signature should be. Could someone please point me in the right direction?

#2

Iterators are not of the Iterator type. They are custom, specific types (like “an iterator that searches a slice for max number” type) that happen to implement the Iterator trait.

So use impl<T> MinMax for T where T: Iterator.

1 Like
#3

If you really want to add a function to all iterators, take a look at how itertools does it.

However in this case it doesn’t seem to be the appropriate solution. Instead consider something like the following:

fn min_or_max<I, J>(iter: I, max: bool) -> Option<J>
where
    I: Iterator<Item = J>,
    J: Ord,
{
    if max {
        iter.max()
    } else {
        iter.min()
    }
}

This could be used in this way:

let iter = children.iter()
    .map(|child| TreeNode::score_depth(child, depth + 1));
let result = min_or_max(iter, depth % 2 == 0).unwrap();
1 Like
#4

What I went for in the end is as follows:

pub trait MinOrMax: Iterator {
    fn min_or_max(self, is_maximising: bool) -> Option<Self::Item> where Self: Sized, Self::Item: Ord;
}

impl<I> MinOrMax for I where I: Iterator {
    fn min_or_max(self, is_maximising: bool) -> Option<Self::Item> where Self: Sized, Self::Item: Ord {
        if is_maximising {
            self.max()
        } else {
            self.min()
        }
    }
}

Which is used as follows:

fn score_children(children: &Option<Vec<Node>>, depth: u32) -> i32 {
    match children {
        None => 0,
        Some(children) => children.iter()
            .map(|child| Self::score_node(child, depth))
            .min_or_max((depth - 1).is_even())
            .unwrap()
    }
}

Thanks for the suggestion Alice, but I’d like to keep the number of temporary variables to a minimum, zero ideally, hence wanting to add a function to the iterator.

I believe it is possible to specify the generic bounds so that the method is only available on iterators whose item’s are of the types that “make sense”, i.e. those which implement Ord in this case. Does my implementation do this, or have I misunderstood what is happening here?

#5

On that note, why do I not need to define the associated type Item in the MinOrMax trait? When I defined it and set type Item = T; in the implementation, I got a whole bunch of errors I couldn’t fathom and it was only by trial and error that I removed it and got a working solution.

There are clearly a few gaps in my knowledge, which the Rust Book hasn’t helped to answer for me. I suspect that my understanding of generics and generic trait bounds will improve as I use them more. However, I’d appreciate it if someone could try and explain to me why the associated type is not required for my trait, or point me towards some other resources that might help to explain it.