Are the head and tail of a Set guaranteed to be mutually exclusive?

Question

The documentation says that Set.head returns the "first" item, and .tail returns "all but the first".* Since a Set doesn't really have a "first" item, the documentation warns that without an ordered type, you might get a different result on different runs. But are you guaranteed that the tail won't include the head?

The reason I'm asking is I'm wondering if it's OK to recurse down a Set like this:

def recurse(itemsToExamine: Set[Item], acc: Result): Result =
  if (itemsToExamine.isEmpty) acc
  else {
    val item = itemsToExamine.head
    recurse(
      item.spawnMoreItems ++ itemsToExamine.tail,
      acc.updatedFor(item))
  }

If that's legitimate, it would certainly be nicer than converting from Set to Seq and back in order to separate head and tail on each recursion.

---

*Actually, it says "selects the first item" and "selects all but the first item". I assume that "selects" is just a poor choice of word. If there's a reason for saying "selects" rather than "returns", please let me know.

Answer 1

I'm not 100% sure about this, because I haven't looked too much at the implementation, but for any HashSet there's an implicit ordering based on the hashCode (of type Int) of the values that are already in the Set.

That means that for any Set instance, calls to head and tail will respect that ordering, so it won't be the same element. Even more, successive iteration through the elements of a given Set instance should yield the elements in the same order, because the Set is immutable.

The takeaway is that while the ordering is unknown, there is one for any instance, which may change as soon as you add (mutably or immutably) a new element to the Set.