How to write a reduce function for a generic ArrayList<T> via streams

user_12804675 0
Viewed 291

I am tasked to implement a custom class to mimic to properties of a Set (without using any data structures of Sets). As such, I chose to store the elements of type T into an ArrayList as a field for the class.

class CustomSet<T> {
    
    private final ArrayList<T> elementList;
    
    CustomSet() { // when initialising an empty set
        this.elementList = new ArrayList<>();
    }

    private CustomSet(ArrayList<T> otherElementList) { // When passing in a list to construct the set
        this.elementList = otherElementList;
    }

    static <T> CustomSet<T> of(T...elem) {
        ArrayList<T> set = new ArrayList<>();
        for (T e: elem) {
            set.add(e);
        }
        return new CustomSet<T>(set);
    }

    // typical add, clear, remove functions for the set which can be done with methods in ArrayList

}

One of my task is to implement a reduce function which takes in a seed and a binary operator to return the reduced value (without the use of explicit loops i.e use streams) such that the following is observed

CustomSet<Integer> thisSet = CustomSet.of(1,2,3,4,5,6);
thisSet.reduce(0, (subtotal, element) -> subtotal + element) // outputs 21

CustomSet<String> otherSet = CustomSet.of("a", "b", "c", "d", "e");
otherSet.reduce("", (partialString, element) -> partialString + element); // outputs "abcde"

I have tried to write my code as such

<U> U reduce(U identity, BiFunction<U, ? super T, U> acc) {
    return elementsList.stream().reduce(identity, acc, (x,y) -> x + y); 
// error which says Operator "+" cannot be applied to 'U', 'U'
}

However it runs to the following error above. How do I solve this?

EDIT

It would be the same as converting the code below to one which uses streams

<U> U reduce(U identity, BiFunction<U, ? super T, U> acc) {
    for (T ele: elementsList) {
        identity = acc.apply(identity, ele);
    }
    return identity;
}
java-stream java
2 Answers

A reduction function must be associative. A BiFunction<U, ? super T, U> acc can not be associative in general. That’s why Java’s Stream API requires a compatible BinaryOperator<U> for its three-arg reduce method. A plus operator is not a compatible third argument and it is impossible to derive a valid third argument from the second, as otherwise, there was no need to insist on that third argument.

We could say, your task is not a real Reduction but a Left-Fold operation that is often confused with Reduction.

There is no direct support for Left Fold operations in the Stream API and while it’s possible to build it without an explicit loop, it’s not a clean operation, but rather a loop in disguise.

<U> U leftFold(U identity, BiFunction<U, ? super T, U> acc) {
    List<U> value = Arrays.asList(identity);
    elementsList.forEach(t -> value.replaceAll(u -> acc.apply(u, t)));
    return value.get(0);
}
user_27114880

I propose this reduce method signature

<U> U reduce(U identity, BiFunction<U, ? super T, U> accumulator, BinaryOperator<U> combiner) {
    return elementList.stream().reduce(identity, accumulator, combiner);
}

And use it like this

CustomSet<Integer> thisSet = CustomSet.of(1, 2, 3, 4, 5, 6);
thisSet.reduce(0, (subtotal, element) -> subtotal + element, Integer::sum); // outputs 21

CustomSet<String> otherSet = CustomSet.of("a", "b", "c", "d", "e");
otherSet.reduce("", (partialString, element) -> partialString + element, (a, b) -> a + b); // outputs "abcde"
user_68154160
Related