binary minheap using locally defined ``isless''

New to Julia
1

I’m trying to write an algorithm (the fast marching method for solving the Eikonal equation) that uses a binary minheap with comparisons defined on the nodes of a network. Because I need both the node indices and values all the time, I thought an easy way to implement the algorithm would be to define a custom type that kept track of indices I was interested in, and define the isless operator such that it looked up the current node values in the array that stored them (code is below). My issue is that I get a ERROR: MethodError: no method matching isless(::Node, ::Node) when I try to copy this function into the interpreter; it seems that binary_minheap doesn’t like the function only being in local scope - any advice on how to proceed?

function do_stuff()    
   T = fill(Inf, size(100,100))

    struct Node
        idx::Int
    end

    function isless(a::Node, b::Node)
        isless(T[a.idx], T[b.idx])
    end

    active_band = binary_minheap(Node)

main loop .....

T
end
2

There’s no benefit to defining your isless method inside the function body, so why not just define it outside?

import Base: isless

function isless(a::Node, b::Node)
  ...
end

function do_stuff()
  ...
end
3

Oh, I see, your isless is using the T from the local scope. In that case, overloading Base.isless is probably the wrong thing to do, as later calls to isless would keep using the same T in a pretty confusing way.

Instead, you can just define an anonymous function and pass that function into binary_minheap. This is how custom comparators in Base.sort work.

julia> sort([1,-2,-3], lt=(x, y) -> abs(x) < abs(y))
3-element Array{Int64,1}:
 1
-2
-3
2 Likes
4

Thanks, that simplifies things considerably…

5

Works here, but I am pretty sure this is another example or where ADL would make this a non-issue (i.e. Function name conflict: ADL / function merging?)

6

I mean…I guess? But think about what’s being implemented here: we have a comparison function that relies on inherently local information (the value of T). Having this isless method automatically attach to the global Base.isless would mean that all comparisons of ::Nodes forever would use that same local information regardless of how or where that comparison occurs. Avoiding such weird non-local behavior is exactly why Julia requires you to be explicit before extending external methods, since such extension is inherently global in effect.

1 Like
7

Couldn’t agree more. But this is exactly the problem ADL solves. Lets say that the struct Node type is more interesting so that a custom type is worthwhile (as you showed it wasn’t really needed in this specific example).

Just to be clear, with an ADL based solution:

  • You would never define your functions, such as isless inside of the Base namespace. You no longer need to shove things into Base just so the generic algorithms in base would be able to write generic code with isless, *, etc. for the custom type.
  • You no longer need to do any sort of using... at all, including not requiring using Base. You instead can just import whatever, and provide namespace qualifications on the types.
  • In C++, for example, which supports all sorts of generic insanity, you never see people add their operator* or operator< into the std:: namespace… if those are defined on types in another namespace, then they stay in that namespace. Furthermore, tend to qualify many (or all?) of the types they use with a namespace qualification.
  • But then, if the isless is defined for comparing types that are not in the Base, how can you write a generic function in Base (or even in another namespace!) that uses the isless in other namespaces and local scopes? This is precisely what ADL is designed to do… enable lookup of methods into the namespaces of the argument types.
8

This is the #user:first-steps category. Let’s try not to get sidetracked with developer jargon and theoretical redesigns.

@rdeits has it right — you can explicitly pass your comparator to sort. This needn’t be an anonymous function; you can define your own mycompare function and just pass it directly as sort([1,-2,-3], lt=mycompare). You could even name mycompare with the name isless (like in the original example), but that will shadow the builtin Base.isless function and can be confusing.

5 Likes
9

100% there is one and only one issue here: this API needs the ability to pass a comparison function. Anything else gets into dynamic scoping, which has historically ended badly and for good reason: it destroys the ability to reason locally about what things mean (or, if your allergic to “meaning” then substitute “refers to”).

6 Likes