# 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: Deprecate IterableOnceOps.fold by BalmungSan Â· Pull Request #9972 Â· scala/scala Â· GitHub

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 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