# binary minheap using locally defined \`\`isless''

**URL:** <https://discourse.julialang.org/t/binary-minheap-using-locally-defined-isless/10644>\
**Category:** New to Julia\
**Created:** [May 1, 2018, 10:00pm UTC](https://discourse.julialang.org/t/binary-minheap-using-locally-defined-isless/10644 "2018-05-01T22:00:35Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Jack\_Muir](https://avatars.discourse-cdn.com/v4/letter/j/b77776/32.png) [@Jack\_Muir](https://discourse.julialang.org/u/Jack_Muir)\
**Post date:** [May 1, 2018, 10:00pm UTC](https://discourse.julialang.org/t/binary-minheap-using-locally-defined-isless/10644/1 "2018-05-01T22:00:35Z")

</div>

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

```

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [May 2, 2018, 1:39am UTC](https://discourse.julialang.org/t/binary-minheap-using-locally-defined-isless/10644/2 "2018-05-02T01:39:06Z")

</div>

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

```julia
import Base: isless

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

function do_stuff()
  ...
end

```

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [May 2, 2018, 1:42am UTC](https://discourse.julialang.org/t/binary-minheap-using-locally-defined-isless/10644/3 "2018-05-02T01:42:11Z")

</div>

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
julia> sort([1,-2,-3], lt=(x, y) -> abs(x) < abs(y))
3-element Array{Int64,1}:
 1
-2
-3

```

---

<div class="post-metadata">

**Author:** ![Jack\_Muir](https://avatars.discourse-cdn.com/v4/letter/j/b77776/32.png) [@Jack\_Muir](https://discourse.julialang.org/u/Jack_Muir)\
**Post date:** [May 2, 2018, 2:29am UTC](https://discourse.julialang.org/t/binary-minheap-using-locally-defined-isless/10644/4 "2018-05-02T02:29:02Z")

</div>

Thanks, that simplifies things considerably…

---

<div class="post-metadata">

**Author:** ![jlperla](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlperla/32/34332_2.png) [@jlperla](https://discourse.julialang.org/u/jlperla)\
**Post date:** [May 2, 2018, 4:06am UTC](https://discourse.julialang.org/t/binary-minheap-using-locally-defined-isless/10644/5 "2018-05-02T04:06:23Z")

</div>

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?](https://discourse.julialang.org/t/function-name-conflict-adl-function-merging/10335))

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [May 2, 2018, 3:03pm UTC](https://discourse.julialang.org/t/binary-minheap-using-locally-defined-isless/10644/6 "2018-05-02T15:03:08Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![jlperla](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlperla/32/34332_2.png) [@jlperla](https://discourse.julialang.org/u/jlperla)\
**Post date:** [May 2, 2018, 4:28pm UTC](https://discourse.julialang.org/t/binary-minheap-using-locally-defined-isless/10644/7 "2018-05-02T16:28:24Z")

</div>

> [@rdeits](#):
>
> 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.

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.

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [May 2, 2018, 5:58pm UTC](https://discourse.julialang.org/t/binary-minheap-using-locally-defined-isless/10644/8 "2018-05-02T17:58:27Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [May 2, 2018, 6:11pm UTC](https://discourse.julialang.org/t/binary-minheap-using-locally-defined-isless/10644/9 "2018-05-02T18:11:51Z")

</div>

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”).