Rethink flatMap et al.

[danieldietrich]

The following is taken from a pull request comment:

With flatMap we have a TODO in general but not here, with this pull-request.

Example:

scala> "123".flatMap(Some(_))
res0: String = 123

scala> "123".flatMap(c => Some(c + 0))
res1: scala.collection.immutable.IndexedSeq[Int] = Vector(49, 50, 51)

scala> val words = Set("Patryk", "Ruslan", "Daniel")
words: scala.collection.immutable.Set[String] = Set(Patryk, Ruslan, Daniel)

scala> words flatMap (word => word.toSet)
res2: scala.collection.immutable.Set[Char] = Set(e, s, n, y, t, u, a, i, l, P, r, R, k, D)

scala> words flatten (word => word.toSet)
res3: scala.collection.immutable.Set[Char] = Set(e, s, n, y, t, u, a, i, l, P, r, R, k, D)

Our flatMap works totally different. We need to check what is possible with Java, what makes sense and what is the expected behavior of flatMap. Maybe we need a Monad.unit(val) and Monoid.combine(m1, m2)...

[patrox]

I can pick this up - and will come back tomorrow with some ideas, ok ?

[ruslansennov]

I'll take a break :)

[danieldietrich]

@patrox ok, this will be fun!

[danieldietrich]

@patrox if any questions (e.g. regarding existing code) - I'm here!

[danieldietrich]

@ruslansennov

I'll take a break :)

you've more than deserved it :)

[patrox]

@ruslansennov you deserved some 🍻 :)

[ruslansennov]

@patrox it's really a good idea

[patrox]

@danieldietrich, @ruslansennov, regarding flatMap and/or map, here are my findings:

I found that when we run any transformation function (like map, filter, etc) on a plain String in Scala, we will go through the following sequence:
1.) First the String is converted (implicitly) to StringOps instance (http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.StringOps)
2.) Then the requested function (method) is called
3.) Lastly the result is converted back to String

But, in case of WrappedString (http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.WrappedString) the sequence which we will go through is much shorter, as:
1.) there is no (implicit) conversion from plain String, so we need to create WrappedString explicitly
2.) the function (method) is applied directly on WrappedString instance
3.) there is also no conversion back to String

So javaslang.collection.WrappedString is much closer to WrappedString, then StringOps (not only because of the name ...

When applying map over javaslang.collection.WrappedString, I think that the result can be also a WrappedString if (and only if) the map function has the following signature: Function<Char, Char>,
because the above ensures that the result will be also a proper WrappedString, as it makes no sense to
construct it from a result of applying map with the following signature Function<Char, Integer> - in such case I believe that more generic collection should be used instead, like for example Vector.

So to summarize:

WrappedString.map(Function<Char,Char>) should result in a WrappedString but,
WrappedString.map(Function<Char,Integer>) should result in a Vector<Integer>
(or to be more generic: WrappedString.map(Function<Char,T>)
should result in a Vector<T>)

Does it make any sense ?

[patrox]

I focused for now on map since flatMap is the same, but flattens the result by 'removing' the most inner layer of abstraction Option, List, etc.

[danieldietrich]

Hi @patrox, thanks for investigating it!!

I think we cannot decide whether our map/flatMap returns a CharSeq (aka WrappedString) or Vector, depending on the result type of the mapping function.

Adding an additional map function which has return type CharSeq would raise ambiguities:

// this call is ambiguous
CharSeq.empty().map(c -> 'c');

// this is additional
public CharSeq map(CharUnaryOperator mapper) {
    Objects.requireNonNull(mapper, "mapper is null");
    if (isEmpty()) {
        return this;
    } else {
        final char[] chars = back.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            chars[i] = mapper.apply(chars[i]);
        }
        return CharSeq.ofAll(chars);
    }
}

// this comes from FilterMonadic
@Override
public <U> Vector<U> map(Function<? super Character, ? extends U> mapper) {
    Objects.requireNonNull(mapper, "mapper is null");
    Vector<U> result = Vector.empty();
    for (int i = 0; i < length(); i++) {
        result = result.append(mapper.apply(get(i)));
    }
    return result;
}

// the compiler can't distinguish between this and Function<Character, Character>
@FunctionalInterface
interface CharUnaryOperator {
    char apply(char c);
}

// factory method
static CharSeq ofAll(char[] array) {
    Objects.requireNonNull(array, "array is null");
    return new CharSeq(String.valueOf(array));
}

If we want our traversables to have common map methods, we need to keep the one that returns Vector<U>.

Additionally it makes sense to map chars to chars. To circumvent the ambiguities, we could rename the char mapper to mapChars(CharUnaryOperator).

Analog, flatMap could be

public CharSeq flatMapChars(CharFunction<? extends CharSequence> mapper) {
    Objects.requireNonNull(mapper, "mapper is null");
    if (isEmpty()) {
        return this;
    } else {
        final StringBuilder builder = new StringBuilder();
        back.chars().forEach(i -> builder.append(mapper.apply((char) i)));
        return new CharSeq(builder.toString());
    }
}

@FunctionalInterface
interface CharFunction<R> {
    R apply(char c);
}

/cc @ruslansennov

[patrox]

yes, I believe that I use too strong words, because when I was writing 'should return' I meant: 'it would be good if ...', but unfortunately it seems that java is missing a lot of scala's 'magic' :)

[danieldietrich]

Yes, it seems the Scala compiler can derive statically the return type...

[patrox]

I'll play with the methods which you proposed and let you know what my experience was ... Maybe something new will pop up.

[danieldietrich]

Alright! 👍

[danieldietrich]

@patrox do you think I can commit these methods or will it produce merge conflicts at your site?

[danieldietrich]

I will do it to get the Array in here...

[patrox]

@danieldietrich, you can merge them without any concerns.

[danieldietrich]

Summarized

We want uniform map and flatMap across our collections

We achieve this by introducing

interface FilterMonadic<M extends Kind<M, ?>, T> extends Kind<M, T> {

    <U> FilterMonadic<M, U> flatMapM(Function<? super T, ? extends Kind<? extends M, ? extends U>> 
mapper);

    <U> FilterMonadic<M, U> map(Function<? super T, ? extends U> mapper);

}

Note: This is what we are able to define as common flatMap in Java. We named it flatMapM because the Kind return type is a little bit nasty. Kind is just a type-constructor hack for missing higher-order types in Java. Additionally we define the real flatMap (without the 'M') for collections but we are not able to do it uniformly for all types.

Example: List.flatMap

// Kind<Iterable, U> is (more or less) the same as Iterable<U>
<U> List<U> flatMap(Function<? super T, ? extends Iterable<? extends U>> mapper);

The semantics of our collection flatMap methods is

1. map all collection elements to iterables
2. combine the iterables to a collection, e.g. List

We observe that map, flatMapM and flatMap are not sufficient for all collection types

Examples (simplified):

interface Map<K, V> extends Traversable<Entry<K, V>> {

    // this is what we get from FilterMonadic
    <U> Set<U> map(Function<? super Entry<K, V>, ? extends U> mapper);

    // this is what we really want to have
    <U, W> Map<U, W> map(BiFunction<? super K, ? super V, ? extends Entry<? extends U, ? extends W>> mapper);

}

final class CharSeq implements IndexedSeq<Character> {

    // this is what we get from FilterMonadic
    <U> Vector<U> map(Function<? super Character, ? extends U> mapper);

    // this is what we really want to have
    CharSeq mapChars(CharUnaryOperator mapper);

    @FunctionalInterface
    interface CharUnaryOperator {
        char apply(char c);
    }
}

Wishlist:

1. We want unique map and flatMap methods (instead one with Kind, one simplified and one useful)
2. We want a common interface with map and flatMap methods for all collections

Our observation showed that it is not possible to fulfill both wishes at once. This issue was created to prevent the creation of a Zoo of map and flatMap methods. A simple API is one of the main targets of Javaslang.

Solution

Currently there is no solution. In order to create one it is essential to understand which are the use cases of FilterMonadic and when a common map/flatMap interface is needed in general.

If it turns out that FilterMonadic is not needed then we also do not need Kind any more.

A suggestion is to delete FilterMonadic and Kind. Additional methods may be added to Value (or MonadOps):

interface Value<T> {

    @Override
    <U> Value<U> mapM(Function<? super T, ? extends U> mapper);

    @Override
    <U> Value<U> flatMapM(Function<? super T, ? extends Value<? extends U>> mapper);
}

Please note that there are single element and multi element Values such as Option, Lazy and Try (single element) and List, HashMap, Tree (multi element).

It is essential that MonadOps, IterableOps and ConversionOps are not public API - their only purpose is to organize the big amount of methods of interface Value.

Also we may delete TraversableOnce.map and flatMap and define them appropriately in Seq, Set and Map.

With other words Value.mapM and flatMapM are the common methods for many types (not only collections). Additionally map and flatMap are defined where possible and where it makes sense regarding the inheritance hierarchy.

[danieldietrich]

To make it more concrete, here is an example:

interface List<T> extends LinearSeq<T>, Value<T> {

    // mapM, map ...

    @Override // defined in Value or MonadOps
    <U> List<U> flatMapM(Function<? super T, ? extends Value<? extends U>> mapper);

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

}

interface Map<K, V> extends Traversable<Entry<K, V>>, Value<Entry<K, V>> {

    // flatMapM, flatMap ...

    @Override // defined in Value or MonadOps
    <U> Set<U> mapM(Function<? super Entry<K, V>, ? extends U> mapper);

    @Override // defined in Map
    <U, W> Map<U, W> map(BiFunction<? super K, ? super V, ? extends Entry<? extends U, ? extends W>> mapper);

}

And then:

// = List(2, 4)
List.of(1, 2, 3, 4).flatMapM(i -> i % 2 == 0 ? new Some<>(i) : None.instance);

// = List(1, 1, 2, 2, 3, 3, 4, 4)
List.of(1, 2, 3, 4).flatMap(i -> Vector.of(i, i));

[danieldietrich]

While applying changes I'm also applying additional minor changes. E.g. renaming Map.merged(...) to Map.merge(...). I know that Scala uses merged. We follow these:

• if the method has no args, it may be named xxxed(), e.g. curried(), memoized(). Counter example: flatten()
• otherwise we omit ed at the end.