Binary heap type problems

General Usage
1

(A bit of a long post because error messages)

i’m trying to generate a binary heap (from DataStructures) where the data item is a pair consisting of an integer and a function.

The following works

julia> function f1() println("hello") end
f1 (generic function with 1 method)

julia> function f2() println("goodbye") end
f2 (generic function with 1 method)

julia> using DataStructures

julia> x = BinaryHeap(Base.By(first), [ ])
BinaryHeap{Any,Base.Order.By{typeof(first),Base.Order.ForwardOrdering}}(Base.Order.By{typeof(first),Base.Order.ForwardOrdering}(first, Base.Order.ForwardOrdering()), Any[])

julia> push!(x, 1=>f1)
BinaryHeap{Any,Base.Order.By{typeof(first),Base.Order.ForwardOrdering}}(Base.Order.By{typeof(first),Base.Order.ForwardOrdering}(first, Base.Order.ForwardOrdering()), Any[1 => f1])

julia> push!(x, 2=>f2)
BinaryHeap{Any,Base.Order.By{typeof(first),Base.Order.ForwardOrdering}}(Base.Order.By{typeof(first),Base.Order.ForwardOrdering}(first, Base.Order.ForwardOrdering()), Any[1 => f1, 2 => f2])

but this doesn’t.

julia> x = BinaryHeap(Base.By(first), [ 1=>f1 ])
BinaryHeap{Pair{Int64,typeof(f1)},Base.Order.By{typeof(first),Base.Order.ForwardOrdering}}(Base.Order.By{typeof(first),Base.Order.ForwardOrdering}(first, Base.Order.ForwardOrdering()), [1 => f1])

julia> push!(x, 2=>f2)

ERROR: MethodError: Cannot `convert` an object of type typeof(f2) to an object of type typeof(f1)
Closest candidates are:
  convert(::Type{T}, ::T) where T at essentials.jl:171
Stacktrace:
 [1] convert(::Type{Pair{Int64,typeof(f1)}}, ::Pair{Int64,typeof(f2)}) at ./pair.jl:71
 [2] push!(::Array{Pair{Int64,typeof(f1)},1}, ::Pair{Int64,typeof(f2)}) at ./array.jl:934
 [3] heappush!(::Array{Pair{Int64,typeof(f1)},1}, ::Pair{Int64,typeof(f2)}, ::Base.Order.By{typeof(first),Base.Order.ForwardOrdering}) at /home/briand/.julia/packages/DataStructures/ixwFs/src/heaps/arrays_as_heaps.jl:72
 [4] push!(::BinaryHeap{Pair{Int64,typeof(f1)},Base.Order.By{typeof(first),Base.Order.ForwardOrdering}}, ::Pair{Int64,typeof(f2)}) at /home/briand/.julia/packages/DataStructures/ixwFs/src/heaps/binary_heap.jl:91
 [5] top-level scope at REPL[8]:1

I’m unclear on why the functions are “typeof(f1)” and “typeof(f2)”. I looked through the documentation because I know the subject of function type annotation has come up before, but I couldn’t find anything which talked about it.

More importantly, if I wanted to explicitly type the array when creating the BinaryHeap structure how would I do that ?

Here’s my attempt.

julia> x = BinaryHeap(Base.By(first), Array{Pair{Int,Function},1}[ ])
BinaryHeap{Array{Pair{Int64,Function},1},Base.Order.By{typeof(first),Base.Order.ForwardOrdering}}(Base.Order.By{typeof(first),Base.Order.ForwardOrdering}(first, Base.Order.ForwardOrdering()), Array{Pair{Int64,Function},1}[])

julia> push!(x, 1=>f1)
ERROR: MethodError: Cannot `convert` an object of type Pair{Int64,typeof(f1)} to an object of type Array{Pair{Int64,Function},1}
Closest candidates are:
  convert(::Type{T}, ::AbstractArray) where T<:Array at array.jl:554
  convert(::Type{T}, ::T) where T<:AbstractArray at abstractarray.jl:14
  convert(::Type{T}, ::LinearAlgebra.Factorization) where T<:AbstractArray at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.5/LinearAlgebra/src/factorization.jl:55
  ...
Stacktrace:
 [1] push!(::Array{Array{Pair{Int64,Function},1},1}, ::Pair{Int64,typeof(f1)}) at ./array.jl:934
 [2] heappush!(::Array{Array{Pair{Int64,Function},1},1}, ::Pair{Int64,typeof(f1)}, ::Base.Order.By{typeof(first),Base.Order.ForwardOrdering}) at /home/briand/.julia/packages/DataStructures/ixwFs/src/heaps/arrays_as_heaps.jl:72
 [3] push!(::BinaryHeap{Array{Pair{Int64,Function},1},Base.Order.By{typeof(first),Base.Order.ForwardOrdering}}, ::Pair{Int64,typeof(f1)}) at /home/briand/.julia/packages/DataStructures/ixwFs/src/heaps/binary_heap.jl:91
 [4] top-level scope at REPL[10]:1

I’ve been trying various things, aka guessing, and reading through the docs, can’t seem to locate anything that will help.

Thank you.

2

You specified the element type to be a Array{Pair{Int64,Function},1}, which is probably not what you intended. Try to use just Pair{Int,Function} and see if that works.

Every function has its own type with supertype Function, which allows for dispatch on function type and various optimizations. You can probably imagine that knowing the exact type of a function at compile time helps enormously with inference and optimization of functions that take functions as arguments and use them on some sorts of data.

The problem you ran into is, that you created an array with a single {Int, Functio} pair for initialization. The array, upon its creation, tries to take on the most specific type that holds the values you supplied, which happenes to be {Int,typeof(f1)}. (This is most often what you want, say, with numbers, but it may seem weird with functions indeed)
Try creating an array with two different functions initially and see for yourself! Good luck :slight_smile:

Edit: also note, that you can create arrays with explicit type specification by prepending the type to the array literal:

julia> [1=>(+), 2=>(-)]
2-element Vector{Pair{Int64, Function}}:
 1 => (+)
 2 => (-)

julia> [1=>(+), 2=>(+)]
2-element Vector{Pair{Int64, typeof(+)}}:
 1 => (+)
 2 => (+)

julia> Pair{Int,Function}[1=>(+), 2=>(+)]
2-element Vector{Pair{Int64, Function}}:
 1 => (+)
 2 => (+)
```
2 Likes