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.

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

5

itaiferber gave you the correct answer to the surface-level question. Bravo.

But at a more fundamental level, why is it even possible that you came across a situation where the code could seemingly produce a non-deterministic result?

Because the logic wasn't abstracted to a level that made it easier to not write bugs, than to write them.

Not only is there a bug in the logic, as noted above, but total is also Optional, when it's impossible for your code to produce nil.

What you're actually looking for is missing from the standard library.

var total: Decimal? { items.values.lazy.flatMap(\.self).reduce(+) }

public extension Sequence {
  /// - Returns: `nil` If the sequence has no elements, instead of an "initial result".
  @inlinable func reduce<Error>(
    _ transform: (Element, Element) throws(Error) -> Element
  ) throws(Error) -> Element? {
    var iterator = makeIterator()
    guard let first = iterator.next() else { return nil }
    do { return try IteratorSequence(iterator).reduce(first, transform) }
    catch { throw error as! Error }
  }
}

The overload is not missing from Reductions.

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
8

My argument is that the tri-conflation of 0, nil, and result in the original code exists because of the missing overload. flatMap helps, but you cannot write the code well without the missing overload. This is true for all reduce operations where nil is the default for empty sequences; I can't believe this hasn't been fixed in 11 years.

var total: Decimal? {
  items.values.reduce(nil) { total, values in
    guard let sum = values.reduce(+) else { return total }
    guard let total else { return sum }
    return total + sum
  }
}

var total: Decimal? {
  items.values.reduce(nil) { total, values in
    guard let sum: Decimal = (values.reduce(nil) { sum, value in
      guard let sum else { return value }
      return sum + value
    })
    else { return total }
    guard let total else { return sum }
    return total + sum
  }
}