Visibility of new methods in a recursive function

Any ideas why this doesn’t work?
The call to StringSorting.quicksort! sees all the methods of keyCompare until the recursive call to quicksort! when it just doesn’t anymore as it seems to call String.keyCompare without the method addition from StringSorting.keyCompare

module Sorting

    Key = Any

    function keyStr end 
    function keyCompare end
    
    function quicksort!(A::Array{Key},i=1,j=length(A)) where {Key}
        @show keyCompare
        @show methods(keyCompare)
        
        if j > i
            pivot = A[rand(i:j)] # random element of A
            left, right = i, j
            while left <= right
                while keyCompare(A[left], pivot) == -1
                    left += 1
                end
                while keyCompare(A[right], pivot) == 1
                    right -= 1
                end
                if left <= right
                    A[left], A[right] = A[right], A[left]
                    left += 1
                    right -= 1
                end
            end
            quicksort!(A,i,right)
            quicksort!(A,left,j)
        end
        return A
    end
    
    export Key, keyStr, keyCompare, quicksort!
    
end
module StringSorting
  
  using Sorting
  
  Key = String
  
  function keyStr(s)::String
    s
  end
  
  function keyCompare(key1::String, key2::String)
    if (key1 < key2) -1 elseif (key1 > key2) 1 else 0 end
  end
  
  export quicksort!, keyCompare, keyStr, Key
end
module Test

import StringSorting

function test()
  A = ["84","77","20","60","47","20","18","97","41","49","31","39","73","68","65","52","1","92","15","9"]
  StringSorting.quicksort!(A)
end

export test

end
1 Like

It doesn’t work because the function keyCompare in Sorting is a completely new definition which shadows the function in Sorting, rather than adding a new method to it. You need to import Sorting.keyCompare or just define your method as function Sorting.keyCompare, as explained in the manual: https://docs.julialang.org/en/v1/manual/modules/#modules-1

Also, I can’t reproduce your result that quicksort! "sees all the methods of keyCompare until the recursive call to quicksort!". In fact, when I run your example I see:

julia> Test.test()
keyCompare = Main.Sorting.keyCompare
methods(keyCompare) = # 0 methods for generic function "keyCompare":
ERROR: MethodError: no method matching keyCompare(::String, ::String)
Stacktrace:
 [1] quicksort!(::Array{String,1}, ::Int64, ::Int64) at ./REPL[1]:16
 [2] quicksort! at ./REPL[1]:9 [inlined]
 [3] test() at ./REPL[3]:7
 [4] top-level scope at REPL[4]:1

i.e. that Sorting.keyCompare has no methods, as expected.

Note that I needed to change to using ..Sorting inside StringSorting and import ..StringSorting in Test, since I defined all of these modules at the REPL.

2 Likes

Thanks! I got it now.