Question: Could the compiler preserve constraints of non-inferred type arguments

Sorry, if the title is not very clear but I really do not know how to synthesis this in a few words.
Let me explain it in details and provide a motivating example of why this functionality would be useful.

Imagine a definition like this:

def foo[B, C](bar: Bar[B, C])(f: A => B): C

Where instances of bar does not really infer what B should be, but does impose constraints on it, like requiring an instance of Ordering. I would like if the compiler could carry that constraint such that when inferring B from the function, it ensures that constraint is satisfied.

Now, I know it may be hard to imagine when that could be useful, so here is an example.
I was trying to implement the following function:

// It was actually an extension method on IterableOnce.
def groupMapTo[A, K, B, CC, MC](data: IterableOnce[A])
                               (colFactory: Factory[B, CC], mapFactory: Factory[(K, B), MC] = Map)
                               (key: A => K)(f: A => B): MC

// So it could be used like this:
list.groupMapTo(colFactory = SortedSet)(

The above definition doesn’t work because B is already inferred to be Nothing; and thus it had to be changed to require the factories after the functions, which made calling this function less readable (IMHO).
It would be great if it could just wait for f to know what B is. Nevertheless, since I used SortedSet instead of a normal Set, it requires an Ordering, so even if it shouldn’t infer what B is, it should add that constraint. So, if f is inferred to return something which is not sortable, then it wouldn’t compile.
(Similarly, it would be good if it also could carry type bounds)

Finally, the main objective of this post would be to answer the following three questions:

  1. Is this just an improvement over the compiler or is this considered a change in the language specifications?
  2. Regardless of the previous question, how feasible / difficult would be to implement this change?
  3. Does more people find this useful? Does anyone have other examples?

I’m wondering whether B is really not inferred, or rather it is inferred, and it just happens that the inferred type is Nothing? I understand you would prefer it if the compiler, when first encountering B, would somehow mark B as “unknown type” and then decide what B should be later. I’m not sure that’s how it works, though, I’ve been assuming the compiler decides that Nothing fits and therefore gets chosen and not reconsidered later.

I’m not an expert, but what you are asking for sounds like backtracking or keeping multiple options open, and will probably be much more costly.

At least from what I’ve seen, this sort of thing is usually accomplished using the partially-applied types technique used extensively in cats (though this usually depends on the required instances being implicitly available)

implicit final class IterableOnceOps[A](val data: IterableOnce[A]) extends AnyVal {
  def groupMapTo[CC]: GroupMapTo[A, CC] = new GroupMapTo[A, CC](data)
final class GroupMapTo[A, CC](val data: IterableOnce[A]) extends AnyVal {
  def apply[K, B, MC](key: A => K)(f: A => B)
                     (implicit colFactory: Factory[B, CC], mapFactory: Factory[(K, B), MC] = Map): MC

// So it could be used like this:

That would not work for all cases, or really it would lead to boilerplate for users.

The problem is groupMapTo[SortedSet] won’t work because SortedSet takes one parameter, so it actually would have been groupMapTo[SortedSet[Bar]].
Now, you may think oh that is easy, just use CC[_] instead of C well then the problem is that then you couldn’t collect values as BitSet or String or even a nested Map in case that B was actually a tuple.

Yeah, that’s a problem, though thankfully it doesn’t come up much in practice.

Usually, what I would do for the nested Map case (or really any F[_,_], like Either) would be to use a type declaration to fix one of the types.

For the case where I want to merge things into something that doesn’t have a type alias at all, I would generally use Id, and have the combining type be the B. Granted, that mostly works because we use cats pretty extensively, so the definition I’d probably end up using might look something like this:

implicit final class IterableOnceOps[A](val data: IterableOnce[A]) extends AnyVal {
  def groupMapTo[F[_]]: GroupMapTo[A, F] = new GroupMapTo[A, F](data)
final class GroupMapTo[A, F[_]](val data: IterableOnce[A]) extends AnyVal {
  def apply[K, V](key: A => K)(f: A => V)
                     (implicit AF: Applicative[F], SG: Semigroup[F[V]]): Map[K, F[V]]

// So it could be used like this:
list.groupMapTo[SortedSet]( // Map[Foo, SortedSet[Bar]]
list.groupMapTo[Id](     // Map[Foo, Bitset]
list.groupMapTo[Id](     // Map[Foo, String]

type DuplicatesOr[A] = Either[Int, A]
list.groupMapTo[DuplicatesOr]( // Either[Int, Bar]

So this was for the stdlib itself so I couldn’t use things like Semigroup.
Also, your examples do not really show how it should be used, for example for String or BitSet the point would be that the function must returns a Char or an Int respectively; in your example, the user would be to manually transform the Char into a String and the Int into a BitSet manually, so the Semigroup can reduce them together.

And about the F[_, _] the point is not to fix a single parameter but rather that I could collect each group into a Map if the values produced by map where a tuple. So the factory of a Map still consumes a single element, not two.

list.groupMapTo[???]( => bar.baz1 -> bar.baz2) // Map[Foo, Map[Baz1, Baz2]]

What would ??? be? it can not be Map[Baz1, ?] since that would not bring the appropriated factory into scope; and even if it could, it implies boilerplate for the user which is essentially the same problem with C.
Sure, here the “problem” could be the way factory is designed… but that is another different and long discussion.

I really do not want to focus this in this particular example. But rather see if more people would find that behaviour useful.
Notably, I must admit that this is probably the first time I needed it and if not, I found a workaround simple enough so I do not remember about needing this before.