Currently impossible to implement polymorphic quicksort in Verse?

Development Programming & Scripting Verse
, , ,
1

I tried implementing Quicksort based on a Wikipedia example:

(Array:[]t where t:type).Partition(Low:int, High:int):int=
    if(Pivot := Array[Floor[(High*1.0-Low*1.0)/2.0]+Low]):
        var Left : int = Low-1
        var Right : int = High+1
        loop:
            loop:
                set Left += 1
                if(Array[Left] >= Pivot). break
            loop:
                set Right -= 1
                if(Array[Right] <= Pivot). break
            if(Left>=Right). return Right
            Tmp := Left
            set Left = Right
            set Right = Left
    return 0

(Array:[]t where t:type).Sort(Low:int, High:int):[]t=
    if(Low >= 0 and High >= 0 and Low < High):
        P := Array.Partition(Low, High)
        Array.Sort(Array,Low,P)
        Array.Sort(Array,P+1,High)
    return Array

but it isn’t compiling because it doesn’t know which overload of +, -, > and < to use.

I assume this should be possible in the future as it doesn’t seem that difficult for the compiler to figure out, but it currently seems impossible?

Or does anyone know if there’s a way to work around this issue?

Edit: I realize I really screwed up the algorithm and the code is completely broken, I really should have made a non-polymorphic version and tested it before posting :face_with_diagonal_mouth: But anyways the main issue is still whether there’s a way to get Verse to use the correct overloads currently

Edit: Here’s a working non-polymorphic version:

int_array_ref := class<unique>:
    var Data : []int = array{}
        
(Array:int_array_ref).Partition(Low:int, High:int):int=
    if(Pivot := Array.Data[Floor[(High*1.0-Low*1.0)/2.0]+Low]):
        var Left : int = Low-1
        var Right : int = High+1
        loop:
            loop:
                set Left += 1
                if(Array.Data[Left]>=Pivot). break
            loop:
                set Right -= 1
                if(Array.Data[Right]<=Pivot). break
            if(Left >= Right). return Right
            if(Tmp := Array.Data[Left]):
                if(set Array.Data[Left] = Array.Data[Right]){}
                if(set Array.Data[Right] = Tmp){}
    return 0

(Array:int_array_ref).Sort(Low:int, High:int):void=
    if(Low >= 0 and High >= 0 and Low < High):
        P := Array.Partition(Low, High)
        Array.Sort(Low,P)
        Array.Sort(P+1,High)
2

You wrote that beautifully, but we haven’t built the features needed to support this yet. We need something resembling C# type constraints ( where (generic type constraint) - C# Reference | Microsoft Learn), Rust traits, or Haskell typeclasses in order to express the constraint that “t is required to be some type supporting ordered comparison”.

3 Likes
3

Here is a quick sort implementation I made with the help of ChatGPT and how other languages implement it, adapted to Verse.
It’s slightly different from yours in that it uses a custom comparison function to sort the data.

(Input:[]t where t:type).QuickSort<public>(CompareFunction(Element1:t, Element2:t):int):[]t = 

    if (Input.Length <= 1):
        return Input

    var Less : []t = array {}
    var Equal : []t = array {}
    var Greater : []t = array {}

    if (Pivot := Input[Int[Input.Length * 0.5]]):
        for (Element : Input):
            Result := CompareFunction(Element, Pivot)
            ArrayElement := array { Element }
            if (Result < 0):
                set Less += ArrayElement
            else if (Result > 0):
                set Greater += ArrayElement
            else:
                set Equal += ArrayElement

    Less.QuickSort(CompareFunction) + Equal + Greater.QuickSort(CompareFunction)

Usage: Having the following array of integers…

IntArray : []int = array { 3, 4, 1, 0, -6, 10, 1 }

you define a comparison function for integers:

# The comparison function should return:
#   -1 if Element1 should go before Element2
#    0 if Element1 and Element2 are equal
#    1 if Element1 should go after Element2
SortFunction(Element1: int, Element2: int): int =
    if (Element1 > Element2):
        1
    else if (Element1 < Element2):
        -1
    else:
        0

Then you call the QuickSort method passing the custom comparision function:

SortedArray := IntArray.Sort(SortFunction)

This way you can also sort any kind of complex data, not just integers, by providing an appropriate comparison function.

5 Likes
4

Beautiful! And your approach works for writing a sort function to sort ascending or descending, sort structures based on field comparisons in some order, and so on.

4 Likes