reduceLeft and HashMap

If HashMap maintains no order, why there is a method reduceLeft, which must assume a certain order?

All collections have some iteration order, HashMap simply don’t guarantee that the iteration order is the same as the insertion order,

I see, so is there a way to know and control the iteration order for collections without order? In other word, to make a useful distinction between left and right for maps one needs somehow to control the ordering.

Nop, you don’t control the iteration order.

Also, note that foldLeft and foldRight both “iterate” from left to right, the difference is the order of associativity.

1 Like

To control iteration order, you must convert to a collection that is ordered in the manner you wish to control.

Or, roll your own iterator…which will likely be just as or more inefficient than using an existing collection implementation already behavior, performance, and security battle-tested.

1 Like

Sorry, but it seems your last statement is contradictory. Let us not touch foldLeft here, but focus on the reduceLeft, as in the original post. Let subscripts indicate the order and take a three element collection {a1, a2, a3}. I would tend to say that as we go from left to right, we go from 1 to 3. Then,
reduceLeft evaluates op(op(a1,a2),op3) --left to right, whereas reduceRight op(a1,op(a2, a3))–right to left. Am I missing something? I do not see how reduceRight iterates from left to right.

But even this is not the point. If we cannot fix the order, it makes no sense to talk about left and right at all! This means that Map contains superfluous methods. If this is not the case, I would be very curious of a real life example where one should use only reduceLeft or reduceRight (but not both equivalently) of a Map.

Look, the elements are in the same left to right order, first a1 second a2 finally a3, the “iteration” is still left to right, what changed is the associative order we are associating from right to left.

Anyways, you are not alone in thinking that foldLeft / foldRight don’t make sense on something like a Map, check this comment from April: https://github.com/scala/scala/pull/9972#issuecomment-1068391166

Yeah, on something for which you don’t control the order you either have something commutative or you simply don’t care at all. Thus, you are correct both are either wrong or interchangeable.
PS: That is why cats don’t provide foldMap on a Map or Set but rather an unorderedFoldMap the first only requires Monoid (which only guarantees associativity) whereas the former requires a CommutativeMonoid

1 Like

Ok, we are not in contradiction then :slight_smile: I like a little excursion to the category theory.

If the underlying collection happens to be a Java HashMap or HashSet, then you can use instead a Java LinkedHashMap or LinkedHasSet. Then the iterator order will be the insertion order. In Java, I have found the idiom

for(Map.Entry<K,V> entry : hashMap.entrySet())

more useful than an iterator, but I am not sure what order the set Set<Map.Entry<K,V>> that entrySet() returns will have.

Charles Elliott

That’s not necessarily true. The default stacksafe implementation of foldRight in the standard library is implemented as reversed.foldLeft(...)

1 Like

Sure, I am speaking in conceptual terms, the real implementation may be different.

1 Like