SortByDescending

Sep 15, 2014 at 6:56 PM
Hi,

I'm working on the SortDescending and SortByDescending for Arrays, Lists and Sequences.
See the table here:
https://github.com/fsharp/FSharpLangDesign/blob/master/CoreLibraryFunctions.md

I want to open up what I've been doing for discussion. For the Array SortDescending, I simply took the existing Sort method and replaced
sortInPlace result;
with
sortInPlaceWith (fun a b -> compare b a) result;
For SortDescendingBy there is no easy equivalent SortBy uses
sortInPlaceBy f result;
So short of perhaps writing a 'sortInPlaceByWith' function, I need to find an althernative. For now just to make the test pass and make sure everything is hanging together I'm just doing an Array.Reverse inside SortDescendingBy, I don't think that's going to be acceptable.

That's my first issue.

My second, which maybe deserves a separate thread relates to Lists and Seqs, the sort on those needs to be stable, but what does that mean in a SortDescending scenario? Should SortDescending be the reverse of Sort? If so, should same items be swapped for SortDescending?

My gut says no, but I'll throw it out for discussion.

My code so far is here:
https://git01.codeplex.com/forks/richardadalton/sortdescending

Thanks.

-Richard
Sep 16, 2014 at 5:07 PM
For your first issue, sortDescendingBy is simply
sortInPlaceWith (fun a b -> compare (f b) (f a)) result
For the second issue, consider sorting names by LastName descending then by FirstName descending.

In this case you would first sort by FirstName descending, then sort the resulting list by LastName descending, but when 2 people have the the same LastName you want to keep them in the same order. I.e. for both ascending and descending stable sorts, when the keys evaluate to equal, they stay in the same order.
Sep 17, 2014 at 12:07 PM
Good spot on the SortDescendingBy. I've made that change.
Sep 17, 2014 at 1:00 PM
So, now for Lists and Sequences I want the sort to be stable,

For Lists there's an existing sortWith which is stable so I can use that for both functions
        [<CompiledName("SortByDescending")>]
        let sortByDescending f xs =
           sortWith  (fun a b -> compare (f b) (f a)) xs
 
        [<CompiledName("SortDescending")>]
        let sortDescending xs =
            sortWith  (fun a b -> compare b a) xs
It looks like sortWith isn't implemented yet for Seq. Looking at the table it seems it's being worked on.
https://github.com/fsharp/FSharpLangDesign/blob/master/CoreLibraryFunctions.md
Sep 17, 2014 at 1:44 PM
I added some unit tests sorting Tuples to test the stable sort. It works for sortDescending, but if I sortDescengingBy snd, I get issues.

``` let tupArr = [(2,"a");(1,"d");(1,"b");(1,"a");(2,"x");(2,"b");(1,"x")]
let resultTup = List.sortByDescending snd tupArr

`` I expect the Tuples to be ordered by the second element descending, and within that I expect the first elements to remain in the same order as they appear in the original list.
Expected: [(2,"x");(1,"x");(1,"d");(1,"b");(2,"b");(2,"a");(1,"a")]

Note that pairs where the second element match are reversed when compared to the original list.
Actual: [(1,"x");(2,"x");(1,"d");(2,"b");(1,"b");(1,"a");(2,"a")]

I've added those tests for Sort and SortBy as well. They work for those as you'd expect.
Sep 17, 2014 at 5:07 PM
Those tests pass fine for me, using the latest version from your fork
Sep 17, 2014 at 5:09 PM
For the stable Seq sortWith, can you use List.sortWith and change over to use Seq.sortWith after all the commits have been merged?
Sep 17, 2014 at 8:04 PM
Edited Sep 18, 2014 at 7:27 AM
There should be a SortByDescending test in ListModule2.fs that fails.

I could use List.sortWith if that's acceptable. Is Seq.sortWith definitly being worked on?

Maybe I should strip out the Seq methods and just issue a PR for Arrays and Lists until the Seq.sortWith commits have been merged.

I see even the implementation of List.sortWith is up for question. It uses the StableSortImplementation module which has this comment
// NOTE: This implementation is now only used for List.sortWith. We should change that to use the stable sort via arrays
// below, and remove this implementation.
Sep 17, 2014 at 11:34 PM
I would suggest getting it working and creating the pull request, then it can be reviewed and maybe marked for update after the merge.

I had a go at a solution using List.sortWith
    [<CompiledName("SortByDescending")>]
    let sortByDescending keyf source =
        checkNonNull "source" source
        mkDelayedSeq (fun () -> source |> toList |> List.sortWith (fun a b -> compare (keyf b) (keyf a)) :> seq<_>)

    [<CompiledName("SortDescending")>]
    let sortDescending source =
        checkNonNull "source" source
        mkDelayedSeq (fun () -> source |> toList |> List.sortWith (fun a b -> compare b a) :> seq<_>)
Your List tests are still passing on my machine, but one of your ArrayModule2 tests is failing, you have an extra Array.reverse in your Array.sortbyDescending method
Sep 18, 2014 at 12:29 AM
Gah! I know what's happened.
Forgot to run update.cmd debug -ngen before running the tests.

All fixed now, and Seq sorts are implemended using List.sortWith.
Issuing the Pull Request now.