search

vavr-io / vavr

vʌvr (formerly called Javaslang) is a non-commercial, non-profit object-functional library that runs with Java 8+. It aims to reduce the lines of code and increase code quality.
https://vavr.io
Other
5.68k stars 630 forks source link

Upper-bounded Traversable.contains behaves unexpected #1065

Closed danieldietrich closed 8 years ago

danieldietrich commented 8 years ago

We need to change the contains(T) and *indexOf(T) methods to contains(Object) and *indexOf(Object).

Here are some example of code that currently does not work:

List<Double> slangDoubles = List.of(42d, 99d);
List<? extends Number> slangNumbers = slangDoubles;
slangNumbers.contains(42d); // DOES NOT COMPILE

java.util.List<Double> javaDoubles = Arrays.asList(42d, 99d);
java.util.List<? extends Number> javaNumbers = javaDoubles;
javaNumbers.contains(42d); // Compiles fine...

However, javaNumbers.add(42d) does also not work. But it is quite eligible and also intuitive to say

// = false
listOfAnimals.contains(stone);

Another example:

 class SimpleComposition {

            private final List<? extends Number> numbers;

            private SimpleComposition(List<? extends Number> numbers) {
                this.numbers = numbers;
            }

            boolean contains(Number number) {
                return this.numbers.contains(number); // DOES NOT COMPILE
            }
}

List<Double> slangDoubles = List.of(2d, 9d);
new SimpleComposition(slangDoubles).contains(2d);

Using <U extends T> boolean contains(U that) does also not work.

As @RobWin says

Producer extends and Consumer super "PECS" is from the collection's point of view. If you are only pulling items from a generic collection, it is a producer and you should use extends; if you are only stuffing items in, it is a consumer and you should use super. (from stackoverflow)

@netzwerg great finding!!

RobWin commented 8 years ago

PECS does not help here :( Only an Object argument helps in contains and indexOf.

danieldietrich commented 8 years ago

Moving back contains from Value to Traversable...

danieldietrich commented 8 years ago

Maybe this could affect even more methods, e.g. let's take a look at java.util.Map:

    boolean containsKey(Object key);
    boolean containsValue(Object value);
    V get(Object key);
    V put(K key, V value);
    V remove(Object key);
    ...
danieldietrich commented 8 years ago

@ruslansennov @netzwerg @RobWin I think this goes in the wrong direction. We loose type safety, which is no good idea. In Rahels example we just need to cast the List<Double> to a List<Number> and all is fine. But Java says we can only get a List<? extends Number>, which is useless. Even if contains is fixed, we still have no working prepend etc.

I've sketched a type safe solution, which introduces a type-safe cast:

import javaslang.collection.List;

import java.math.BigDecimal;

public class Test {

    public static void main(String[] args) {

        //
        // Initial situation:
        //   We have a type 'Double' which is in between other types
        //   within a specific type hierarchy.
        //

        List<Double> doubles = List.of(1d);

        //
        // Our intuition says that a List<Double> is a List<Number>
        //

        // error: "Incompatible types"
        List<Number> numbers1 = doubles;

        // error: "Inconvertible types"
        List<Number> numbers2 = (List<Number>) doubles;

        // Works, but captured generics are useless
        // as we will see in the following examples
        List<? extends Number> numbers3 = doubles;

        // prepend (capture<? extends Number>) in List cannot be applied to (BigDecimal)
        numbers3.prepend(new BigDecimal("0"));

        // prepend (capture<? extends Number>) in List cannot be applied to (Number)
        numbers3.prepend((Number) new BigDecimal("0"));

        //
        // In a mutable world it would be possible to
        //
        //    List<Double> doubles = List.of(1d);
        //    List<Number> numbers = cast(doubles);
        //    numbers.add(new BigDecimal("0"));
        //    // now doubles contains a BigDecimal, what is wrong
        //
        // In an immutable world it is pretty eligible to assume
        // that a List<Double> is a List<Number>. Looking at the
        // example above, we now have:
        //
        //    List<Double> doubles = List.of(1d);
        //    List<Number> numbers = cast(doubles);
        //    List<Number> newNumbers = numbers.add(new BigDecimal("0"));
        //    // doubles remains the same
        //

        List<Number> numbers4 = (List<Number>) (Object) doubles;
        numbers4.contains(42d);
        numbers4.contains(new BigDecimal("1"));
        numbers4.prepend(42d);

        final List<Number> newNumbers4 = numbers4.prepend(new BigDecimal("1"));

        //
        // We abstract over (List<Number>) (Object) doubles and provide
        // a _safe_ API to perform correct casts:
        //

        List<Number> test = List.empty();

        // does not compile: "inference variable U has incompatible bounds"
        List<Double> wrong = cast(test);

        // does compile!
        List<Number> right = cast(doubles);

    }

    @SuppressWarnings("unchecked")
    static <T extends U, U> List<U> cast(List<T> list) {
        return (List<U>) list;
    }
}

What do you think?

danieldietrich commented 8 years ago

It will be part of each collection type. E.g.

interface List<T> {
    @SuppressWarnings("unchecked")
    static <T extends U, T> List<U> cast(List<T> list) {
        return (List<U>) list;
    }
}

Note: it would be nice to have an instance method but we can't express a lower-bound generic like this:

interface List<T> {
    // <U super T> does not compile
    @SuppressWarnings("unchecked")
    default <U super T> List<U> cast() {
        return (List<U>) this;
    }
}

Is there a better name for cast?

But wait...

Maybe we already have that method, it is ofAll and we just need to fix the generics, e.g.

interface List<T> {
    @SuppressWarnings("unchecked")
    static <T extends U, T> List<U> ofAll(Iterable<? extends T> elements) {
        Objects.requireNonNull(elements, "elements is null");
        if (elements instanceof List) {
            return (List<U>) elements;
        } else if (elements instanceof java.util.List) {
            List<U> result = Nil.instance();
            final java.util.List<T> list = (java.util.List<U>) elements;
            final ListIterator<T> iterator = list.listIterator(list.size());
            while (iterator.hasPrevious()) {
                result = result.prepend(iterator.previous());
            }
            return result;
        } else if (elements instanceof NavigableSet) {
            List<U> result = Nil.instance();
            final java.util.Iterator<T> iterator = ((NavigableSet<T>) elements).descendingIterator();
            while (iterator.hasNext()) {
                result = result.prepend(iterator.next());
            }
            return result;
        } else {
            List<U> result = Nil.instance();
            for (T element : elements) {
                result = result.prepend(element);
            }
            return result.reverse();
        }
    }
}
danieldietrich commented 8 years ago

A few months ago I started a discussion about this topic on twitter: https://twitter.com/danieldietrich/status/669534660561629185

The replies are interesting, in particular those of Peter Lawrey (this), Jean-Baptiste Giraudeau (this) and Brian Goetz (this).

Interestingly the binarySearch was also mentioned there :-)

