Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Returntype of searchsorted* should always be the keytype #32568

Closed
sostock opened this issue Jul 12, 2019 · 4 comments · Fixed by #32978
Closed

Returntype of searchsorted* should always be the keytype #32568

sostock opened this issue Jul 12, 2019 · 4 comments · Fixed by #32978
Labels
help wanted Indicates that a maintainer wants help on an issue or pull request

Comments

@sostock
Copy link
Contributor

sostock commented Jul 12, 2019

Currently, the type of the index returned by the find* and searchsorted* functions is kind of inconsistent:

  • findfirst etc. (almost) always returns an Int (unless it returns nothing).
  • the return value searchsortedfirst(vec, x) depends on the type of x:
    julia> typeof(searchsortedfirst(1:5, 2))
    Int64
    
    julia> typeof(searchsortedfirst(1:5, big(2)))
    BigInt

The different return types make it harder to write type-stable code. For example, I am writing a function that returns an index of a sorted array, using findlast in one branch of the function and searchsortedlast in another.

Another problem with the find* behavior is that it errors when the indices of the array are not representable as Ints (but this is a separate issue that should be fixed in keys or LinearIndices, cf. #32566)

My proposal: The type returned by find* and searchsorted* should only depend on the type of the collection that is being searched. In my opinion, the obvious choice for that type would be eltype(eachindex(collection)).

@StefanKarpinski
Copy link
Member

Agree that it seems broken for the type of the value being searched for to affect the type of the index returned.

@mbauman
Copy link
Member

mbauman commented Jul 16, 2019

Yes, this needs to be fixed. Note that this only affects ranges — they do math against the value to compute the result, but we need to convert things back to the correct index type. It should be as easy as throwing a ::keytype(r) return type assertion on the relevant functions.

@mbauman mbauman added help wanted Indicates that a maintainer wants help on an issue or pull request bug Indicates an unexpected problem or unintended behavior and removed bug Indicates an unexpected problem or unintended behavior labels Jul 16, 2019
@mbauman mbauman changed the title Returntype of find* and searchsorted* Returntype of searchsorted* should always be the keytype Jul 16, 2019
@sostock
Copy link
Contributor Author

sostock commented Aug 19, 2019

In addition to the searchsorted* functions, findnext and findprev are also affected. The returntype of findnext([f,] A, start)/findprev([f,] A, start) depends on the type and value of start:

julia> typeof(findnext(iseven, 1:5, big(1)))
Int64

julia> typeof(findnext(iseven, 1:5, big(2)))
BigInt

Should this be fixed as well, or can it be ignored (since most people will probably use an Int for start anyway)?

@mbauman
Copy link
Member

mbauman commented Aug 19, 2019

Yes, that'd be good to fix at the same time.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
help wanted Indicates that a maintainer wants help on an issue or pull request
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants