Repository: rust-itertools/itertools (language: rust)

Issue:
Merge `MergeBy` and `MergeJoinBy`
It seems that `merge_join_by`/`MergeJoinBy` is actually a more generic variant of `merge`/`MergeBy`.

However, currently, the `MergeJoinBy` and `MergeBy` are implemented independently (`PutBack` vs `Peekable`, fused behavior, requiring `Ordering` vs `bool`). The past showed that uniform implementations may be better.

This change should not introduce breaking changes for users: `merge`, `merge_by` and `merge_join_by` should stay usable as they are. 

However, I'd imagine that the general `merge_join_by` could also accept a comparator returning `bool` (instead of `Ordering`) - this would free the users from having to deal with the `EitherOrBoth::Both` case. I.e. I suggest that users should be able to write:

```
use itertools; // 0.10.5
use itertools::{Either, EitherOrBoth};

fn main() {
    let numbers = [1,2,3,4,5];
    let strings = ["one", "two", "three", "four"];
    
    for x in itertools::merge_join_by(
        numbers,
        strings,
        |number, string| number.cmp(&string.len()),
    ) {
        match x {
            EitherOrBoth::Left(number) => {dbg!(number);},
            EitherOrBoth::Right(string) => {dbg!(string);},
            EitherOrBoth::Both(number, string) => {dbg!(number, string);},
        };
    }
    
    for x in itertools::merge_join_by(
        numbers,
        strings,
        |number, string| number < &string.len(), // <-- Note that we return bool instead of Ordering
    ) {
        match x {
            Either::Left(number) => {dbg!(number);},
            Either::Right(string) => {dbg!(string);},
            // <-- Note that we do not need to deal with the "Both" case, as our comparator returns bool
        };
    }
}
```

When we tackle this, we should - as a first step - probably move all the `merge`-related functions into an own module.


Discussion / hints:
I experimented a bit and what you want is for `MergeJoinBy<I, J, F>` to have:
* `impl Iterator<Item = EitherOrBoth<I::Item, J::Item>>` when the `cmp_fn` is returning `Ordering` ;
* `impl Iterator<Item = Either<I::Item, J::Item>>` when the `cmp_fn` is returning `bool`.

It's conflicting. But then if we add a type `T` to "MergeJoinBy" (I think it's a small breaking change):

    pub struct MergeJoinBy<I: Iterator, J: Iterator, F, T>
        where F: FnMut(&I::Item, &J::Item) -> T
    { ... }
then we can have

    impl<I, J, F> Iterator for MergeJoinBy<I, J, F, Ordering> // EitherOrBoth
    impl<I, J, F> Iterator for MergeJoinBy<I, J, F, bool> // Either
Does it seems good to you? (changes in "src/merge_join.rs" and very little in "src/lib.rs").
EDIT: I can avoid duplication with a macro.
EDIT 2: A bit unsure about what variant it should return in our new case:
cmp_fn returning  | output variant
-------------------|--------------------
Ordering::Less       | EitherOrBoth::Left
Ordering::Greater  | EitherOrBoth::Right
Ordering::Equal     | EitherOrBoth::Both
false                      | **Either::Right ?**
true                      | **Either::Left ?**

Hi there. I'm not sure if I follow 100% wrt "conflicting". I think `MergeJoinBy` should not require the function's return type explicitly, because it can be inferred from `F`.

As such, I'd imagine this:

```
impl<I, J, F, ResultOfF> Iterator for MergeJoinBy
    where
        F: FnMut(&I::Item, &J::Item) -> ResultOfF,
        ResultOfF: OrderingOrBool<I::Item, J::Item>
{
    type Item = ResultOfF::Item;
}

trait OrderingOrBool<IItem, JItem> {
    type Item
}
impl<IItem, JItem> OrderingOrBool<IItem, JItem> for std::cmp::Ordering {
    type Item = EitherOrBoth<IItem, JItem>;
}
// similar for bool with Item = Either
```

I am not sure if this design hits an unsovable obstacle somewhere, but for me it looks a bit clearer than basically copy-pasting/macro-generating two impls for `bool` and `Ordering` separately. Did you research this possibility and run into problems?
I agree about not conflicting for the reason you mention, I was just being careful.
TBH, I did not think of this trait-way, I like it. After giving it a try, it works with a few additions.

    pub trait OrderingOrBool<I, J> {
        type Item;
        // All with `#[inline(always)]` in both impl
        fn into_cmp(self) -> Ordering;
        fn left(left: I) -> Self::Item;
        fn right(right: J) -> Self::Item;
        fn both(left: I, right: J) -> Self::Item;
    }
To match against the result of the user function, I needed `into_cmp` (for bool, `if self { Ordering::Less } else { Ordering::Greater }`).
I added "left/right/both" methods to be able to create variants ("both" for bool only contains `unreachable!("into_cmp never returns Ordering::Equal so this should never be called")`).
Wow, that was fast. - Nice that it seems to work.

