5
\$\begingroup\$

There is a problem on Exercism Java track that requires writing a function to flatten an arbitrarily nested list to a flattened list without null values. For Example
input: [1,[2,3,null,4],[null],5]
output: [1,2,3,4,5]

Here is the solution I wrote for it without using wildcards.

public List flatten(List<Object> two) {
    Function<Object, List> mapper = item -> (item instanceof List) ? flatten((List) item) : Collections.singletonList(item);
    return (List) two.stream()
            .filter(x -> x != null)
            .map(mapper)
            .flatMap(x -> x.stream())
            .collect(Collectors.toList());
}

Here is my solution with the wildcard generics. My IDE was happier with this solution.

public List<Object> flatten(List<?> two) {
    Function<Object, List<?>> mapper = item -> (item instanceof List) ? flatten((List<?>) item) : Collections.singletonList(item);
    return two.stream()
            .filter(Objects::nonNull)
            .map(mapper)
            .flatMap(List::stream)
            .collect(Collectors.toList());
}

Is it ok to use the wildcard in this case? Which solution would you prefer? Any other comments about the code are also welcome.

\$\endgroup\$
1
  • 4
    \$\begingroup\$ While Torben and Marc did some good effort in answering your question, I'd rather like to challenge the exercise itself: as often, this is somthing without any practical relevance that someone found mildly interesting. In reality, we've had generics for 16 years now, and you do not mix collections today. If you really have old legacy code that still does, refactor this code. Do not try to find "elegant" solutions for this kind of impractical crap. \$\endgroup\$
    – mtj
    Nov 6 '20 at 11:54
3
\$\begingroup\$

The question

Your IDE complains about the first one because you're mixing raw types and parameterized types. By changing the raw types to List<Object> your IDE will be a bit happier. However, the second example, with the unknown type, is the correct one to use. It lets you call the method with any list type, such as List<List<String>>, not just List<Object>. Also you use the method reference operator :: instead of lambdas (the operator was added for this exact purpose so it should be used here).

Plain old review

  • Method name should tell the caller it does recursive flattening.
  • Did the exercise specify only lists to be flattened instead of all collections? If former, call it flattenListsRecursively.
  • Parameter name two is confusing.
  • Variable name mapper is a bit generic. Use mapToList or similar instead.
  • There is no limit in the recursion.

The last one may be a bit controversial, but my opinion is that if you intend to do a recursive algorithm for generic use you should provide the caller with tools to prevent it from running out of control instead of just relying on an eventual StackOverflowError.

Performance

The stream API requires you to do an awful lot of throwaway singleton list creation. A good old loop with recursion would be much more effective in this case. It may even be a bit more readable as the recursive call is not buried down into a fairly long one line lambda. Remember, streams are like a hammer. It's a handy tool sometimes but hardly the right tool every time.

public static List<Object> flattenListsRecursively(List<?> input) {
    final List<Object> result = new ArrayList<>();
    flattenListRecursively(input, result);
    return result;
}

private static void flattenListsRecursively(List<?> input, List<Object> result) {
    for (Object o: input) {
        if (o instanceof List) {
            flattenListRecursively((List<?>) o, result);
        } else if (o != null) {
            result.add(o);
        }
    }
}

If you made the latter public, you could let the caller use the result list as a way to control the execution by, for example, passing a size limited list. But this doesn't solve the stack overflow problem I mentioned earlier as a list of lists that contains itself just goes into a runaway recursion without necessarily affecting the output size.

\$\endgroup\$
1
  • \$\begingroup\$ I am choosing this answer as I found this most helpful towards the problem I asked. Thanks for other comments and answers too everyone. \$\endgroup\$ Nov 8 '20 at 13:05
5
\$\begingroup\$

@TorbenPutkonen already provided a great review, I just wanted to add something about usability.

Depending on your use case, returning a List<Object> means that you need to do the casting later. For example:

List<Object> result = flatten(myList);
for(Object o : result) {
    if(o instanceof String) {
        String myString = (String) o;
        // do something with the string
    }
    // etc...
}

If you know the type of the elements you can pass it to the method:

@SuppressWarnings("unchecked")
public <T> List<T> flatten(List<?> list, Class<T> itemType) {
    return list.stream()
            .filter(Objects::nonNull)
            .flatMap(i -> i instanceof List ? flatten((List<?>)i, itemType).stream() : Stream.of((T)i))
            .collect(Collectors.toList());
}

And then use it like:

List<String> result = flatten(myList, String.class);
for(String s : result) {
    // do something with the string
}

This is the version without streams:

@SuppressWarnings("unchecked")
public static <T> List<T> flatten(List<?> list, Class<T> itemType) {
    List<T> result = new ArrayList<>();
    for(Object o : list) {
        if(o instanceof List) {
            result.addAll(flatten((List<?>) o, itemType));
        }
        else if (o != null){
            result.add((T) o);
        }
    }
    return result;
}
\$\endgroup\$
3
  • \$\begingroup\$ You should have insist in your usage of Stream.of(i) in your answer before the code. The first answer mentionned the creation of lot intermediary list and propose immediately to switch to the old for insteand of this, which is using the Stream API more properly instead of throwing it altogether as if it wasn't good enough \$\endgroup\$
    – Walfrat
    Nov 6 '20 at 13:36
  • \$\begingroup\$ @Walfrat It's a better use but arguably the best time to use Stream here, that's why I haven't insisted. Honestly, I would be happier to read and debug the version without Stream. \$\endgroup\$
    – Marc
    Nov 6 '20 at 15:06
  • \$\begingroup\$ I know that's why i said "good enough" and not the "best". \$\endgroup\$
    – Walfrat
    Nov 6 '20 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.