--
-- Frequency.hs
--
--------------------------------------------------------------------------------

module Frequency ( frequency ) where


mergeSort :: ([t] -> [t] -> [t]) -> [t] -> [t]
mergeSort merge liste | laenge < 2 = liste
                      | otherwise  = merge (mergeSort merge l) (mergeSort merge r)
  where (l, r) = splitAt mitte liste
        mitte  = laenge `div` 2
        laenge = length liste


sortFold :: [(Char, Int)] -> [(Char, Int)]
sortFold = mergeSort sfMerge

sfMerge :: [(Char, Int)] -> [(Char, Int)] -> [(Char, Int)]
sfMerge []                    r                    = r
sfMerge l                     []                   = l
sfMerge ll@((c1, h1) : rest1) lr@((c2, h2) : rest2)
  | c1 == c2 = (c1, h1+h2) : sfMerge rest1 rest2
  | c1 < c2  = (c1, h1)    : sfMerge rest1 lr
  | c1 > c2  = (c2, h2)    : sfMerge ll    rest2

testSF = sortFold [('c',2), ('d',1), ('a',4), ('d',2), ('c',5)]


frequency :: [Char] -> [(Char, Int)]
frequency = mergeSort freqMerge . mergeSort sfMerge . map (\x -> (x,1))
  where freqMerge l                     []                    = l
        freqMerge []                    r                     = r
        freqMerge ll@((c1, h1) : rest1) lr@((c2, h2) : rest2)
          | h1 < h2 || (h1 == h2 && c1 < c2) = (c1, h1) : freqMerge rest1 lr
          | otherwise                        = (c2, h2) : freqMerge ll    rest2