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))