Visibility of new methods in a recursive function

General Usage
1

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
2

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: Modules · The Julia Language

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
3

Thanks! I got it now.