Problem 50a Solutions

Solution 1

Sort the input, then use the pack function from Problem 9, runLengths from Problem 10. Note this requires that the type of the input be a comparable.

freqs : List comparable -> List ( Int, comparable )
freqs list =
    runLengths <| pack <| List.sort list


pack : List a -> List (List a)
pack xs =
    case xs of
        [] ->
            []

        y :: ys ->
            pack_ y [ y ] ys


pack_ : a -> List a -> List a -> List (List a)
pack_ v run xs =
    case xs of
        [] ->
            [ run ]

        y :: ys ->
            if y == v then
                pack_ y (y :: run) ys
            else
                (run) :: pack_ y [ y ] ys



runLengths : List (List a) -> List ( Int, a )
runLengths xss =
    let
        f : List a -> List (Int, a) -> List (Int, a)
        f run runs =
            case List.head run of
                Nothing ->
                    runs

                Just x ->
                    (List.length run, x) :: runs
     in 
            List.foldl f [] xss

Back to problem