Why does this code product a non-deterministic result?

Using Swift
1

There's a fairly obvious bug here where I'm passing in the wrong initial value (result vs 0) on line 11, but that aside I'm surprised that this produces a non-deterministic result?

import Foundation

var items: [String: [Decimal]] = [
    "1": [1, 10],
    "2": [100],
    "3": [1000],
]

var total: Decimal? {
    return items.values.reduce(0, { result, values in
        result + values.reduce(result, { runningSubtotal, value in
            runningSubtotal + value
        })
    })
}
        
print("Total: \(total!)")
2

This is due to the fact that when you iterate a Dictionary (e.g., items) or Set, the iteration order is based on the order of the elements in memory — which depends on their hash value. These hash values are based on a seed which is randomized on every run of your program, leading to a different iteration order every time you run the above code.

If you print(values) inside of your outer reduce, you'll be able to see that the order they're passed in changes — and because result compounds here, this affects the final result.

9 Likes
3

Re your bug on line 11, passing result is fine if you don't also add result, i.e. -

var total: Decimal? {
    return items.values.reduce(0, { result, values in
        values.reduce(result, { runningSubtotal, value in
            runningSubtotal + value
        })
    })
}
1 Like
4

Ah yes, good point!

6

FWIW, the magic here isn't in the reduce(+) but in lazy.flatMap(\.self), in that you're concatenating the list-of-lists into a single list and then adding, eliminating the inner loop. You can achieve this today with the stdlib too, just by providing 0 as the initial value:

var total: Decimal? { items.values.lazy.flatMap(\.self).reduce(0, +) }
1 Like
7

If you are interested in a key-value store to preserve order you might also want to try OrderedDictionary from swift-collections.

2 Likes