add maximumWith and minimumWith

[rlefevre]

As Core List has sortWith and sortBy and list-extra maximumBy and minimumBy, I thought it could be relevant to add those (I needed a maximum function with a custom comparison function in my app).

Note that similar functions already exist in NoRedInk/elm-compare (in 0.18 only for now), so this may be the reason why they were not in list-extra. They are however more difficult to find because of the Comparator alias, and they do not return the first maximum/minimum element but the last: https://package.elm-lang.org/packages/NoRedInk/elm-compare/latest/Compare#maximum

[Chadtech]

What did you use maximumWith for in your app? Im trying to picture the use case right now where you need to get the maximum by some comparison and Order. I guess any comparison that doesnt just come down to single comparable values? Still tho, could you provide a concrete use case for maximumWith.

Also, maybe theres a better name than maximumWith? To me, the With part doesnt really convey the the fact that it works by explicit comparison using a a -> a -> Order. Maybe we could get away with just maximum like the NoRedInk package? What do you think?

[rlefevre]

elm/core List has:

sort : List comparable -> List comparable
sortBy : (a -> comparable) -> List a -> List a
sortWith : (a -> a -> Order) -> List a -> List a

and

maximum : List comparable -> Maybe comparable

and List.Extra has:

maximumBy : (a -> comparable) -> List a -> Maybe a

so:

maximumWith: (a -> a -> Order) -> List a -> Maybe a

seemed to fit, but I get your point about With. However I don't like maximum as it is already in Core and I think it is better to not have conflicts with core List as this allows to do import List.Extra as List. More explicit names could be maximumComparingBy and maximumComparingWith, but given the sortBy and sortWith from core, I'm not convinced that this is necessary.

Concerning the use case, I use it to get the maximum from a List (Maybe Int) where Nothing is actually the maximum value (like Infinity). As Infinity is not directly usable (unless by using the hack 1/0), it is not easy to find a function Maybe Int -> comparable in this case, so maximumBy cannot be easily used. Therefore I think that the function is indeed useful for all custom types that cannot be represented easily by a comparable.

[Chadtech]

That makes sense about the naming. A lot of times it just feels like none of the names are good, at the very least we can be consistent with List.sortWith. Maybe this is one of those times.

So what do you do to compare Maybe Int? Do you do something like 'if its Infinity return LT'? How does it work in your project? I just have no idea. After you sort the Maybe Int do you use the Nothings still?

[rlefevre]

So what do you do to compare Maybe Int?

It have this:

compareMaybesWithNothingAsMax : Maybe comparable -> Maybe comparable -> Order
compareMaybesWithNothingAsMax maybe1 maybe2 =
    case ( maybe1, maybe2 ) of
        ( Just be1, Just be2 ) ->
            compare be1 be2

        ( Nothing, Just _ ) ->
            GT

        ( Just _, Nothing ) ->
            LT

        ( Nothing, Nothing ) ->
            EQ

and implemented maximumWith

[pzp1997]

I feel like you could do that just as cleanly with the following:

maximumWithNothingAsInfinity : List (Maybe comparable) -> Maybe comparable
maximumWithNothingAsInfinity list =
    if List.member Nothing list then
        Nothing

    else
        List.maximum (List.filterMap identity list)

