Search code examples
scalafindnon-deterministic

Will find() ever act nondeterministically?

I know if I run a simple find() function such as (1 to 5).find(_ < 6), I will always get back Some(1).

Here, find() is deterministic and will always return the same result, even though the collection (1 to 5) contains four other elements that make the predicate _ < 6 true.

My question is - can find() ever act nondeterministically?

Does there exist a collection and/or a predicate that will make collection.find(predicate) return different results for successive executions?

Solution

  • For a linear sequence, find will always proceed linearly, and thus it will always return the same element.

    This is not necessarily true for a non-linear collection such as Set.

    Set(1 to 5: _*).find(_ < 6) // Some(5)
Set(1 to 5: _*).find(_ < 6) // Some(5)

    Here you get a different element, although the implementation seems to be deterministic due to value equality.

    This equality can easily be broken:

    // reference equality
class Box(val peer: Int) { override def toString = peer.toString }

def mkIndet() = Set((1 to 5).map(new Box(_)): _*)

mkIndet.find(_.peer < 6) // "random"
mkIndet.find(_.peer < 6) // "random"
mkIndet.find(_.peer < 6) // "random"

    Another case is parallel collections:

    def par() = (1 to 10000).par.find(i => i % 1000 == 0)

par()  // "random"
par()  // "random"
par()  // "random"