No good deed goes unpunished, eh? There are two reasonable search_sorted APIs: the one this PR implements and the one it replaces. To wit, search_sorted can be defined to return the index of an exact match of the input if it exists, as this PR does; or search_sorted can be defined to return the largest index whose value is less than or equal to the input, if it exists, as it used to. The former is better for testing membership in sets, whereas the latter is better for implementing piecewise-constant functions, such as the CDF of a categorical distribution. The test suite uses it that way in at least one place, hence the failure.
I think we should have both. The exact-match-only API is easily implemented in terms of the largest-smaller-index API (and now that we have the case-of-case optimization, doing it that way shouldn't even incur any performance cost, provided the optimization triggers). We might even try to change the type of largest-smaller-index API to return some type like Post n instead of Maybe n to imply that the Nothing case actually means "the query is smaller than the smallest element of the array" rather than "the query is not present in the array".
axch
commented
1 year ago
No good deed goes unpunished, eh? There are two reasonable
search_sortedAPIs: the one this PR implements and the one it replaces. To wit,search_sortedcan be defined to return the index of an exact match of the input if it exists, as this PR does; orsearch_sortedcan be defined to return the largest index whose value is less than or equal to the input, if it exists, as it used to. The former is better for testing membership in sets, whereas the latter is better for implementing piecewise-constant functions, such as the CDF of a categorical distribution. The test suite uses it that way in at least one place, hence the failure.I think we should have both. The exact-match-only API is easily implemented in terms of the largest-smaller-index API (and now that we have the case-of-case optimization, doing it that way shouldn't even incur any performance cost, provided the optimization triggers). We might even try to change the type of largest-smaller-index API to return some type like
Post ninstead ofMaybe nto imply that theNothingcase actually means "the query is smaller than the smallest element of the array" rather than "the query is not present in the array".