module Data.Map ( groupBy , sortByKey , Map ) where import Data.List (sortBy) type Map k v = [(k, v)] groupBy :: (Ord k, Eq k) => (v -> k) -> [v] -> Map k [v] groupBy :: (v -> k) -> [v] -> Map k [v] groupBy v -> k f [v] vs = ((k, [v]) -> (k, [v]) -> Ordering) -> Map k [v] -> Map k [v] forall a. (a -> a -> Ordering) -> [a] -> [a] sortBy (\(k k1, [v] _) (k k2, [v] _) -> k -> k -> Ordering forall a. Ord a => a -> a -> Ordering compare k k1 k k2) (Map k [v] -> Map k [v]) -> Map k [v] -> Map k [v] forall a b. (a -> b) -> a -> b $ (v -> k) -> ([v], Map k [v]) -> Map k [v] forall k v. Eq k => (v -> k) -> ([v], Map k [v]) -> Map k [v] go v -> k f ([v] vs, []) where go :: Eq k => (v -> k) -> ([v], Map k [v]) -> Map k [v] go :: (v -> k) -> ([v], Map k [v]) -> Map k [v] go v -> k _ ([], Map k [v] vs) = Map k [v] vs go v -> k f (v v : [v] vs, Map k [v] acc) = let append :: a -> a -> (a, [a]) -> (a, [a]) append a key a value (a k, [a] v) = if a key a -> a -> Bool forall a. Eq a => a -> a -> Bool == a k then (a k, a value a -> [a] -> [a] forall a. a -> [a] -> [a] : [a] v) else (a k, [a] v) acc' :: Map k [v] acc' = if ((k, [v]) -> Bool) -> Map k [v] -> Bool forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool any (\(k k', [v] _) -> k k' k -> k -> Bool forall a. Eq a => a -> a -> Bool == v -> k f v v) Map k [v] acc then ((k, [v]) -> (k, [v])) -> Map k [v] -> Map k [v] forall a b. (a -> b) -> [a] -> [b] map (k -> v -> (k, [v]) -> (k, [v]) forall a a. Eq a => a -> a -> (a, [a]) -> (a, [a]) append (v -> k f v v) v v) Map k [v] acc else (v -> k f v v, [v v]) (k, [v]) -> Map k [v] -> Map k [v] forall a. a -> [a] -> [a] : Map k [v] acc in (v -> k) -> ([v], Map k [v]) -> Map k [v] forall k v. Eq k => (v -> k) -> ([v], Map k [v]) -> Map k [v] go v -> k f ([v] vs, Map k [v] acc') sortByKey :: (Ord k) => Map k v -> Map k v sortByKey :: Map k v -> Map k v sortByKey = ((k, v) -> (k, v) -> Ordering) -> Map k v -> Map k v forall a. (a -> a -> Ordering) -> [a] -> [a] sortBy (\(k, v) a (k, v) b -> k -> k -> Ordering forall a. Ord a => a -> a -> Ordering compare ((k, v) -> k forall a b. (a, b) -> a fst (k, v) a) ((k, v) -> k forall a b. (a, b) -> a fst (k, v) b))