(See https://ellie-app.com/3bW9vNzH4SSa1 if you want to play around with it.) That is not to say that there are no valid use cases for maximumWith; I am just not sure that this is one of them.

[rlefevre]

Fair enough. This requires to go through the list three times if Nothing is not a member though (one for member, one for filterMap and one for maximum).

[Chadtech]

How do you end up using Nothing to represent Infinity to begin with? It sounds like you are doing that deliberately, so I am wondering what your project is that would lead you to doing that. Where are your numbers coming from (if you dont mind me asking)?

Also I think I am a bit confused. So in your project, suppose you have a list [ Nothing, Just 1 ], are you intending the return value to be Just Nothing or Just (Just 1)? Are you making it Nothing so that it wont be used as the maximum?

[rlefevre]

Well, this may become embarrassing because I actually use it for a quite obscure and specific other List function that I gave not much though about, but needed, so it can most likely be improved, but anyway:

listFindDiffIndex : List a -> List a -> Maybe Int
listFindDiffIndex source target =
    listFindDiffIndexHelper 0 source target

listFindDiffIndexHelper : Int -> List a -> List a -> Maybe Int
listFindDiffIndexHelper idx source target =
    case ( source, target ) of
        ( s :: ss, t :: tt ) ->
            if s == t then
                listFindDiffIndexHelper (idx + 1) ss tt

            else
                Just idx

        ( [], t :: tt ) ->
            Just idx

        _ ->
            Nothing

This function gives the index of the first element in the lists that differs, or Nothing if the second list ends before any difference is found:

listFindDiffIndex [1,2,3] [1,2,3] == Nothing
listFindDiffIndex [1,2,3] [3,2,1] = Just 0
listFindDIffIndex [1,2,3] [1,3,2] = Just 1
listFindDiffIndex [1,2,3] [1,2] == Nothing
listFindDiffIndex [1,2,3] [1,2,3,4] == Just 3

I could have made a custom type to differentiate the case where the lists are equal but it was not needed for my use case, so I just used a Maybe (I think that I would still have needed the maximumWith function anyway).

But then I need the same but between one list and a list of lists. The returned index is the maximum one found, and as you can guess, Nothing being the "maximum":

istFindMaxDiffIndex : List a -> List (List a) -> Maybe Int
listFindMaxDiffIndex source targets =
    List.map (listFindDiffIndex source) targets
        |> maximumWith compareMaybesWithNothingAsMax
        |> Maybe.withDefault Nothing

Example:

listFindMaxDiffIndex [1,2,3] [[1,2,3],[3,2,1],[1,3,2],[1,2]] == Nothing
listFindMaxDiffIndex [1,2,3] [[3,2,1],[1,3,2],[1,2,3,4]] == Just 1

I'm not sure that this will help in this discussion though :sweat_smile:

[rlefevre]

Maybe a better example would be an imaginary card game where a Jocker scores 0 point but beats all other cards:

module Card exposing (Card(..), compare, maximum, score)

type Card
    = As
    | King
    | Queen
    | Jack
    | Ten
    | Nine
    | Eight
    | Seven
    | Jocker

score : Card -> Int
score card =
    case card of
        As ->
            14

        King ->
            13

        Queen ->
            12

        Jack ->
            11

        Ten ->
            10

        Nine ->
            9

        Eight ->
            8

        Seven ->
            7

        Jocker ->
            0

compare : Card -> Card -> Order
compare card1 card2 =
    case ( card1, card2 ) of
        ( Jocker, Jocker ) ->
            EQ

        ( Jocker, _ ) ->
            GT

        ( _, Jocker ) ->
            LT

        _ ->
            Basics.compare (score card1) (score card2)

maximum : List Card -> Maybe Card
maximum cards =
    maximumWith compare cards

Then

Card.maximum [As, Jocker, Ten] == Just Jocker

[pzp1997]

Yeah, I guess that is pretty reasonable. Would you mind benchmarking your implementation against the following implementation? My guess is that inlining the accumulation function will speed things up.

maximumWith : (a -> a -> Order) -> List a -> Maybe a
maximumWith comparator list =
    List.Extra.foldl1
        (\x y ->
            if comparator x y == GT then
                x

            else
                y
        )
        list

[rlefevre]

We are lucky, elm-explorations/benchmark has just been released for 0.19. But the version with inline accumulation seems actually slower, particularly on firefox:

I used a simple list of numbers:

suite =
    let
        smallList =
            List.repeat 8 42

        mediumList =
            List.repeat 256 42

        bigList =
            List.repeat 4096 42
    in
    describe "List.Extra.maximumWith"
        [ Benchmark.compare "list with 8 elements"
            "PR version"
            (\_ -> List.Extra.maximumWith Basics.compare smallList)
            "With inline accumulation"
            (\_ -> List.Extra.maximumWithInlineAcc Basics.compare smallList)
        ...

[rlefevre]

But it seems to be because of the if/else, because if I rewrite it as:

maximumWithInlineAcc : (a -> a -> Order) -> List a -> Maybe a
maximumWithInlineAcc comparator list =
    foldl1
        (\x y ->
            case comparator x y of
                GT ->
                    x

                _ ->
                    y
        )
        list

it is a lot faster:

[rlefevre]

Previous benchmarks were done without --optimize. When using --optimize, the difference between if...then...else and case...of disappears (case...of is very slightly faster in firefox, and if...then...else in chrome)

So I think I should change the patch to use case...of and inline accumulation, shouldn't I?

[pzp1997]

Yeah, updating the PR to use inline accumulator with case... of seems reasonable to me.

[pzp1997]

Actually, could you run one last benchmark? I wonder if we can improve speed even more by pulling the accumulation function out into it's own top-level definition.

[rlefevre]

I'm not sure to understand all those results and I don't really have time now to look at the generated js, but performance is a lot worse with a top level definition, about -28% on firefox and -50% on chrome...

I tested the following function with --optimize:

maxWith : (a -> a -> Order) -> a -> a -> a
maxWith comparator x y =
    case comparator x y of
        GT ->
            x
        _ ->
            y

maximumWith : (a -> a -> Order) -> List a -> Maybe a
maximumWith comparator list =
    foldl1 (maxWith comparator) list

[pzp1997]

Hmm that's pretty interesting. Let's just go with the inline version then. Don't worry about analyzing the results, most of perf is tough to account for anyway.

[rlefevre]

Ok. I have updated the patch.

[Chadtech]

Okay awesome. I feel good enough about these functions now. Do you all think its ready to merge now?

For me at least, in your card game example, its not clear that your Order implementation is better than just having two separate -> Int functions; one -> Int function for score and one for ranking. But I do see one advantage in the the Order type implementation: it corresponds pretty well with how people actually think of the rules of the game ("Better cards beat worse cards and Jokers beat everything", not "Better cards in a different ranking thats very similar to the point ranking"). Lets provide that advantage.

Also, thats interesting that the case statement is so much faster than the if statement. I wonder why.

[Chadtech]

Okay, if I dont hear otherwise I am going to merge and publish this soon.

Thanks @rlefevre for the contribution.