Re-implement Collections.scanLeft/scanRight:

[danieldietrich]

class Collections {
    static <T, U, R extends Traversable<U>> R scanLeft(Traversable<? extends T> traversable,
            U zero, BiFunction<? super U, ? super T, ? extends U> operation, Function<Iterator<U>, R> finisher) {

        final Iterator<U> iterator = traversable.iterator().scanLeft(zero, operation);
        return finisher.apply(iterator);
    }
}

Call site example:

Collections.scanLeft(this, zero, operation, Iterator::toVector)

---

Please do the same for Collections.scanRight using traversable.reverseIterator(). This will leverage efficient implementations for IndexedSeqs.

[ashrwin]

@danieldietrich Traversable does not have a reverseIterator() method ?
Did you mean the reverseIterator() in Collections ?

[danieldietrich]

@ashrko619 I meant Traversable.reverseIterator(). Currently Collections.scanRight() is implemented like this:

static <T, U, C extends Iterable<U>, R extends Traversable<U>> R scanRight(
        Iterable<? extends T> elements,
        U zero, BiFunction<? super T, ? super U, ? extends U> operation,
        C cumulativeResult, BiFunction<C, U, C> combiner,
        Function<C, R> finisher
) {
    final Iterator<? extends T> reversedElements = reverseIterator(elements);
    return scanLeft(reversedElements, zero, (u, t) -> operation.apply(t, u), cumulativeResult, combiner, finisher);
}

If we had the possibility to iterate the elements in reverse order (which is efficiently possible for IndexedSeq for example), the implementation could look like this:

static <T, U, C extends Iterable<U>, R extends Traversable<U>> R scanRight(
        Iterable<? extends T> elements,
        U zero, BiFunction<? super T, ? super U, ? extends U> operation,
        C cumulativeResult, BiFunction<C, U, C> combiner,
        Function<C, R> finisher
) {
    final Iterator<U> iterator = traversable.reverseIterator().scanLeft(zero, (u, t) -> operation.apply(t, u));
    return finisher.apply(iterator);
}

(note: code not tested)

[ashrwin]

Can we change the signature of scanRight similar to scanLeft as you had said above?
Right now, I have the following implementation :

static <T, U, R extends Traversable<U>> R scanRight(Traversable<? extends T> traversable,
                                                        U zero, BiFunction<? super T, ? super U, ? extends U> operation, Function<Iterator<U>, R> finisher) {

  final Iterator<? extends T> reversedElements = reverseIterator(traversable.iterator());
  return scanLeft(reversedElements, zero, (u, t) -> operation.apply(t, u), finisher);
}

reverseIterator() already checks if reverse iteration is possible.

[danieldietrich]

I think you looked at the wrong file. Here is my content of javaslang.collection.Collections:

    static <T, U, C extends Iterable<U>, R extends Traversable<U>> R scanLeft(Iterable<? extends T> elements,
                                                                              U zero, BiFunction<? super U, ? super T, ? extends U> operation,
                                                                              C cumulativeResult, BiFunction<C, U, C> combiner,
                                                                              Function<C, R> finisher) {
        U acc = zero;
        cumulativeResult = combiner.apply(cumulativeResult, acc);
        for (T a : elements) {
            acc = operation.apply(acc, a);
            cumulativeResult = combiner.apply(cumulativeResult, acc);
        }
        return finisher.apply(cumulativeResult);
    }

    static <T, U, C extends Iterable<U>, R extends Traversable<U>> R scanRight(Iterable<? extends T> elements,
                                                                               U zero, BiFunction<? super T, ? super U, ? extends U> operation,
                                                                               C cumulativeResult, BiFunction<C, U, C> combiner,
                                                                               Function<C, R> finisher) {
        final Iterator<? extends T> reversedElements = reverseIterator(elements);
        return scanLeft(reversedElements, zero, (u, t) -> operation.apply(t, u), cumulativeResult, combiner, finisher);
    }

You are right, we do not need to add reverseIterator() to Traversable.

Instead this line should be changed in Collections.reverseIterator():

