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.

1 Like
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).

1 Like
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.

3 Likes
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.

1 Like
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.

1 Like
20 
apply =

maybe