In theory at least that precondition could be guaranteed by a newtype like SortedList without requiring any linear scan, that would work at least for most cases where lists are sorted by an algorithm. Though not necessarily custom data which is constructed sorted/maintains it's sorting outside the algorithm, but you could perhaps have an unsafe constructor for your SortedList type. That should avoid a linear scan...