@SuppressWarnings("unchecked")
static <T> Iterator<? extends T> reverseIterator(Iterable<? extends T> iterable) {
    if (iterable instanceof java.util.List) {
        final java.util.List<T> list = (java.util.List<T>) iterable;
        return new Iterator<T>() {
            java.util.ListIterator<T> delegate = list.listIterator(list.size());

            @Override
            public boolean hasNext() { return delegate.hasPrevious(); }

            @Override
            public T next() { return delegate.previous(); }
        };
-    } else {
-        final Seq<? extends T> result = (iterable instanceof Seq) ? (Seq<T>) iterable
-                                                                  : Vector.ofAll(iterable);
-        return result.reverseIterator();
+    } else if (iterable instanceof Seq) {
+        return ((Seq<T>) iterable).reverseIterator();
+    } else {
+        return Iterator.ofAll(iterable).foldLeft(List.<T> empty(), List::prepend).iterator();
    }
}

[ashrwin]

I am looking at the correct file only :) In the first comment on this page, you had asked to re-implement scanLeft like this

static <T, U, R extends Traversable<U>> R scanLeft(Traversable<? extends T> traversable,
            U zero, BiFunction<? super U, ? super T, ? extends U> operation, Function<Iterator<U>, R> finisher)

I thought we are going to change the method signature of scanRight also 😄

[danieldietrich]

@ashrko619 Thank you, I was confused. Yes, we can change the signature of Collections.scanRight.

[ashrwin]

If we change the signature of Collections.scanRight we need to reverse the results again before applying the finisher, something like this

static <T, U, R extends Traversable<U>> R scanRight(Traversable<? extends T> traversable,
                                                    U zero, BiFunction<? super T, ? super U, ? extends U> operation, Function<Iterator<U>, R> finisher) {
    final Iterator<? extends T> reversedElements = reverseIterator(traversable.iterator());
    return scanLeft(reversedElements, zero, (u, t) -> operation.apply(t, u), us -> finisher.apply(reverseIterator(us)));
}
//Call Site
Collections.scanRight(this, zero, operation, Iterator::toVector)

We can reuse the reverseIterator method so that it is efficient for IndexedSeq but for others we have to reverse twice. Is this ok ?

[danieldietrich]

@ashrko619 Thank you for your suggestions. I looked a bit through the code and think it should look like this:

class Collections {

    static <T, U, R extends Traversable<U>> R scanLeft(Traversable<? extends T> traversable,
            U zero, BiFunction<? super U, ? super T, ? extends U> operation, Function<Iterator<U>, R> finisher) {

        final Iterator<U> iterator = traversable.iterator().scanLeft(zero, operation);
        return finisher.apply(iterator);
    }

    static <T, U, R extends Traversable<U>> R scanRight(Traversable<? extends T> traversable,
            U zero, BiFunction<? super T, ? super U, ? extends U> operation, Function<Iterator<U>, R> finisher) {
        final Iterator<U> iterator = reverseIterator(traversable).scanLeft(zero, (u, t) -> operation.apply(t, u));
        return finisher.apply(iterator);
    }

}

(plus the changes to the reverseIterator() method mentioned in this comment)

After changing the methods, this test should produce the same results:

import javaslang.collection.Array;
import java.util.function.BiFunction;
import static javaslang.API.*;

public class Test {

    public static void main(String[] args) {

        Array<Integer> a = Array(1, 2, 3);
        BiFunction<Integer, Integer, Integer> product = (i, j) -> i * j;

        // Array(10, 10, 20, 60)
        println(a.scanLeft(10, product));

        // Array(60, 60, 30, 10)
        println(a.scanRight(10, product));

    }

}

[ashrwin]

@danieldietrich

 static <T, U, R extends Traversable<U>> R scanRight(Traversable<? extends T> traversable,
            U zero, BiFunction<? super T, ? super U, ? extends U> operation, Function<Iterator<U>, R> finisher) {
  // Input -> 1, 2, 3
  // 1, 2, 3 -> reverse -> 3, 2, 1
  // 3, 2, 1 -> scanLeft -> 10, 30, 60, 60
  // we need to reverse the iterator again before applying the finisher
  final Iterator<U> iterator = reverseIterator(traversable).scanLeft(zero, (u, t) -> operation.apply(t, u));
  return finisher.apply(iterator);
}

[danieldietrich]

Hi @ashrko619, you are right! The result needs to be reversed before applying the finisher - thank you.

[danieldietrich]

fixed with #1684