praxis

Various programming exercises.
git clone git://git.jtobin.io/praxis.git
Log | Files | Refs

Common.hs (814B)

      1 
      2 module Common where
      3 
      4 import Control.Monad
      5 import Data.List
      6 import Data.Map (Map)
      7 import qualified Data.Map as Map
      8 
      9 commons :: Ord a => [[a]] -> [a]
     10 commons = expand . intersection . fmap sparseRepr
     11 
     12 sparseRepr :: Ord a => [a] -> Map a Int
     13 sparseRepr = Map.fromList . fmap labelAndCount . group where
     14   labelAndCount v = (head v, length v)
     15 
     16 intersection :: (Ord k, Ord v) => [Map k v] -> Map k v
     17 intersection [] = Map.empty
     18 intersection (m:ms) = foldl' (Map.intersectionWith min) m ms
     19 
     20 expand :: Map a Int -> [a]
     21 expand = uncurry (flip replicate) <=< Map.toList
     22 
     23 test0 = [1,5,10,20,40,80]
     24 test1 = [6,7,10,20,80,100]
     25 test2 = [3,4,15,20,30,70,80,120]
     26 
     27 test3 = [1,5,5,5]
     28 test4 = [3,4,5,5,10]
     29 test5 = [5,5,10,20]
     30 
     31 main :: IO ()
     32 main = do
     33   print $ commons [test0, test1, test2]
     34   print $ commons [test3, test4, test5]