search

fsharp / fslang-design

RFCs and docs related to the F# language design process, see https://github.com/fsharp/fslang-suggestions to submit ideas
512 stars 142 forks source link

Create FS-1135-map-binary-search.md #734

Open reinux opened 1 year ago

reinux commented 1 year ago

Rendered RFC

dsyme commented 1 month ago

@KevinRansom @vzarytovskii @abelbraaksma Comments on this please?

T-Gro commented 1 month ago

@reinux :

I am still thinking of a better self-explainable API, I don't think a tuple of 3 with same types is best. Even though the ordering (previous,match,next) is likely the most natural one here.

Just to show another proposal, I have tried to DU-model the outcomes, but I do not think it is any better to your proposal here. The number of possible combinations is an inherent part of binary search if we want this to be a primitive supporting all sorts of scenarios.

type Node<'TKey,'TValue> = (struct ('TKey * 'TValue))

[<Struct>]
type MapPosition<'a,'b> =  
    | Between of below:Node<'a,'b> * above:Node<'a,'b>
    | AtMinimum of above:Node<'a,'b>
    | AtMaximum of below:Node<'a,'b>
    | MapWasEMpty

[<Struct>]
type BinarySearchResult<'a,'b> =
    | ExactMatch of hit:Node<'a,'b> * position:MapPosition<'a,'b> 
    | NotFound of  position:MapPosition<'a,'b>