mvh77 commented 8 years ago

No need to fix anything, RC3 works fine?

List<Double> slangDoubles = List.of(42d, 99d);
List<Number> slangNumbers = List.ofAll(slangDoubles);
slangNumbers.contains(42d);
danieldietrich commented 8 years ago

Oohh, you're right - awesome :smile: I love this library - everything just works™

netzwerg commented 8 years ago

I am not completely convinced yet, so just to be sure:

You're suggesting to call List.ofAll in order to get rid of the upper bound for slangNumbers, right? I am aware that this is safe & fast, but the readability suffers if you're doing this in real-world code.

Looking at it from a different angle: I am in the process of convincing my dev team that Javaslang is awesome. One of many arguments is that we no longer need defensive copying upon construction, and here I come suggesting this "fix":

class SimpleComposition {

    private final List<Number> numbers;

    private SimpleComposition(List<? extends Number> numbers) {
        this.numbers = List.ofAll(numbers); // Smell 
    }

    boolean contains(Number number) {
        return numbers.contains(number);
    }
}

This doesn't feel 100% right...

It certainly is a good workaround until we have a proper contains though:

boolean contains(Number number) {
  return List.ofAll(this.numbers).contains(number);
}
RobWin commented 8 years ago

In think the idea is not to copy the list, but cast. See ofAll

if (elements instanceof List) {
            return (List<U>) elements;

Or am I wrong?

danieldietrich commented 8 years ago

@netzwerg @RobWin I see, List.ofAll(...) is not a good name for our use-case.

What we really need in order to use the type-safe variants contains(T), prepend(T), ... is a unsound type system like that of Dart: Why Dart Types Are Optional and Unsound (scroll down to Why are generics covariant?).

The essence of that document is: a ReadOnlyReference is a ReadOnlyReference.

Java does not have a unsound type system. The best we can do is: ReadOnlyReference is a ReadOnlyReference<? extends Number>.

So we have to choices:

  1. Use an unsafe Object instead of a safe T everywhere we need to circumvent Java's type system. That requires us to clutter our code with unsafe type casts. Ruslan did already the change in this PR. There are many places which may throw a ClassCastException. Trust me - we don't want to have such unsafe code in production, if there is safe solution.
  2. The safe solution makes use of the fact that ReadOnlyReference is a ReadOnlyReference. We can just cast it. But we need a human-readable API for that. Any suggestions? ofAll(...) seems to be confusing. Is cast(...) or safeCast(...) better? The Method needs to be static because the generic bound is super, which cannot be expressed in an instance method. And because we do not have higher-kinded types/type constructors, we need to implement that methods for each type.

Note: It is not sufficient to use contains(Object) and indexOf(Object). There are plenty of more methods which need to take Object instead of T because a (capture of ? extends T) does not allow us to insert subtypes of T. Example: java.util.List.add(1.0d) is not possible on a List<? extends Number>

netzwerg commented 8 years ago

Tx for your excellent explanation, @danieldietrich!

IMHO, cast(...) sounds scary while safeCast(...) sounds suspicious :-) But in our case, the cast is not risky at all, so we don't want the method to sound scary.

What about something along the lines of narrow(...)?

danieldietrich commented 8 years ago

The Problem

We have List<Double> doubles = ....

We want a List<Number> numbers = doubles.

But the best Java offers us is List<? extends Number> numbers = doubles.

Facts

About the types:

It is not possbile to

interface List<T> {

    // not possible
    <U super T> List<U> cast() {
        return (List<U>) this;
    }

    // also not possible
    <U> List<U super T> cast() {
        return (List<U>) this;
    }
}
interface Predef {

    // not possible:
    static <M<T>> M<T> cast(M<? extends T> type) { ... }

    // workaround, but return type not helpful here
    static <M extends Kind<M, ?>, T> Kind<M, T> cast(Kind<M, ? extends T> type) { ... }
}

Solution

This leads to a static cast method per type.

Example: List

interface List<T> {
    static <T> List<T> cast(List<? extends T> list) { ... }
}

Note: List.ofAll(...) does exactly what cast does (+ additional things with other inputs). But ofAll is not convenient/comprehensible. The API should exactly describe what happens.

danieldietrich commented 8 years ago

@netzwerg please read my previous comment, it clarifies the higher-kinded stuff etc.

Yes, cast is a negative pattern / anti-idiom.

We use narrow in the context of Monads/higher-kinded types. A second use case of the same keyword would be confusing.

Are there other names? Maybe

It is all about types, why not

danieldietrich commented 8 years ago

Re-opening this issue to find a better name...

netzwerg commented 8 years ago

We use narrow in the context of Monads/higher-kinded types. A second use case of the same keyword would be confusing.

Good point...

Inspired by your links, confine or restrict could work?

Anything with bound can be confusing because it blurs the intention i.e. it is no longer clear that we're going from ? extends T (wide) to T (narrow).

danieldietrich commented 8 years ago

I like restrict :+1:

danieldietrich commented 8 years ago

I also like infer. restrict sounds like loosing something. But we gain type-safe collection operations that are otherwise not possible in Java. Java can't infer the right type, but we know better because List is immutable.

List<Number> numbers = List.infer(doubles);

Note: We also see sorted instead of sort or curried instead of curry. Maybe inferred is better than infer? In the sense of give me an inferred version instead of infer that list. On the other hand there is sum and zip instead of summed and zipped. Never understood the difference. I think most of the ...ed methods take no arguments. The static infer/inferred method does also take no arguments other than the instance itself, i.e. it is an extension method. That would indicate inferred.

Oh my gosh - naming things is so hard... :)

netzwerg commented 8 years ago

I like infer if it's on the RHS of an assignment, like in your example:

List<Number> numbers = List.infer(doubles);

I prefer restrict in a method chain:

return List.restrict(doubles).contains(...);

But probably I am focusing too much on my use case...

What about List.typeSafe(...)? Has a positive connotation and works for both.

RobWin commented 8 years ago

What about List.typeSafeUpCast() ?

danieldietrich commented 8 years ago

What did you say?

List.whatAboutTypeSafeUpCast() ? ;)

I like typeSafe, too. Maybe it has to be List.typeSafe™() :-)

RobWin commented 8 years ago

List.surprise or Traumschiff.surprise()

RobWin commented 8 years ago

Just upCast?

danieldietrich commented 8 years ago

upCast is like cast, which is a smell because it is unsafe in general.

Mmhh, narrow fits very good. I think it does not collide with Monad.narrow(). javaslang has no dependency to javaslang-algebra.

Check?

danieldietrich commented 8 years ago

Collections got narrow(). Do other types also need narrow()? E.g. Option, Try, Either, Future, Validation, Lazy, ... ???

danieldietrich commented 8 years ago

Need to add tests for these:

danieldietrich commented 8 years ago

Done with #1077 and #1081. Moved pending tests to #477