How can I re-bound a wildcard?

Question

I'm implementing (single-pivot) Quicksort in Java.

I read there is a term of partitioning and I thought I can write a method with extensibility.

    public static <E> void sort(
            final List<? extends E> list,
            final Comparator<? super E> comparator,
            final BiFunction<List<? extends E>, Comparator<? super E>, Integer> partitioner) {
        if (list.size() < 2) {
            return;
        }
        final int p = partitioner.apply(list, comparator);
        sort(list.subList(0, p), comparator, partitioner);
        sort(list.subList(p + 1, list.size()), comparator, partitioner);
    }

It seemed good to me. The original intention is giving a chance to select any partitioning logic with the BiFunction which takes the unsorted list and the comparator and returns the partitioning index.

And I tried to add another method for Lomuto partition scheme.

   static <E> void lomuto(final List<? extends E> list,
                          final Comparator<? super E> comparator) {
        sort(list,
             comparator,
             (l, c) -> {
                 final E pivot = l.get(l.size() - 1);
                 int i = 0;
                 for (int j = 0; j < l.size() - 1; j++) {
                     if (c.compare(l.get(j), pivot) <= 0) {
                         swap(l, j, i++);
                     }
                 }
                 swap(l, l.size() - 1, i);
                 return i;
             });
    }

And the compiler complains at c.compare(l.get(j), pivot) part.

    Required type                                Provided
o1: capture of ? super capture of ? extends E    E
o2: capture of ? super capture of ? extends E    E

I found I can work around with

static <E> void lomuto(final List<E> list, final Comparator<? super E> comparator) {

How can I still do the PECS with lomuto method? ? extends E?

Since you never use `E` directly, why would you want the `E` to be the most specific subtype? `List list, Comparator super E> comparator` is the correct way to do it, for both methods. — Andreas, Jan 15 '20 at 01:38
as weird as it may seem those `? extends E` are different types. [related](https://stackoverflow.com/questions/27902219/nested-wildcards/58631449#58631449) — Eugene, Jan 15 '20 at 01:38
@Andreas Oh you're absolutely right. Can you please make it as an answer so that I can accept it? Even with PECS the list should be bounded with `` cuz it's a producer and also a consumer. — Jin Kwon, Jan 15 '20 at 02:10
Don't see how answer could be useful to anyone, as they'd be unlikely to be able to even find the question/answer, so I'd suggest just deleting the question. If you disagree, self-answer the question and accept your own answer. You might even get the [Self-Learner](https://stackoverflow.com/help/badges/14/self-learner) badge for that, if you're right. — Andreas, Jan 15 '20 at 02:15

score 4 · Accepted Answer · answered Jan 15 '20 at 09:55

The problem is that the <E> of the lomuto method is not the <E> of the sort method. You wish the compiler to infer lomuto’s E as the type argument for sort’s type parameter, as the two methods have two congruent parameters, but that’s not how type inference works. All the compiler sees, are the three arguments for the sort method, a List<? extends E>, a Comparator<? super E>, and a poly expression. It will introduce special inference types which will then propagate to the poly expression.

When you use an explicit type argument to match the two E’s, the code compiles:

public static <E> void sort(
        final List<? extends E> list,
        final Comparator<? super E> comparator,
        final BiFunction<List<? extends E>, Comparator<? super E>, Integer> partitioner) {
    if (list.size() < 2) {
        return;
    }
    final int p = partitioner.apply(list, comparator);
    sort(list.subList(0, p), comparator, partitioner);
    sort(list.subList(p + 1, list.size()), comparator, partitioner);
}

static <E> void lomuto(final List<? extends E> list,
                      final Comparator<? super E> comparator) {
    ContainingClass.<E>sort(list,
         comparator,
         (l,c) -> {
             final E pivot = l.get(l.size() - 1);
             int i = 0;
             for (int j = 0; j < l.size() - 1; j++) {
                 if (c.compare(l.get(j), pivot) <= 0) {
                     swap(l, j, i++);
                 }
             }
             swap(l, l.size() - 1, i);
             return i;
         });
}

Alternatively, you can provide explicit argument types for the lambda expression, so it isn’t a poly expression anymore:

// keep the sort method unchanged

static <E> void lomuto(final List<? extends E> list,
                      final Comparator<? super E> comparator) {
    sort(list,
         comparator,
         (List<? extends E> l, Comparator<? super E> c) -> {
             final E pivot = l.get(l.size() - 1);
             int i = 0;
             for (int j = 0; j < l.size() - 1; j++) {
                 if (c.compare(l.get(j), pivot) <= 0) {
                     swap(l, j, i++);
                 }
             }
             swap(l, l.size() - 1, i);
             return i;
         });
}

what a beauty! I never thought that you could match those `E`s — Eugene, Jan 15 '20 at 12:17

score 0 · Answer 2 · answered Jan 15 '20 at 02:32

I'm answering for my own.

As Andreas commented, the ? extends E of the List is not necessary and even wrong.

The list argument has both role of consumer and producer.

And the method should look look this.

    public static <E> void sort(
            final List<E> list,
            final Comparator<? super E> comparator,
            final BiFunction<? super List<E>, ? super Comparator<? super E>, Integer> partitioner) {
        if (list.size() < 2) {
            return;
        }
        final int p = partitioner.apply(list, comparator);
        assert p >= 0;
        assert p < list.size();
        sort(list.subList(0, p), comparator, partitioner);
        sort(list.subList(p + 1, list.size()), comparator, partitioner);
    }

And the method for a specific partition scheme should look like this.

    public static <E> void lomuto(final List<E> list,
                                  final Comparator<? super E> comparator) {
        sort(list,
             comparator,
             (l, c) -> {
                 assert !l.isEmpty();
                 final int p = l.size() - 1;
                 int i = 0; // the index to be swapped with the pivot
                 for (int j = 0; j < l.size() - 1; j++) {
                     if (c.compare(l.get(j), l.get(p)) <= 0) {
                         swap(l, j, i++);
                     }
                 }
                 swap(l, p, i);
                 return i;
             });
    }

Using `List extends E>` might be unnecessary, but not wrong. Reordering is an operation that doesn’t count as “produce and consume”. Note how the `swap` calls do not produce any errors. — Holger, Jan 15 '20 at 10:00

How can I re-bound a wildcard?

2 Answers2