Is it intentional that fold and reduce for List<T> neglect linked structures?

In fold, foldRight, reduce, reduceRight extension functions for List<T>, the items are obtained through get(index).

This means that the total time for LinkedList<T> and other linked lists will be O(n^2).
Using listIterator() instead would improve the situation for linked lists, but my tests show that it slightly slows down the execution for random access lists.

Is it intentional that linked lists performance is completely neglected in these operations?
Should linked lists be avoided generally when working with stdlib?

It looks like only foldRight and reduceRight actually use get, from what I’m looking at, but yeah, seems like it should check to see if the list implements RandomAccess and then either use get or listIterator. In the mean time, I guess you could either reverse the list in advance yourself or just use ArrayList…which I think is probably better 99% of the time anyway, unless you’re frequently removing from the middle of the list.

Currently it’s a some form of optimization which is feasible for RandomAccess lists, especially in Android: it allows not to create Iterator instances if possible.

Branching in these methods (fold, foldRight, reduce, reduceRight) based on whether the List supports RandomAccess isn’t always straightforward: having two branches would require to inline the reduction operation two times, which might be undesirable considering resulting bytecode size.

We may revise these implementations in one of 1.0.x releases.

1 Like