RFC FS-1135: Map.binarySearch

[reinux]

This is the discussion thread for the Map.binarySearch, RFC FS-1135 (link tbd): the addition of a Map.binarySearch function which would provide a way to find items with adjacent keys.

[T-Gro]

Thanks, now I appreciate the full triplet - even in the case of value being found, it can still make sense to access previous/next.

1/ If a match is found by "lucky guess" somewhere between two bounding keys, wouldnt it cause additional cpu cost to provide the precise (next,prev) siblings ?
Maybe the implementation will show that better.

2/ I still think an explicit return type would be safer for wide usage.
The particular risky part about the API proposal is the ordering of same-typed elements in a triple - should the first one be the match, or the previous element? Feels at least uncertain, as a triple is always anonymous.

A DU with data can provide names to the items, or a struct record could do.

[reinux]

1/ If a match is found by "lucky guess" somewhere between two bounding keys, wouldnt it cause additional cpu cost to provide the precise (next,prev) siblings ? Maybe the implementation will show that better.\

If the match is at the bottom of the tree, it can take advantage of the fact that the adjacent keys will be above it and hence already discovered. Or, if there's no exact match, it doesn't have to do anything else, because it'll have traversed the closest two in the process. Otherwise, if it's an exact match and it isn't at the bottom of the tree, it has to traverse the tree a little more (conveniently, using the brand new minKeyValue and maxKeyValue functions), so there's another two log n's worth of iterations to do. Not terrible, but you're right, there's some additional cpu cost in that case.

We could wrap it in a lazy, which I don't think would affect the ergonomics too much, but aesthetically it might not fit the feel of the rest of the API.

2/ I still think an explicit return type would be safer for wide usage. The particular risky part about the API proposal is the ordering of same-typed elements in a triple - should the first one be the match, or the previous element? Feels at least uncertain, as a triple is always anonymous.

A DU with data can provide names to the items, or a struct record could do.

Agreed. I mostly just stuck with a tuple since that's what the rest of the FSharp.Core collection APIs seem to do, but with those, it's always easy to infer from the types being returned or from common sense what each of the elements is (e.g. zip3 will return things in order from left to right).

FWIW, my personal preference might be for a single-case DU, just because even after having used F# for a huge portion of my life, I still tend to forget the syntax for pattern matching on records 😂