Problem 28.b

Sort list of lists by the frequency of the list length.

Solution 1

sortByLengthFrequency : List (List a) -> List (List a)
sortByLengthFrequency xs =
    xs
     |> List.map (\ys -> freq ys xs )
     |> List.sortBy Tuple.first
     |> List.map Tuple.second


freq: List a -> List (List a) -> (Int, List a)
freq xs list =
  ( list 
      |> List.filter (\ys -> List.length ys == List.length xs)
      |> List.length
  , xs
  )

Solution 2

This solution is similar to the first, but replaces the list of length/frequency pairs with a Dict. Lengths are the dictionary keys, and frequencies are the value.

sortByLengthFrequency : List (List a) -> List (List a)
sortByLengthFrequency xs =
    let
        freqs =
            lenFreq xs Dict.empty
    in
        List.sortBy (sortLenFreq freqs) xs


sortLenFreq : Dict.Dict Int Int -> List a -> Int
sortLenFreq lenFreqs xs =
    case Dict.get (List.length xs) lenFreqs of
        -- should never get Nothing
        Nothing ->
            -1

        Just freq ->
            freq


lenFreq : List (List a) -> Dict.Dict Int Int -> Dict.Dict Int Int
lenFreq xs d =
    case xs of
        [] ->
            Dict.empty

        l :: ls ->
            let
                len =
                    List.length l

                ( sameLength, otherLengths ) =
                    List.partition (\x -> List.length x == len) xs

                freq =
                    List.length sameLength
            in
                if List.isEmpty otherLengths then
                    Dict.insert len freq d
                else
                    lenFreq otherLengths (Dict.insert len freq d)

Back to problem