import Data.Monoid import Data.Foldable (foldMap) import Control.Arrow type Pattern = String type Weight = Int type Cluster = [(Pattern, Weight)] clusters :: [Cluster] clusters = [ [("a1", 1), ("a2", 2), ("a3", 3)] , [("b1", 4), ("b2", 5)] , [("c1", 7), ("c2", 8), ("c3", 9)] , [("d1", 10), ("d2", 11), ("d3", 12)] ] allCombs :: [a] -> [[[a]]] allCombs [] = [[[]]] allCombs (x:xs) = zipWith (++) ([] : map (map (x:)) next) (next ++ [[]]) where next = allCombs xs mixClusters :: [Cluster] -> Cluster mixClusters = map (second getSum . foldMap (second Sum)) . sequence mixAllClusters :: [Cluster] -> Cluster mixAllClusters = concatMap mixClusters . concat . tail . allCombs main = mapM_ print $ mixAllClusters clusters