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