-- Mouad NACIRI
-- Master IAO
-- TP1: Les n mots les plus fréquents 

import Data.Char as Char

nCommonWords :: Int -> String -> [(String, Int)]
nCommonWords _ [] = []
nCommonWords n s = take n . qSort' . compress . qSort . words $ s

words' :: String -> [String]
words' [] = []
words' xs = let (w, rest) = break Char.isSpace xs in w : (words' . dropWhile Char.isSpace $ rest)

qSort :: (Ord a) => [a] -> [a]
qSort [] = []
qSort (x:xs) = (qSort . filter (<x) $ xs) ++ x : (qSort . filter (>=x) $ xs)

compress :: [String] -> [(String, Int)]
compress [] = []
compress (x:xs) = let (y,ys) = span (==x) xs in (x, length y + 1) : compress ys

qSort' :: (Ord a, Ord b) => [(a,b)] -> [(a,b)]
qSort' [] = []
qSort' ((x,y):xs) = (qSort' . filter (\z -> snd z >= y) $ xs) ++ (x,y) : (qSort' . filter (\z -> snd z < y) $ xs)

