Problem with searchsortedfirst

General Usage
1

I have a problem with searchsortedfirst. I want to search a list of Pair{Symbol,Int} which is sorted by the Symbol.

julia> a=[:a=>1,:b=>2]
2-element Vector{Pair{Symbol, Int64}}:
 :a => 1
 :b => 2

julia> searchsortedfirst(a,:b;by=first)
ERROR: MethodError: no method matching iterate(::Symbol)
Closest candidates are:
  iterate(::Union{LinRange, StepRangeLen}) at ~/julia-1.7.0/share/julia/base/range.jl:826
  iterate(::Union{LinRange, StepRangeLen}, ::Integer) at ~/julia-1.7.0/share/julia/base/range.jl:826
  iterate(::T) where T<:Union{Base.KeySet{<:Any, <:Dict}, Base.ValueIterator{<:Dict}} at ~/julia-1.7.0/share/julia/base/dict.jl:695
  ...
Stacktrace:
 [1] first(itr::Symbol)
   @ Base ./abstractarray.jl:418
 [2] lt(o::Base.Order.By{typeof(first), Base.Order.ForwardOrdering}, a::Pair{Symbol, Int64}, b::Symbol)
   @ Base.Order ./ordering.jl:111
 [3] searchsortedfirst
   @ ./sort.jl:184 [inlined]
 [4] searchsortedfirst
   @ ./sort.jl:295 [inlined]
 [5] #searchsortedfirst#4
   @ ./sort.jl:297 [inlined]
 [6] top-level scope
   @ REPL[27]:1

Am I misusing searchsortedfirst? This is in julia1.7.0

2

I think it has to compare Pair{Symbol, Int64} to just a symbol :b.
See for example in contrast:

julia> searchsortedfirst(a,:b=>2;by=first)
2

But the following doesn’t work either:

julia> a=[ :a, :b ]
2-element Vector{Symbol}:
 :a
 :b

julia> searchsortedfirst( a, :b ;by=first)
ERROR: MethodError: no method matching iterate(::Symbol)

So Symbols seem to have some issue.
As a first and clumsy attempt to work around, I suggest this:

julia> a=[:a=>1,:b=>2]
2-element Vector{Pair{Symbol, Int64}}:
 :a => 1
 :b => 2

julia> searchsortedfirst( [ String(x[1]) for x in a ], String(:b) ;by=first)
2

which isn’t the best, I am sure.

3

Your example rightly does not work since first(:a) is an error. On the other hand first(:b=>2)is legal and gives :b.

4

This one is better, by defining lt = lowerthan for your case:

julia> searchsortedfirst(a, :b; lt = (x,y) -> x[1] < y )
2

See

help?> searchsortedfirst
search: searchsortedfirst searchsortedlast searchsorted

  searchsortedfirst(a, x; by=<transform>, lt=<comparison>, rev=false)
...
5

I do not want x[1]<y but x[1]<y[1]. This raises also an error.

6

It’s about the elements in a versus :b.
The elements in a are Pair{Symbol, Int64}, e.g. :a=>1
In the list of such elements you are looking for the first :b

If I am right so far, it’s about comparing a Pair{Symbol, Int64} with a Symbol, therefor x[1] vs y where x[1]is the Symbol from inside the Pair, and y is just the Symbol :b.

Is this understandable? I am not sure and not good in being short and on the point.

7

Actually I don’t understand the by keyword, as the list is expected to be already sorted…
So, using by=first here, seems to also apply first to :b which raises the original error. Therefor my idea not using by but defining lt.

8

This may clarify a bit more:

julia> Base.first(s::Symbol)=s

julia> searchsortedfirst(a, :b; by=first)
2
9

The :by keyword tells which part of the objects should be compared.
I thought that the object to compare would be compared to the by part since the following works:

julia> a=[1=>"a",3=>"b"]
2-element Vector{Pair{Int64, String}}:
 1 => "a"
 3 => "b"

julia> searchsortedfirst(a,3;by=first)
2
10

Yes, but you are searching for :b which is a Symbol, and first(::Symbol) raises the original error, because a single Symbol :b is not iterable as it is not a collection.`

julia> first(:b)
ERROR: MethodError: no method matching iterate(::Symbol)

So defining first on type Symbol, as in my last post, resolves this, but it’s not the recommended solution. The recommended solution is defining the less-than relation between Pair{Symbol, Int64} and Symbol.
Now you are editing your replies… this is becoming to awkward, so I think, it’s all said, perhaps not in the best understandable way.

11

Integer number are per definition iterables:

julia> first(1)
1

There is quite some discussion about this, which I don’t look up for you now, but it is like that.
Symbols are not iterable.

12

I edit my posts when I have written a mistake and hope the edit is before you read.
I think I understand: the by is also applied to the value I want to compare (unfortunately)
and my last example works by a fluke (that first is valid for an Int).

13

And I did it anyways:
https://github.com/JuliaLang/julia/issues/7903

14

The discussion got complicated and is solved, but it was not clear to me if it is clear to the reader that this works:

julia> a=[:a=>1,:b=>2,:b=>3,:c=>4]
4-element Vector{Pair{Symbol, Int64}}:
 :a => 1
 :b => 2
 :b => 3
 :c => 4

julia> searchsortedfirst(a, (:b,); by=first)
2

julia> searchsortedfirst(a, (:c,); by=first)
4

(any catch here I don’t see?)

I see now: the order is on the values, not on the keys… (though I’m unsure now, if by=first, if that is not what one wants really)

15

It works since first((:b,)) is defined and returns :b. I think I projected in my mind a better interface for the searchsorted... routines in case of by keyword that the actual interface,that is I hoped that the by function would not be applied to the value given to compare, which seemed natural.

16

Yes, that is catchy. I have been there is some more mundane examples, like:

julia> searchsortedfirst([1,2,3,4], 2, by=x -> x^2)
2

julia>

Sometimes this is very annoying, because it requires one to define the inverse function to be able to search, something that is not always trivial.

17

Perhaps change the meaning of by in julia2.0?

18

I think that I was convinced that that is the reasonable behavior, but I don’t remember why. Let me see if I find the thread. (I found the thread, but it was not really related, I just learnt that there, not really with a good justification).

19

Perhaps we could ask for a compromise, that is a keyword to the searchsorted... function which would signify that the by function is not applied to the object to compare.

20 
apply =

maybe