Do sorted ranges have any special properties?

[Peter Alexander]

Personally, I would just expose all accelerated algorithms for sorted 
ranges, and make the user call them explicitly e.g. if they know their 
range is sorted, make them call binarySearch (or whatever) instead of find.

I have two primary reasons for this:

1. Having the function choose the right algorithm puts an undue burden 
on the function writer, which translates into increased uncertainty for 
the user of the function, "If I call find(assumeSorted(r)), is it going 
to use binary search? What if I call SomeThirdParty.find? Will it know 
about assumeSorted?"

2. While we're only discussing assumeSorted now, there are a myriad of 
other assumeX wrappers that would be useful:

assumeUnimodal(range) - Allows ternary search for maxElement.
assumeDistinct(range) - uniq doesn't need to do anything.
assumePrime(int) - e.g. getFactors(assumePrime(x)) returns [1, x]
assumeAssociative(binOp) - power can work in O(lg(n)).

* power!(binOp)(a, b) := reduce!(binOp)(replicate(a, b))

Do we provide wrappers for these as well, and make the algorithms check 
for all relevant ones?

---

I say no. Provide ternarySearch, powerAssociative etc., and let the user 
choose them when he/she knows they are the right algorithm. That way, 
function writers can focus on writing specialized functions, and 
function users can rest assured that the function they are calling is 
performing the algorithm that they expect (with the complexity bounds 
that they expect).