How to create a function groupBy, which groups elements of a list into tuples of lists and a value based on a function given as input?

Question

I have to implement a method named groupBy which has the following signature: groupBy : (a -> b) -> List a -> List ( b, List a ).

The method takes as input a function and a list of items and returns a list of tuples in the form (b, List a), i.e. it returns some kind of dictionary in which the key is the value b of the function applied to an item a in the input list, and the value is an array of items for which the function applied on has the same value. The function given as a parameter is the criteria by which the elements are grouped by. The following examples should make it more clear.

It should return the following results for the give tests:

• groupBy .x [ { x = 1 } ] --> [(1, [{x = 1}])]
• groupBy (modBy 10) [ 11, 12, 21, 22 ] --> [(1, [11, 21]), (2, [12, 22])]
• groupBy identity [] --> [].

I'm not sure what the 'identity' input means, but I suppose that it is an input for which the method should return the same array which was given as the second parameter.

I've tried the following code and I almost managed to get the result, but I'm stuck and I have no ideas of how I should continue:

groupBy : (a -> b) -> List a -> List ( b, List a )
groupBy criteria list =
    let
        unique lst = 
            List.foldl
                (\a uniques ->
                    if List.member a uniques then
                        uniques
                    else
                        uniques ++ [a]
                )
                [] 
                lst
        keys = 
            list
                |> List.map criteria
                |> unique
        pairs =
            List.map2 Tuple.pair (List.map criteria list) list

        filtered_list =
            List.filterMap (\x -> criteria x == keys) 
        group kl lst =
            case kl of
                [] -> []
                k::ks ->
                    (k, []):: (result els)
    in
        []
    -- Debug.todo "Implement groupBy in Util.elm"

If I run the following code in elm repl: List.map2 Tuple.pair (List.map (modBy 10) [ 11, 12, 21, 22 ]) [ 11, 12, 21, 22 ], then I get the result: [(1,11),(2,12),(1,21),(2,22)]

The unique function returns a list of unique elements (basically a set) given a list which contains duplicates. The pairs function creates tuples of (b, a) form, but I'm trying to get to the form (b, List a). The other two functions don't work, they're just attempts for trying to get to the final form.

[How do I ask and answer homework questions?]

Answer 1

The function already exists in the list-extra package under the name gatherEqualsBy. You can check the implementation there: https://github.com/elm-community/list-extra/blob/8.7.0/src/List/Extra.elm#L2132

You can use https://klaftertief.github.io/elm-search/ to search for signatures: (a -> b) -> List a -> List ( b, List a ) in your case.