# binary minheap using locally defined ``isless''

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
``````

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
``````

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

Thanks, that simplifies things considerably…

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?)

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 `::Node`s 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

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.

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

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