-------------------------------------------------------------------
--
-- Modul Frequency (Lösung zu Aufgabe 16, Blatt 7)
--
-------------------------------------------------------------------
module Frequency where
import Data.Char

-------------------------------------------------------------------
-- (a) Mischsortieren mit Mischfunktion als Parameter
mergeSort :: ([t] -> [t] -> [t]) -> [t] -> [t]
mergeSort merge liste
  | laenge < 2 = liste
  | otherwise  = merge (mergeSort merge l) (mergeSort merge r)
  where (l, r) = split liste
        laenge = length liste

split          :: [a] -> ([a],[a])
-- split zerlegt eine Liste in zwei Teillisten
split []       =  ([],[])
split [x]      =  ([x],[])
split (x:y:ys) =  (x:l1,y:l2)
                  where (l1,l2) = split ys

-- (b)
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)]

-- (c) Buchstabenhaeufigkeit in einem Text bestimmen
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