As for the additional methods: Of course, I didn't see the whole implementation, but it sounds reasonable.
Here is a [commit](https://github.com/Philippe-Cholet/itertools/commit/5ad6f70e46c0e2404f86c5eaeed800adec27d9cc) for it. Seems reasonable to me too.
I'm currently blocked about merging implementations of `MergeJoinBy` and `MergeBy`. Maybe you have an idea on what to do. Or I will try again.
First, I [moved](https://github.com/Philippe-Cholet/itertools/commit/d853808ca78b6482ccd4ac0480a2a7684486a13d) `MergeBy` into its own module "merge" as you suggested.

To merge implementations of "MergeBy" and "MergeJoinBy", I mostly struggled with the type "Merge" (how to discard "MergePredicate" and "MergeLte" for `I::Item::le`).
[Here](https://github.com/Philippe-Cholet/itertools/commit/2f45b173d68215aa4272aaeac0ac6f09d3d3c72e), `type Merge<I, J> = MergeBy<I, J, MergeLte>;` becomes `type Merge<I, J> = MergeBy<I, J, fn(&<I as Iterator>::Item, &<J as Iterator>::Item) -> bool>;`.
Then `trait MergePredicate<T>` and `struct MergeLte` can be removed.
Finally, `MergeBy<I, J, F>` basically wraps `MergeJoinBy<I, J, F, bool>`.
So in `impl Iterator`, I use `Either::into_inner` to convert `Either<T, T>` to `T`.

- "MergeJoinBy" don't have `impl FusedIterator` while "MergeBy" did. Not sure what to do here.
- (`MergeJoinBy<I, J, F, bool>` and) `MergeBy<I, J, F>` lost some `size_hint` information because "EitherOrBoth" sometimes use one element of each iterator in one item (`Both` variant) while "Either" does not. Unless I find a fix.
- Should I `#[inline]` methods in `impl Iterator for MergeBy` ?

If this is satisfying, should I merge files "merge_join.rs" into the newly created "adaptors/merge.rs" ?

**EDIT:** In "OrderingOrBool" trait, I [added](https://github.com/Philippe-Cholet/itertools/commit/f51563f882bee8abfa1d9329f625351521dd8491) `fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint;` to fix the small `size_hint` issue mentionned above.
Thank you for staying in touch. I see there are some valid questions, so I suggest to first focus on supporting `bool` (since that's probably what's needed anyway if we want to merge `MergeBy` and `MergeJoinBy`, i.e. let's focus on your first commit (https://github.com/Philippe-Cholet/itertools/commit/5ad6f70e46c0e2404f86c5eaeed800adec27d9cc).

Please see my comments there for specifics, but probably most important: Is the fourth type parameter in `MergeJoinBy` really needed? (I would guess "no", because it could be inferred from `F`.)

In addition, this commit introduced several trait bounds that look unneeded to me. We should add only the trait bounds  required to support `bool` and these that keep the code in line with what's already there.

The idea of your transformation (i.e. having `left`, `right`, `both` as customization points) looks correct, but the `unreachable` makes me think if there's a way to refactor this to get rid of it. Did you try something in this direction?

As said, let's keep it at supporting `bool` for now, but here's some thoughts regarding your questions anyway:


> "MergeJoinBy" don't have `impl FusedIterator` while "MergeBy" did. Not sure what to do here.

I think we should fuse the input iterators (i.e. adapt `MergeJoinBy`'s strategy and document this. (Sidenote: That's exactly the type of problem that would be avoided if the structs had been merged.)

> (`MergeJoinBy<I, J, F, bool>` and) `MergeBy<I, J, F>` lost some `size_hint` information because "EitherOrBoth" sometimes use one element of each iterator in one item (`Both` variant) while "Either" does not. Unless I find a fix.

Good catch. Maybe that precludes merging the structs... We'll have to look into that.


> Should I `#[inline]` methods in `impl Iterator for MergeBy` ?

I think most of the time we rely on the compiler, but afaik there are no definitive guidelines about `[inline]`.
You might have missed (or not) an edit of my comment, a [fix](https://github.com/Philippe-Cholet/itertools/commit/f51563f882bee8abfa1d9329f625351521dd8491) about size_hint, seems simple enough to me.
Instead of creating a trait for Ordering/bool, maybe we can create a trait for `FnMut(&I, &J) -> T`, I'll come back to you.
I did not find a way to have only three types. I was going with a trait MergePredicate (idea from how `MergeBy` currently works)

    pub trait MergePredicate<I, J> { // or <I, J, T>
        type Item;
        // fn merge_pred(&mut self, left: &I, right: &J) -> T; // return self(left, right)
        fn merge(&mut self, left: I, right: J) -> (Option<I>, Option<J>, Self::Item);
        // (item to put back left, same for right, next_item)
        // then I can match against Ordering/bool variants, and don't need one unreachable both method.
        fn left(left: I) -> Self::Item;
        fn right(right: J) -> Self::Item;
    }
With `MergePredicate<I, J>`, I get an error about "conflicting implementations".

    impl<I, J, F: FnMut(&I, &J) -> Ordering> MergePredicate<I, J> for F { ... }
    impl<I, J, F: FnMut(&I, &J) -> bool> MergePredicate<I, J> for F { ... }
I suppose it worries that there is a type out there implementing both `FnMut(&I, &J) -> Ordering` and `FnMut(&I, &J) -> bool`. Seems impossible but it's an error.
With `MergePredicate<I, J, T>` (`T` being `Ordering` or `bool`), this problem vanishes but I get another, a weird one IMO about:

    impl<I, J, F, T> Iterator for MergeJoinBy<I, J, F>
        where I: Iterator,
              J: Iterator,
              F: MergePredicate<I::Item, J::Item, T>,
    { ... }
> error[[E0207](https://doc.rust-lang.org/error_codes/E0207.html)]: the type parameter `T` is not constrained by the impl trait, self type, or predicates

The constraint on `F` does not constrain `T` at all apparently.

Hence I add `T` as a fourth type to MergeJoinBy. Only to get that it's not used (add a `PhantomData<T>` field leads to a compiler error in tests about "type annotation", even with constraint `F: MergePredicate<I, J, T>`) so with `F: FnMut(&I::Item, &J::Item) -> T` as a constraint on MergeJoinBy, then it works with `MergePredicate<I, J, T>` being a super trait of `FnMut(&I, &J) -> T`! Harsh right?!

So I think `T` should be inferred from `F` as you guessed but not by the current compiler or this trait way.
It solves the issue you have with unreachable. I'll make a commit after dinner for you to see.
Here is a new [commit](https://github.com/Philippe-Cholet/itertools/commit/d8bdac565c0e0fd963c58234e69addffe2acaeed) (in a new branch) with `trait MergePredicate<I, J, T>: FnMut(&I, &J) -> T` (see previous comment). It better matches `Ordering` & `bool` variants. And `merge_join_by` constraints seems nicer ?
If you don't want the previous OrderingOrBool or this MergePredicate, I'm open to suggestions.
Not a priority at this moment but either way, there is some code duplication about putting back right/left elements.
Following the last commit, add a PhantomData field on MergeJoinBy would allow me to remove `F: FnMut(...) -> T` constraint on the struct definition, impl Clone and impl Debug of MergeJoinBy, all three that **were added** in the last commit, and MergePredicate does not need to be a supertrait.
So the new [PhantomData commit](https://github.com/Philippe-Cholet/itertools/commit/5eb0eb5d8881b8720b4dcf79486bb20ad8c47bf7) but you might prefer to see the diff if these last two were squashed: [comparison here](https://github.com/Philippe-Cholet/itertools/compare/ad2e401862d80d34e380d343758f71a533dcf36b..5eb0eb5d8881b8720b4dcf79486bb20ad8c47bf7) (the changes on constraints are way more natural/minimalist).
Thanks for the update. I like how you were able to avoid the `unreachable`. I would assume that the compiler is smart enough to inline `fn merge` and avoid the temporary `Option`s.

I still think it should be possible without `T` in `MergeJoinBy` - see this prototype: https://github.com/phimuemue/rust-itertools/commit/072fe00e666f3d6fa5616af3176e2ae6e294516c. (I consider it important to not change `MergeJoinBy`'s interface (if not strictly required), as it right now is already complex enough.)

Looking at this prototype, it seems that `MergePredicate` is not even needed anymore. If you want to continue working on this, you can use the prototype as a starting point, and get rid of the rough edges. 
So I got rid of MergePredicate [there](https://github.com/Philippe-Cholet/itertools/commit/d1535e945e05b4b49084127d81340d00d36b8bf3). The [diff](https://github.com/Philippe-Cholet/itertools/compare/ad2e401862d80d34e380d343758f71a533dcf36b..d1535e945e05b4b49084127d81340d00d36b8bf3) between before the issue and now, it feels right.

I could avoid code duplication (code below is in four Iterator methods), or not (it's not that bad).

    if let Some(left) = left { self.left.put_back(left); }
    if let Some(right) = right { self.right.put_back(right); }
I could work on bringing `struct MergeBy` into `src/merge_join.rs` or another place ?

I'd say we should focus on supporting `bool` before moving stuff around, especially in light of https://github.com/rust-itertools/itertools/issues/702.

* `merge` never returns `(Some(...), Some(...), ...)`, but the caller always checks both `Option`s. On top of that, when we call `merge`, this is *always* followed by `put_back`s. As such, we could think about moving the `put_back` into `merge` - or possibly at least returning `Option<Either<I::Item, J::Item>>`. IMO you do not have to do this, because would I hope the compiler is smart enough to get rid of all the checks, but please add a comment that we thought about this.
* `merge_join_by` should only accept `T` where `T: OrderingOrBool`.
* Could you please add some (possibly quickcheck) tests. In particular, we should `assert` that the `bool`-variant behaves the same as the `Ordering`-variant as long as the `Ordering` is not `equal`. And we should `assert` that the `bool`-variant yields the same elements (modulo wrapping in `Either`) as the simpler `MergeBy`.
* In the documentation, instead of "in the first case", let's be more explicit: "If `cmp_fn` returns `Ordering`"; similar for the other case. The `bool` case should probably mention that this somewhat corresponds to `cmp_fn` returning if the first argument is considered "less" than the second argument. I like your idea of re-using the example here - nice.
Use `MergeJoinBy` for the internal of `MergeBy` to merge their implementation in a single file is quite easy anyway.

All four points are done [here](https://github.com/Philippe-Cholet/itertools/commit/988a222bb36be05afbc2596dbd874ec205ab2014) (and [small stupid duplicates removed](https://github.com/Philippe-Cholet/itertools/commit/dc359e00302dbebd44895aedcdcef97cafb8ab59)). Although, I'm not sure the documentation sentence about "less" is clear enough. I changed the common example to show that the `Both` variant does not always split into consecutives `Left, Right` variants (when one of the two iterators is not ascending, it's not a precondition after all).
I should not have unwrapped Either in the first quickcheck ([commit](https://github.com/Philippe-Cholet/itertools/commit/ac5c357e11b3bf47878ce50590eea3f19b794935)).
I tried with `put_back`s in `merge`, and while its definition certainly would be not pretty, the rest would be straightforward (just `let elem = T::merge(&mut self, left, right);`).

    pub trait OrderingOrBool<L, R> {    // L R for types, I J for iterators below
        type MergeResult;
        fn left(left: L) -> Self::MergeResult;
        fn right(right: R) -> Self::MergeResult;
        fn merge<I, J, F>(it: &mut MergeJoinBy<I, J, F>, left: L, right: R) -> Self::MergeResult
            where I: Iterator<Item = L>,
                  J: Iterator<Item = R>,
                  F: FnMut(&L, &R) -> Self;    // match/if  (it.cmp_fn)(&left, &right)  {...}
        fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint;
    }
Hi, thanks so far. I realized we should keep the inners of `OrderingOrBool` private (so that we can change them later). We could employ a similar technique to [`HomogenousTuple`](https://docs.rs/itertools/0.10.5/itertools/traits/trait.HomogeneousTuple.html) which is a facade for `TupleCollect`.
`OrderingOrBool` is still private (we can't access it from outside itertools) because in "lib.rs", the module "merge_join" is not public, and `OrderingOrBool` is not `pub use`d anywhere else.
But `HomogenousTuple` is public (I can `use itertools::traits::HomogeneousTuple;` in a personal project).
Oh, cool. Maybe open a PR so we can have a last review?
Now that the PR is merged, we can merge implementations as you first wanted. The way I see it, `trait MergePredicate<T>` and `struct MergeLte` are useless (being respectively replaced by `FnMut(&T, &T) -> bool` and `PartialOrd::le`).

    pub type Merge<I, J> = MergeBy<I, J, MergeLte>;
    // becomes
    pub type Merge<I, J> = MergeBy<I, J, fn(&<I as Iterator>::Item, &<J as Iterator>::Item) -> bool>;
Then

    pub fn merge<I, J>(i: I, j: J) -> Merge<<I as IntoIterator>::IntoIter, <J as IntoIterator>::IntoIter>
        where I: IntoIterator,
              J: IntoIterator<Item = I::Item>,
              I::Item: PartialOrd
    {
        // merge_by_new(i, j, MergeLte)
        // becomes
        merge_by_new(i, j, PartialOrd::le)
    }

And MergeBy uses MergeJoinBy in its internal

    pub struct MergeBy<I, J, F>
        where I: Iterator,
              J: Iterator<Item = I::Item>
    {
        iter: MergeJoinBy<I, J, F>,
    }
The rest is really straightforward. I know it will pass tests as I experimented before.
If that seems reasonable to you then my question is where do we move all the code, in which file? Or we move it a last step? Or as a first?
Hi @Philippe-Cholet , I think this design has two drawbacks:

- Using `fn` (note the lower case) buys some flexibility at the expense of possibly worsening runtime, as it is a function _pointer_. Thus, we should avoid it.
- Having a field `iter` in `MergeBy` would require that we implement all iterator methods and manually forward them to `iter`. Instead, we could make `MergeBy` a type alias for a particular `MergeJoinBy` specialization.

Without having looked at the code too closely, I think we should express the affected iterators all as instances of `MergeJoinBy`, and customize `MergeJoinBy` essentially by one parameter that

- encapsulates the predicate which decides how elements are merged/ordered
- converts the raw iterator elements into the merged types.

This could be realized by extending `OrderingOrBool`.
I kinda expected it about `fn`.
About `iter`, I thought about it and I didn't think it was an issue because I don't think it would make sense to implement more than `next/size_hint/count/last/nth`. I was more annoyed by `Either::into_inner` decapsulation (see below, straightforward). I'm gonna try going your way.

    impl<I, J, F> Iterator for MergeBy<I, J, F>
        where I: Iterator,
              J: Iterator<Item = I::Item>,
              F: FnMut(&I::Item, &I::Item) -> bool,
    {
        type Item = I::Item;
        fn next(&mut self) -> Option<Self::Item> {
            self.iter.next().map(Either::into_inner)
        }
        fn size_hint(&self) -> SizeHint {
            self.iter.size_hint()
        }
        fn count(self) -> usize {
            self.iter.count()
        }
        fn last(self) -> Option<Self::Item> {
            self.iter.last().map(Either::into_inner)
        }
        fn nth(&mut self, n: usize) -> Option<Self::Item> {
            self.iter.nth(n).map(Either::into_inner)
        }
    }
After [moving](https://github.com/Philippe-Cholet/itertools/commit/7aee5796080a5bd72d6151fdada0404e8a68bc61) Merge/MergeBy into merge_join module to manipulate them all easily, I'm just really stuck.

To be able to keep `MergeLte` and not use `PartialOrd::le` (and therefore not a function pointer in `Merge` type), we can't keep `F: FnMut(&I::Item, &J::Item) -> T` in `impl Iterator for MergeJoinBy`. But use something like `F: MergePredicate<I::Item, J::Item, T>` instead does not [constrain `T` anymore](https://doc.rust-lang.org/error_codes/E0207.html) leading to introduce `T` back in `MergeJoinBy<I, J, F, T>` with a phantom field. I don't see a way around this.

Both `MergeBy` and `MergeJoinBy` use functions returning `bool` so in order for `MergeBy` to be an instance of `MergeJoinBy`, the only way I saw was adding _another_ parameter (`const SAME: bool` (meaning `L == R ?`), a const one hence breaking the MSRV) to distinguish them. You can see the changes [here](https://github.com/Philippe-Cholet/itertools/commit/0781f1d00609f411b703163c5026dd56b8a1eb10). I'll revert them if you can't salvage any of this.
About `F: MergePredicate<I::Item, J::Item, T>` not contraining `T`, the answer was `F: MergePredicate<I::Item, J::Item, Out = T>`. Then no phantom field. Commit [here](https://github.com/Philippe-Cholet/itertools/commit/587261f7f6bb443356af773a505dbbce2d057036).
I think I'm finally on the right path!

To get rid of `const SAME: bool`, I wrap the function `F` in `MergeFuncLR` (result wrapped `EitherOrBoth/Either<L,R>`) and `MergeFuncT` (result unwrapped `T`).
Those `MergeFuncLR/T` have a parameter `T` (phantom field) to not have conflicting implementations of `MergePredicate<L, R>`.

In `merge_join_by` definition, in order for the compiler to keep guessing left/right types, I kept `F: FnMut(&Self::Item, &J::Item) -> T`. But to not add `F: MergePredicate<Self::Item, J::Item>` that felt duplicate, I removed `T: OrderingOrBool...`, the user might lose `OrderingOrBool` information.

Commit [there](https://github.com/Philippe-Cholet/itertools/commit/6b8750c27f60976ee388d93f9d538fe27cd21b11) but you might prefer to see the [current code](https://github.com/Philippe-Cholet/itertools/blob/issue-701-part2/src/merge_join.rs).
Hi there, thanks for going through this. I do not have too much time right now, so just quick feedback:

I think this is indeed taking the right turns! I skimmed the code, and I saw that you have four merge predicates:

* `merge` -> `MergeJoinBy<..., MergeFuncT<MergeLte, bool>>`
* `merge_by` -> `MergeJoinBy<..., MergeFuncT<F, bool>>`
* `merge_join_by(...bool)` -> `MergeJoinBy<..., MergeFuncLR<F, bool>>`
* `merge_join_by(...Ordering)` -> `MergeJoinBy<..., MergeFuncLR<F, Ordering>>`

Looks simple and good. Maybe we can simplify some `MergeFuncT`/`MergeFuncLR` internals (does `MergeFuncT` need its second parameter?), but the scaffold so far seems right.

I think that `MergeJoinBy` it should `impl FusedIterator`, shouldn't it?
Thanks for the quick feedback.

I only commented out `FusedIterator` temporarily, I definitely think `MergeJoinBy` should implement it ([commit](https://github.com/Philippe-Cholet/itertools/commit/6f0442426fbf700140a6856b1d4b96295232375d)) like many other iterators. After we solve the current issue, I'll probably make an issue (or use an old one if any) as I investigated it.

Good catch, `MergeFuncT<F, bool>` does not need the second (phantom) parameter since `T` always is `bool` so `MergeFuncT<F>` is enough. Therefore new [commit](https://github.com/Philippe-Cholet/itertools/commit/81d371f184232de69815641623ac819aaa15d689) in which I also simplify `MergeFuncLR` and `MergeFuncT` to "tuple structs".

Note 1: But `MergeFuncLR` needs it to avoid conflicting implementations of `MergePredicate<L, R>`.

    impl<L, R, F: FnMut(&L, &R) -> Ordering> MergePredicate<L, R> for MergeFuncLR<F/*, Ordering*/> { ... }
    impl<L, R, F: FnMut(&L, &R) -> bool> MergePredicate<L, R> for MergeFuncLR<F/*, bool*/> { ... }

Some **impossible `F`** could implement both `FnMut(&L, &R) -> Ordering` and `FnMut(&L, &R) -> bool`. Annoying but unavoidable IMO.

Note 2: `impl<...> MergePredicate<T, T> for MergeFuncT<MergeLte>` is mostly copy/paste of `impl<...> MergePredicate<T, T> for MergeFuncT<F>` with `self.0(&left, &right)` replaced by `left <= right`.

EDIT: I could write a new `fn merge_join_by_new<I: IntoIterator, J: IntoIterator, F>(left: I, right: J, f: F) -> MergeJoinBy<I::IntoIter, J::IntoIter, F>` to avoid `MergeJoinBy {
        left: put_back(left.into_iter().fuse()),
        right: put_back(right.into_iter().fuse()),
        cmp_fn: ...,
    }` **three times** when only `cmp_fn` changes.
From its [trait documentation](https://doc.rust-lang.org/std/iter/trait.FusedIterator.html), we _should implement `FusedIterator` for all iterators that always return `None` once they've done it once_. But the real question IMO is **on which conditions?!**

Here, I think I made a mistake (being too fast). `MergeJoinBy` fuses both left and right iterators even if they were not before. So I think we should

    impl<I, J, F, T> FusedIterator for MergeJoinBy<I, J, F>
        where I: Iterator,
              J: Iterator,
              F: MergePredicate<I::Item, J::Item, Out = T>,
    {}
instead of

    impl<I, J, F, T> FusedIterator for MergeJoinBy<I, J, F>
        where I: FusedIterator,
              // ~~~~~
              J: FusedIterator,
              // ~~~~~
              F: MergePredicate<I::Item, J::Item, Out = T>,
    {}
Sounds right.
FusedIterator' [small fix](https://github.com/Philippe-Cholet/itertools/commit/042ca7e47b5404b311aecdc1561008112842c3d5).
Currently: [lib.rs](https://github.com/Philippe-Cholet/itertools/blob/issue-701-part2/src/lib.rs#L1068), [merge_join.rs](https://github.com/Philippe-Cholet/itertools/blob/issue-701-part2/src/merge_join.rs), [big diff](https://github.com/rust-itertools/itertools/compare/master...Philippe-Cholet:itertools:issue-701-part2).

---
> In `merge_join_by` definition, in order for the compiler to keep guessing left/right types, I kept `F: FnMut(&Self::Item, &J::Item) -> T`. But to not add `F: MergePredicate<Self::Item, J::Item>` that felt duplicate, I removed `T: OrderingOrBool...`, the user might lose "`OrderingOrBool` information".

I could

    pub trait IsOrderingOrBool {}
    impl IsOrderingOrBool for Ordering {}
    impl IsOrderingOrBool for bool {}
    // then add to the function definition
        T: merge_join::IsOrderingOrBool,
I think that would be clearer to people. What's your thought on that?

Then should I open a pull request for review, or do you see changes to do?
@phimuemue Little reminder.
Hi, thanks for keeping in touch.

What I see:
* Could we keep the return type of `fn merge_join_by` to be `MergeJoinBy<Self, J::IntoIter, F>`, and make `MergeJoinBy` a type alias for some `InternalMergeJoinBy`? (I'd like to avoid our auxiliary structs (such as `MergeFunc`) appearing in public signatures.)
* I really like that you just laid out the four `MergePredicate` variants (instead of introducing another level of indirection for the `Merge`/`MergeBy` variants).
* Always implementing `FusedIterator` is correct imho.

If all this passes our tests, can you open a PR?
Thank you too for this long discussion, I initially thought it would be quickier.

I don't like `MergeFuncLR` to be public either, so I thought of this `InternalMergeJoinBy` but what it means for `MergeJoinBy` is a fourth type (`pub type MergeJoinBy<I, J, F, T> = InternalMergeJoinBy<I, J, MergeFuncLR<F, T>>;`) which we previously tried to avoid. Because we can't write something like `<F as FnMut(...)>::Output` to infer `T` from `F` (from what I understand because `Fn*` traits aren't stabilized).

I don't see any way to avoid it, but maybe you do. Currently, Philippe-Cholet@c622606fa4c9d6ca85b485e6bd7cc8004a249e24 . I'll make a PR once you find a way or are ok with the 4th type.
I think I'm fine with `InternalMergeJoinBy` - I agree it's a bit ugly, but the ugliness is not leaked too much to the user. And I hope that - once we find something better - we can clean up the internals.

Fix patch:
diff --git a/src/lib.rs b/src/lib.rs
index 7dc40370b..ec1bbca2a 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1075,7 +1075,6 @@ pub trait Itertools: Iterator {
     where
         J: IntoIterator,
         F: FnMut(&Self::Item, &J::Item) -> T,
-        T: merge_join::OrderingOrBool<Self::Item, J::Item>,
         Self: Sized,
     {
         merge_join_by(self, other, cmp_fn)
diff --git a/src/merge_join.rs b/src/merge_join.rs
index 1769aaf3a..c83159186 100644
--- a/src/merge_join.rs
+++ b/src/merge_join.rs
@@ -1,7 +1,7 @@
 use std::cmp::Ordering;
 use std::fmt;
-use std::iter::Fuse;
-use std::iter::{FusedIterator, Peekable};
+use std::iter::{Fuse, FusedIterator};
+use std::marker::PhantomData;
 
 use either::Either;
 
@@ -11,19 +11,9 @@ use crate::size_hint::{self, SizeHint};
 #[cfg(doc)]
 use crate::Itertools;
 
-pub trait MergePredicate<T> {
-    fn merge_pred(&mut self, a: &T, b: &T) -> bool;
-}
-
 #[derive(Clone, Debug)]
 pub struct MergeLte;
 
-impl<T: PartialOrd> MergePredicate<T> for MergeLte {
-    fn merge_pred(&mut self, a: &T, b: &T) -> bool {
-        a <= b
-    }
-}
-
 /// An iterator adaptor that merges the two base iterators in ascending order.
 /// If both base iterators are sorted (ascending), the result is sorted.
 ///
@@ -62,30 +52,10 @@ where
 ///
 /// See [`.merge_by()`](crate::Itertools::merge_by) for more information.
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
-pub struct MergeBy<I, J, F>
-where
-    I: Iterator,
-    J: Iterator<Item = I::Item>,
-{
-    a: Peekable<I>,
-    b: Peekable<J>,
-    fused: Option<bool>,
-    cmp: F,
-}
-
-impl<I, J, F> fmt::Debug for MergeBy<I, J, F>
-where
-    I: Iterator + fmt::Debug,
-    J: Iterator<Item = I::Item> + fmt::Debug,
-    I::Item: fmt::Debug,
-{
-    debug_fmt_fields!(MergeBy, a, b);
-}
-
-impl<T, F: FnMut(&T, &T) -> bool> MergePredicate<T> for F {
-    fn merge_pred(&mut self, a: &T, b: &T) -> bool {
-        self(a, b)
-    }
+pub struct MergeBy<I: Iterator, J: Iterator, F> {
+    left: PutBack<Fuse<I>>,
+    right: PutBack<Fuse<J>>,
+    cmp_fn: F,
 }
 
 /// Create a `MergeBy` iterator.
@@ -93,72 +63,14 @@ pub fn merge_by_new<I, J, F>(a: I, b: J, cmp: F) -> MergeBy<I::IntoIter, J::Into
 where
     I: IntoIterator,
     J: IntoIterator<Item = I::Item>,
-    F: MergePredicate<I::Item>,
 {
     MergeBy {
-        a: a.into_iter().peekable(),
-        b: b.into_iter().peekable(),
-        fused: None,
-        cmp,
+        left: put_back(a.into_iter().fuse()),
+        right: put_back(b.into_iter().fuse()),
+        cmp_fn: cmp,
     }
 }
 
-impl<I, J, F> Clone for MergeBy<I, J, F>
-where
-    I: Iterator,
-    J: Iterator<Item = I::Item>,
-    Peekable<I>: Clone,
-    Peekable<J>: Clone,
-    F: Clone,
-{
-    clone_fields!(a, b, fused, cmp);
-}
-
-impl<I, J, F> Iterator for MergeBy<I, J, F>
-where
-    I: Iterator,
-    J: Iterator<Item = I::Item>,
-    F: MergePredicate<I::Item>,
-{
-    type Item = I::Item;
-
-    fn next(&mut self) -> Option<Self::Item> {
-        let less_than = match self.fused {
-            Some(lt) => lt,
-            None => match (self.a.peek(), self.b.peek()) {
-                (Some(a), Some(b)) => self.cmp.merge_pred(a, b),
-                (Some(_), None) => {
-                    self.fused = Some(true);
-                    true
-                }
-                (None, Some(_)) => {
-                    self.fused = Some(false);
-                    false
-                }
-                (None, None) => return None,
-            },
-        };
-        if less_than {
-            self.a.next()
-        } else {
-            self.b.next()
-        }
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        // Not ExactSizeIterator because size may be larger than usize
-        size_hint::add(self.a.size_hint(), self.b.size_hint())
-    }
-}
-
-impl<I, J, F> FusedIterator for MergeBy<I, J, F>
-where
-    I: FusedIterator,
-    J: FusedIterator<Item = I::Item>,
-    F: MergePredicate<I::Item>,
-{
-}
-
 /// Return an iterator adaptor that merge-joins items from the two base iterators in ascending order.
 ///
 /// [`IntoIterator`] enabled version of [`Itertools::merge_join_by`].
@@ -171,23 +83,29 @@ where
     I: IntoIterator,
     J: IntoIterator,
     F: FnMut(&I::Item, &J::Item) -> T,
-    T: OrderingOrBool<I::Item, J::Item>,
 {
-    MergeJoinBy {
+    MergeBy {
         left: put_back(left.into_iter().fuse()),
         right: put_back(right.into_iter().fuse()),
-        cmp_fn,
+        cmp_fn: MergeFuncLR(cmp_fn, PhantomData),
     }
 }
 
 /// An iterator adaptor that merge-joins items from the two base iterators in ascending order.
 ///
 /// See [`.merge_join_by()`](crate::Itertools::merge_join_by) for more information.
-#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
-pub struct MergeJoinBy<I: Iterator, J: Iterator, F> {
-    left: PutBack<Fuse<I>>,
-    right: PutBack<Fuse<J>>,
-    cmp_fn: F,
+pub type MergeJoinBy<I, J, F> =
+    MergeBy<I, J, MergeFuncLR<F, <F as FuncLR<<I as Iterator>::Item, <J as Iterator>::Item>>::T>>;
+
+#[derive(Clone, Debug)]
+pub struct MergeFuncLR<F, T>(F, PhantomData<T>);
+
+pub trait FuncLR<L, R> {
+    type T;
+}
+
+impl<L, R, T, F: FnMut(&L, &R) -> T> FuncLR<L, R> for F {
+    type T = T;
 }
 
 pub trait OrderingOrBool<L, R> {
@@ -197,11 +115,11 @@ pub trait OrderingOrBool<L, R> {
     // "merge" never returns (Some(...), Some(...), ...) so Option<Either<I::Item, J::Item>>
     // is appealing but it is always followed by two put_backs, so we think the compiler is
     // smart enough to optimize it. Or we could move put_backs into "merge".
-    fn merge(self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult);
+    fn merge(&mut self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult);
     fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint;
 }
 
-impl<L, R> OrderingOrBool<L, R> for Ordering {
+impl<L, R, F: FnMut(&L, &R) -> Ordering> OrderingOrBool<L, R> for MergeFuncLR<F, Ordering> {
     type MergeResult = EitherOrBoth<L, R>;
     fn left(left: L) -> Self::MergeResult {
         EitherOrBoth::Left(left)
@@ -209,8 +127,8 @@ impl<L, R> OrderingOrBool<L, R> for Ordering {
     fn right(right: R) -> Self::MergeResult {
         EitherOrBoth::Right(right)
     }
-    fn merge(self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult) {
-        match self {
+    fn merge(&mut self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult) {
+        match self.0(&left, &right) {
             Ordering::Equal => (None, None, EitherOrBoth::Both(left, right)),
             Ordering::Less => (None, Some(right), EitherOrBoth::Left(left)),
             Ordering::Greater => (Some(left), None, EitherOrBoth::Right(right)),
@@ -228,7 +146,7 @@ impl<L, R> OrderingOrBool<L, R> for Ordering {
     }
 }
 
-impl<L, R> OrderingOrBool<L, R> for bool {
+impl<L, R, F: FnMut(&L, &R) -> bool> OrderingOrBool<L, R> for MergeFuncLR<F, bool> {
     type MergeResult = Either<L, R>;
     fn left(left: L) -> Self::MergeResult {
         Either::Left(left)
@@ -236,8 +154,8 @@ impl<L, R> OrderingOrBool<L, R> for bool {
     fn right(right: R) -> Self::MergeResult {
         Either::Right(right)
     }
-    fn merge(self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult) {
-        if self {
+    fn merge(&mut self, left: L, right: R) -> (Option<L>, Option<R>, Self::MergeResult) {
+        if self.0(&left, &right) {
             (None, Some(right), Either::Left(left))
         } else {
             (Some(left), None, Either::Right(right))
@@ -249,7 +167,49 @@ impl<L, R> OrderingOrBool<L, R> for bool {
     }
 }
 
-impl<I, J, F> Clone for MergeJoinBy<I, J, F>
+impl<T, F: FnMut(&T, &T) -> bool> OrderingOrBool<T, T> for F {
+    type MergeResult = T;
+    fn left(left: T) -> Self::MergeResult {
+        left
+    }
+    fn right(right: T) -> Self::MergeResult {
+        right
+    }
+    fn merge(&mut self, left: T, right: T) -> (Option<T>, Option<T>, Self::MergeResult) {
+        if self(&left, &right) {
+            (None, Some(right), left)
+        } else {
+            (Some(left), None, right)
+        }
+    }
+    fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint {
+        // Not ExactSizeIterator because size may be larger than usize
+        size_hint::add(left, right)
+    }
+}
+
+impl<T: PartialOrd> OrderingOrBool<T, T> for MergeLte {
+    type MergeResult = T;
+    fn left(left: T) -> Self::MergeResult {
+        left
+    }
+    fn right(right: T) -> Self::MergeResult {
+        right
+    }
+    fn merge(&mut self, left: T, right: T) -> (Option<T>, Option<T>, Self::MergeResult) {
+        if left <= right {
+            (None, Some(right), left)
+        } else {
+            (Some(left), None, right)
+        }
+    }
+    fn size_hint(left: SizeHint, right: SizeHint) -> SizeHint {
+        // Not ExactSizeIterator because size may be larger than usize
+        size_hint::add(left, right)
+    }
+}
+
+impl<I, J, F> Clone for MergeBy<I, J, F>
 where
     I: Iterator,
     J: Iterator,
@@ -260,32 +220,31 @@ where
     clone_fields!(left, right, cmp_fn);
 }
 
-impl<I, J, F> fmt::Debug for MergeJoinBy<I, J, F>
+impl<I, J, F> fmt::Debug for MergeBy<I, J, F>
 where
     I: Iterator + fmt::Debug,
     I::Item: fmt::Debug,
     J: Iterator + fmt::Debug,
     J::Item: fmt::Debug,
 {
-    debug_fmt_fields!(MergeJoinBy, left, right);
+    debug_fmt_fields!(MergeBy, left, right);
 }
 
-impl<I, J, F, T> Iterator for MergeJoinBy<I, J, F>
+impl<I, J, F> Iterator for MergeBy<I, J, F>
 where
     I: Iterator,
     J: Iterator,
-    F: FnMut(&I::Item, &J::Item) -> T,
-    T: OrderingOrBool<I::Item, J::Item>,
+    F: OrderingOrBool<I::Item, J::Item>,
 {
-    type Item = T::MergeResult;
+    type Item = F::MergeResult;
 
     fn next(&mut self) -> Option<Self::Item> {
         match (self.left.next(), self.right.next()) {
             (None, None) => None,
-            (Some(left), None) => Some(T::left(left)),
-            (None, Some(right)) => Some(T::right(right)),
+            (Some(left), None) => Some(F::left(left)),
+            (None, Some(right)) => Some(F::right(right)),
             (Some(left), Some(right)) => {
-                let (left, right, next) = (self.cmp_fn)(&left, &right).merge(left, right);
+                let (left, right, next) = self.cmp_fn.merge(left, right);
                 if let Some(left) = left {
                     self.left.put_back(left);
                 }
@@ -298,7 +257,7 @@ where
     }
 
     fn size_hint(&self) -> SizeHint {
-        T::size_hint(self.left.size_hint(), self.right.size_hint())
+        F::size_hint(self.left.size_hint(), self.right.size_hint())
     }
 
     fn count(mut self) -> usize {
@@ -310,7 +269,7 @@ where
                 (None, Some(_right)) => break count + 1 + self.right.into_parts().1.count(),
                 (Some(left), Some(right)) => {
                     count += 1;
-                    let (left, right, _) = (self.cmp_fn)(&left, &right).merge(left, right);
+                    let (left, right, _) = self.cmp_fn.merge(left, right);
                     if let Some(left) = left {
                         self.left.put_back(left);
                     }
@@ -328,13 +287,13 @@ where
             match (self.left.next(), self.right.next()) {
                 (None, None) => break previous_element,
                 (Some(left), None) => {
-                    break Some(T::left(self.left.into_parts().1.last().unwrap_or(left)))
+                    break Some(F::left(self.left.into_parts().1.last().unwrap_or(left)))
                 }
                 (None, Some(right)) => {
-                    break Some(T::right(self.right.into_parts().1.last().unwrap_or(right)))
+                    break Some(F::right(self.right.into_parts().1.last().unwrap_or(right)))
                 }
                 (Some(left), Some(right)) => {
-                    let (left, right, elem) = (self.cmp_fn)(&left, &right).merge(left, right);
+                    let (left, right, elem) = self.cmp_fn.merge(left, right);
                     if let Some(left) = left {
                         self.left.put_back(left);
                     }
@@ -355,10 +314,10 @@ where
             n -= 1;
             match (self.left.next(), self.right.next()) {
                 (None, None) => break None,
-                (Some(_left), None) => break self.left.nth(n).map(T::left),
-                (None, Some(_right)) => break self.right.nth(n).map(T::right),
+                (Some(_left), None) => break self.left.nth(n).map(F::left),
+                (None, Some(_right)) => break self.right.nth(n).map(F::right),
                 (Some(left), Some(right)) => {
-                    let (left, right, _) = (self.cmp_fn)(&left, &right).merge(left, right);
+                    let (left, right, _) = self.cmp_fn.merge(left, right);
                     if let Some(left) = left {
                         self.left.put_back(left);
                     }
@@ -370,3 +329,11 @@ where
         }
     }
 }
+
+impl<I, J, F> FusedIterator for MergeBy<I, J, F>
+where
+    I: Iterator,
+    J: Iterator,
+    F: OrderingOrBool<I::Item, J::Item>,
+{
+}


Test patch: