Circumnavigate Java's type system limitations

[danieldietrich]

Java's type system has several limitations, e.g. type constructors are invariant.

We already have javaslang.algebra.HigherKinded, e.g. in order to be able to define the method flatMap() accross types within a inheritance path. But the first definition of flatMap() fixates the result type of the mapper function of flatMap().

Simply spoken, flatMap() has currently the following shape accross types:

// defined in Traversable
Traversable<U> flatMap(Function<? super T, ? extends Traversable<U>> mapper);

// defined in Seq extends Traversable
@Override
Seq<U> flatMap(Function<? super T, ? extends Traversable<U>> mapper);

// defined in List extends Seq
@Override
List<U> flatMap(Function<? super T, ? extends Traversable<U>> mapper);

But what we want is (which unfortunately does not work in Java):

// defined in Traversable
Traversable<U> flatMap(Function<? super T, ? extends Traversable<U>> mapper);

// defined in Seq extends Traversable
@Override
Seq<U> flatMap(Function<? super T, ? extends Seq<U>> mapper);

// defined in List extends Seq
@Override
List<U> flatMap(Function<? super T, ? extends List<U>> mapper);

We can achieve this by adding self-type hints to Traversable and Seq:

interface Traversable<T, M extends Traversable<?, M>> extends Iterable<T>, HigherKinded<T, M> {

    <U> Traversable<U, M> flatMap(Function<? super T, ? extends HigherKinded<U, M>> mapper);
}

interface Seq<T, M extends Seq<?, M>> extends Traversable<T, M>, IntFunction<T>, HigherKinded<T, M> {

    @Override
    <U> Seq<U, M> flatMap(Function<? super T, ? extends HigherKinded<U, M>> mapper);
}

interface List<T> extends Seq<T, List<?>>, Monad<T, List<?>>, HigherKinded<T, List<?>> {

    @Override
    <U> List<U> flatMap(Function<? super T, ? extends HigherKinded<U, List<?>>> mapper);
}

// ---

// f-bounded type
interface HigherKinded<T, TYPE extends HigherKinded<?, TYPE>> {
}

interface Monad<T, M extends HigherKinded<?, M>> extends HigherKinded<T, M> {

    <U> Monad<U, M> flatMap(Function<? super T, ? extends HigherKinded<U, M>> mapper);
}

Note: We could also define flatMap() directly in List, Stream, etc. and remove it from Traversable and Seq. Then HigherKinded could be removed from Javaslang.

[danieldietrich]

Note: I struggled with the idea to remove HigherKinded from Javaslang. But then it would not be possible to have flatMap() accross inherited types like so:

interface Traversable<T, M extends Traversable<?, M>> extends Iterable<T> {

    <U> Traversable<U, M> flatMap(Function<? super T, ? extends M> mapper);
}

interface Seq<T, M extends Seq<?, M>> extends Traversable<T, M>, IntFunction<T> {

    @Override
    <U> Seq<U, M> flatMap(Function<? super T, ? extends M> mapper);
}

interface List<T> extends Seq<T, List<?>> {

    // does not compile, List<U> does not match the type ? extends M
    @Override
    <U> List<U> flatMap(Function<? super T, ? extends List<U>> mapper);
}

1) The first solution would be to remove flatMap() in order to have mapper return the current type:

interface Traversable<T> extends Iterable<T> {
    // no flatMap() here
}

interface Seq<T> extends Traversable<T>, IntFunction<T> {
    // no flatMap() here
}

interface List<T> extends Seq<T> {

    <U> List<U> flatMap(Function<? super T, ? extends List<U>> mapper);
}

This is unsatisfying.

2) The second solution would be to fixate the return type of mapper:

interface Traversable<T> extends Iterable<T> {

    <U> Traversable<U> flatMap(Function<? super T, ? extends Traversable<U>> mapper);
}

interface Seq<T> extends Traversable<T>, IntFunction<T> {

    @Override
    <U> Seq<U> flatMap(Function<? super T, ? extends Traversable<U>> mapper);
}

interface List<T> extends Seq<T> {

    @Override
    <U> List<U> flatMap(Function<? super T, ? extends Traversable<U>> mapper);
}

This solution implies, that List<T> has to extend Monad<T, Traversable<?>> instead of Monad<T, List<?>> which has implications on the monadic properties and is therefore no viable alternative.

