Efficient way to check if a traversable has more than 1 element in Scala

Question

I need to check if a Traversable (which I already know to be nonEmpty) has a single element or more.

I could use size, but (tell me if I'm wrong) I suspect that this could be O(n), and traverse the collection to compute it.

I could check if tail.nonEmpty, or if .head != .last

Which are the pros and cons of the two approaches? Is there a better way? (for example, will .last do a full iteration as well?)

Answer 1

All approaches that cut elements from beginning of the collection and return tail are inefficient. For example tail for List is O(1), while tail for Array is O(N). Same with drop.

I propose using take:

 list.take(2).size == 1 // list is singleton

take is declared to return whole collection if collection length is less that take's argument. Thus there will be no error if collection is empty or has only one element. On the other hand if collection is huge take will run in O(1) time nevertheless. Internally take will start iterating your collection, take two steps and break, putting elements in new collection to return.

UPD: I changed condition to exactly match the question

Answer 2

Not all will be the same, but let's take a worst case scenario where it's a List. last will consume the entire List just to access that element, as will size.

tail.nonEmpty is obtained from a head :: tail pattern match, which doesn't need to consume the entire List. If you already know the list to be non-empty, this should be the obvious choice.

But not all tail operations take constant time like a List: Scala Collections Performance