I'm confused by Data.Map API. I'm looking for a simple way to find a range of keys of the map at log(n) cost. This is a basic concept known as "binary search", and maybe "bisecting".

I see this strange takeWhileAntitone function where I need to provide an "antitone" predicate function. It's the first time I encounter this concept.

After reading Wikipedia on the topic, this seems to be simply saying that there may be only one place where the function changes from True to False when applied to arguments in key order. This fits a requirement for a binary search.

Since the API is documented in a strange (to me) language, I wanted to ask here:

• if my understanding is correct, and
• is there a reason these functions aren't called bisect, binarySearch or similar?

CodePudding user response：

Since the API is documented in a strange (to me) language, I wanted to ask here:

• if my understanding is correct, and

Yes. takeWhileAntitone (and other similarly named variants in the library) is the function for doing binary search on keys. It's not named takeWhile because it does not work for any argument predicate, so if you're reviewing code, it serves as a reminder to check for that.

• is there a reason these functions aren't called bisect, binarySearch or similar?

1. This name serves to distinguish variants takeWhileAntitone, dropWhileAntitone, spanAntitone that "do binary search" but with different final results.

2. takeWhile is a well-known name from Haskell's standard library (in Data.List).

3. In FP we like to distinguish the "what" from the "how". "binary search" is an algorithm ("how"). "take while" is also literally a "how", but its meaning is arguably more naturally connected to a "what" (the longest prefix of elements satisfying a predicate). In particular, the interpretation of "take while" as "longest prefix" doesn't rely on any assumption about the predicate.