@jbgi Again, you are completely right, thanks for the hint/your question, why Traversable implements Monad. I will fix that.

3) The caveats of the solution described in the issue's initial description / proposed solution are:

• More noise: Traversable<T, M> and Seq<T, M> carry an addition generic type parameter on their way
• The mapper result has the type ? extends HigherKinded<U, List<?>> instead of List<U>, which is odd

[danieldietrich]

Maybe I should rename HigherKinded to Type and swap the generic parameters, i.e. Type<List<?>, U> that reads: type List with elements of type U.

The class Type would then move to the first-level package javaslang and it would be official API for these kind of problems in functional programming with Java.

[jbgi]

+1 for switching type parameters. also Functor should be probably extends Type/HigherKind. But what about using a visualy light class name like hk<> or __<> (alla highj)?

[danieldietrich]

Functor should be probably extends Type/HigherKind

What is the use case you have in mind? It does not have a method of the shape of flatMap, i.e. it does not need the additional type information. The less the better...

But what about using a visualy light class name like hk<> or __<> (alla highj)?

Yes, I've thought of that. flatMap() has this name in its type signature. I bet Java programmer Joe/Jane Average will be totally lost, if he/she reads:

interface List<T> /* super interfaces omitted */ {

        @Override
        <U> List<U> flatMap(Function<? super T, ? extends __<List<?>, U>> mapper);
}

The name Type gives a hint about the semantics.

[danieldietrich]

@jbgi oh wait __<List<?>, U> isn't that bad :-) because we see only the relevant part: List of type U.

Indeed, this is very cool!

[danieldietrich]

@jbgi Why do you write two underscores __ instead of one _? Does it reflect the number of generic type arguments?

[jbgi]

just that only one underscore give a javac warning.

[danieldietrich]

ah, ok. I've read about "completing underscore removal from legal identifier names" in Java 9. Does this affect also class names? I don't know...

[danieldietrich]

As of Java 9 / JEP 213 Milling Project Coin: "In addition, using underscore ("_") as an identifier, which generates a warning as of Java SE 8, should be turned into an error in Java SE 9."

Having in mind that two underscores produce no javac warning, I interpret this as two underscores are permitted as identifier with Java 9 onwards.

[danieldietrich]

@jbgi We could be really evil and using unicode character non-breaking space   "\u00A0" as interface name. I like that. This would automatically internalize the higher-kinded type because no one can type it :-)

(This is no joke!)

[danieldietrich]

lame - javac does not allow "\u00A0" as interface name. perhaps there are other unicode chars, I'm searching...

[danieldietrich]

in particular \u200B is interesting ('zero width space')

[danieldietrich]

also does not work - ok, I will read the Java language spec...

[danieldietrich]

Here is a list of all valid Java 8 identifier start characters between unicode 0 and 9999 (dec): http://danieldietrich.net/playground/ValidJava8IdentifierStart.html

[danieldietrich]

After fiddling around with unicode a while I give up. I will take the two underscores approach for HigherKinded and swap Type args as suggested above.

[martin-g]

I am not sure but it looks to me that some Oracle developer uses bad/incomplete regex (e.g. ^_\w+) to detect when _ is used. I guess it is a matter of time to improve it to check for ^_+\w+

[danieldietrich]

Mmhhh... any suggestions?

[martin-g]

I may be wrong!

[danieldietrich]

I think we have to work with the information we have - we do it with two underscores. (It will take years for Oracle to change that standard.)

[martin-g]

But using ascii art for names reminds me of all the complains about Scala operator overloading and its overuse. I'd vote for HK<>.

[danieldietrich]

We want to formulate that List<T> is of type <List<?>, T>.

For now I will stick with List<T> is of type __<List<?>, T> because it is nearest to that without introducing additional information like non-punctuation characters.

I think, higher-kinded __ has to move to the first-level package javaslang. It has nothing to do with javaslang.algebra, instead it is used for API design.

[danieldietrich]

__ is not the right way to do it. I tweetet with Brian Goetz himself and he clarified not to use such identifiers. I'm thankful for the push in the right direction.

HK is no viable alternative, it also says nothing to someone who does not know the context. We need something short and explanatory. HigherKinded is too long. We describe a Type but Type is taken by reflection.

From wikipedia:

"(...) a kind is the type of a type constructor or, less commonly, the type of a higher-order type operator".

So let's take Kind.