    module Data.List.Key.Private where

    import Data.Function.HT (compose2, )

    import Data.List (nubBy, sortBy, minimumBy, maximumBy, )

    import Prelude hiding (minimum, maximum, )

    attach :: (a -> b) -> [a] -> [(b,a)]
    attach :: forall a b. (a -> b) -> [a] -> [(b, a)]
    attach a -> b
    key = (a -> (b, a)) -> [a] -> [(b, a)]
    forall a b. (a -> b) -> [a] -> [b]
    map (\a
    x -> (a -> b
    key a
    x, a
    x))

    aux ::
       (((key, a) -> (key, a) -> b) -> [(key, a)] -> c) ->
          (key -> key -> b) -> (a -> key) ->
              ([a] -> c)
    aux :: forall key a b c.
    (((key, a) -> (key, a) -> b) -> [(key, a)] -> c)
    -> (key -> key -> b) -> (a -> key) -> [a] -> c
    aux ((key, a) -> (key, a) -> b) -> [(key, a)] -> c
    listFunc key -> key -> b
    cmpFunc a -> key
    key =
       ((key, a) -> (key, a) -> b) -> [(key, a)] -> c
    listFunc ((key -> key -> b) -> ((key, a) -> key) -> (key, a) -> (key, a) -> b
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    compose2 key -> key -> b
    cmpFunc (key, a) -> key
    forall a b. (a, b) -> a
    fst) ([(key, a)] -> c) -> ([a] -> [(key, a)]) -> [a] -> c
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> key) -> [a] -> [(key, a)]
    forall a b. (a -> b) -> [a] -> [(b, a)]
    attach a -> key
    key

    aux' ::
       ((a -> a -> b) -> [a] -> c) ->
          (key -> key -> b) -> (a -> key) ->
              ([a] -> c)
    aux' :: forall a b c key.
    ((a -> a -> b) -> [a] -> c)
    -> (key -> key -> b) -> (a -> key) -> [a] -> c
    aux' (a -> a -> b) -> [a] -> c
    listFunc key -> key -> b
    cmpFunc a -> key
    key =
       (a -> a -> b) -> [a] -> c
    listFunc ((key -> key -> b) -> (a -> key) -> a -> a -> b
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    compose2 key -> key -> b
    cmpFunc a -> key
    key)

    {- |
    Divides a list into sublists such that the members in a sublist
    share the same key.
    It uses semantics of 'Data.List.HT.groupBy',
    not that of 'Data.List.groupBy'.
    -}
    group :: Eq b => (a -> b) -> [a] -> [[a]]
    group :: forall b a. Eq b => (a -> b) -> [a] -> [[a]]
    group a -> b
    key = ([(b, a)] -> [a]) -> [[(b, a)]] -> [[a]]
    forall a b. (a -> b) -> [a] -> [b]
    map (((b, a) -> a) -> [(b, a)] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    map (b, a) -> a
    forall a b. (a, b) -> b
    snd) ([[(b, a)]] -> [[a]]) -> ([a] -> [[(b, a)]]) -> [a] -> [[a]]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (((b, a) -> (b, a) -> Bool) -> [(b, a)] -> [[(b, a)]])
    -> (b -> b -> Bool) -> (a -> b) -> [a] -> [[(b, a)]]
    forall key a b c.
    (((key, a) -> (key, a) -> b) -> [(key, a)] -> c)
    -> (key -> key -> b) -> (a -> key) -> [a] -> c
    aux ((b, a) -> (b, a) -> Bool) -> [(b, a)] -> [[(b, a)]]
    forall a. (a -> a -> Bool) -> [a] -> [[a]]
    groupBy b -> b -> Bool
    forall a. Eq a => a -> a -> Bool
    (==) a -> b
    key

    {- |
    Will be less efficient than 'group'
    if @key@ is computationally expensive.
    This is so because the key is re-evaluated for each list item.
    Alternatively you may write @groupBy ((==) `on` key)@.
    -}
    group' :: Eq b => (a -> b) -> [a] -> [[a]]
    group' :: forall b a. Eq b => (a -> b) -> [a] -> [[a]]
    group'  =  ((a -> a -> Bool) -> [a] -> [[a]])
    -> (b -> b -> Bool) -> (a -> b) -> [a] -> [[a]]
    forall a b c key.
    ((a -> a -> b) -> [a] -> c)
    -> (key -> key -> b) -> (a -> key) -> [a] -> c
    aux' (a -> a -> Bool) -> [a] -> [[a]]
    forall a. (a -> a -> Bool) -> [a] -> [[a]]
    groupBy b -> b -> Bool
    forall a. Eq a => a -> a -> Bool
    (==)

    propGroup :: (Eq a, Eq b) => (a -> b) -> [a] -> Bool
    propGroup :: forall a b. (Eq a, Eq b) => (a -> b) -> [a] -> Bool
    propGroup a -> b
    key [a]
    xs =
       (a -> b) -> [a] -> [[a]]
    forall b a. Eq b => (a -> b) -> [a] -> [[a]]
    group a -> b
    key [a]
    xs [[a]] -> [[a]] -> Bool
    forall a. Eq a => a -> a -> Bool
    == (a -> b) -> [a] -> [[a]]
    forall b a. Eq b => (a -> b) -> [a] -> [[a]]
    group' a -> b
    key [a]
    xs

    {- | argmin -}
    minimum :: Ord b => (a -> b) -> [a] -> a
    minimum :: forall b a. Ord b => (a -> b) -> [a] -> a
    minimum a -> b
    key  =  (b, a) -> a
    forall a b. (a, b) -> b
    snd ((b, a) -> a) -> ([a] -> (b, a)) -> [a] -> a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (((b, a) -> (b, a) -> Ordering) -> [(b, a)] -> (b, a))
    -> (b -> b -> Ordering) -> (a -> b) -> [a] -> (b, a)
    forall key a b c.
    (((key, a) -> (key, a) -> b) -> [(key, a)] -> c)
    -> (key -> key -> b) -> (a -> key) -> [a] -> c
    aux ((b, a) -> (b, a) -> Ordering) -> [(b, a)] -> (b, a)
    forall (t :: * -> *) a.
    Foldable t =>
    (a -> a -> Ordering) -> t a -> a
    minimumBy b -> b -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare a -> b
    key

    {- | argmax -}
    maximum :: Ord b => (a -> b) -> [a] -> a
    maximum :: forall b a. Ord b => (a -> b) -> [a] -> a
    maximum a -> b
    key  =  (b, a) -> a
    forall a b. (a, b) -> b
    snd ((b, a) -> a) -> ([a] -> (b, a)) -> [a] -> a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (((b, a) -> (b, a) -> Ordering) -> [(b, a)] -> (b, a))
    -> (b -> b -> Ordering) -> (a -> b) -> [a] -> (b, a)
    forall key a b c.
    (((key, a) -> (key, a) -> b) -> [(key, a)] -> c)
    -> (key -> key -> b) -> (a -> key) -> [a] -> c
    aux ((b, a) -> (b, a) -> Ordering) -> [(b, a)] -> (b, a)
    forall (t :: * -> *) a.
    Foldable t =>
    (a -> a -> Ordering) -> t a -> a
    maximumBy b -> b -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare a -> b
    key

    sort :: Ord b => (a -> b) -> [a] -> [a]
    sort :: forall b a. Ord b => (a -> b) -> [a] -> [a]
    sort a -> b
    key  =  ((b, a) -> a) -> [(b, a)] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    map (b, a) -> a
    forall a b. (a, b) -> b
    snd ([(b, a)] -> [a]) -> ([a] -> [(b, a)]) -> [a] -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (((b, a) -> (b, a) -> Ordering) -> [(b, a)] -> [(b, a)])
    -> (b -> b -> Ordering) -> (a -> b) -> [a] -> [(b, a)]
    forall key a b c.
    (((key, a) -> (key, a) -> b) -> [(key, a)] -> c)
    -> (key -> key -> b) -> (a -> key) -> [a] -> c
    aux ((b, a) -> (b, a) -> Ordering) -> [(b, a)] -> [(b, a)]
    forall a. (a -> a -> Ordering) -> [a] -> [a]
    sortBy b -> b -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare a -> b
    key

    merge :: Ord b => (a -> b) -> [a] -> [a] -> [a]
    merge :: forall b a. Ord b => (a -> b) -> [a] -> [a] -> [a]
    merge a -> b
    key [a]
    xs [a]
    ys  =
       ((b, a) -> a) -> [(b, a)] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    map (b, a) -> a
    forall a b. (a, b) -> b
    snd ([(b, a)] -> [a]) -> [(b, a)] -> [a]
    forall a b. (a -> b) -> a -> b
    $
       ((b, a) -> (b, a) -> Bool) -> [(b, a)] -> [(b, a)] -> [(b, a)]
    forall a. (a -> a -> Bool) -> [a] -> [a] -> [a]
    mergeBy
          ((b -> b -> Bool) -> ((b, a) -> b) -> (b, a) -> (b, a) -> Bool
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    compose2 b -> b -> Bool
    forall a. Ord a => a -> a -> Bool
    (<=) (b, a) -> b
    forall a b. (a, b) -> a
    fst)
          ((a -> b) -> [a] -> [(b, a)]
    forall a b. (a -> b) -> [a] -> [(b, a)]
    attach a -> b
    key [a]
    xs) ((a -> b) -> [a] -> [(b, a)]
    forall a b. (a -> b) -> [a] -> [(b, a)]
    attach a -> b
    key [a]
    ys)

    nub :: Eq b => (a -> b) -> [a] -> [a]
    nub :: forall b a. Eq b => (a -> b) -> [a] -> [a]
    nub a -> b
    key  =  ((b, a) -> a) -> [(b, a)] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    map (b, a) -> a
    forall a b. (a, b) -> b
    snd ([(b, a)] -> [a]) -> ([a] -> [(b, a)]) -> [a] -> [a]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (((b, a) -> (b, a) -> Bool) -> [(b, a)] -> [(b, a)])
    -> (b -> b -> Bool) -> (a -> b) -> [a] -> [(b, a)]
    forall key a b c.
    (((key, a) -> (key, a) -> b) -> [(key, a)] -> c)
    -> (key -> key -> b) -> (a -> key) -> [a] -> c
    aux ((b, a) -> (b, a) -> Bool) -> [(b, a)] -> [(b, a)]
    forall a. (a -> a -> Bool) -> [a] -> [a]
    nubBy b -> b -> Bool
    forall a. Eq a => a -> a -> Bool
    (==) a -> b
    key

    -- * helper functions

    groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
    groupBy :: forall a. (a -> a -> Bool) -> [a] -> [[a]]
    groupBy a -> a -> Bool
    p = ((a, [a]) -> [a]) -> [(a, [a])] -> [[a]]
    forall a b. (a -> b) -> [a] -> [b]
    map ((a -> [a] -> [a]) -> (a, [a]) -> [a]
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry (:)) ([(a, [a])] -> [[a]]) -> ([a] -> [(a, [a])]) -> [a] -> [[a]]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> a -> Bool) -> [a] -> [(a, [a])]
    forall a. (a -> a -> Bool) -> [a] -> [(a, [a])]
    groupByNonEmpty a -> a -> Bool
    p

    groupByNonEmpty :: (a -> a -> Bool) -> [a] -> [(a,[a])]
    groupByNonEmpty :: forall a. (a -> a -> Bool) -> [a] -> [(a, [a])]
    groupByNonEmpty a -> a -> Bool
    p =
       (a -> [(a, [a])] -> [(a, [a])]) -> [(a, [a])] -> [a] -> [(a, [a])]
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr
          (\a
    x0 [(a, [a])]
    yt ->
             let ([a]
    xr,[(a, [a])]
    yr) =
                   case [(a, [a])]
    yt of
                      (a
    x1,[a]
    xs):[(a, [a])]
    ys ->
                         if a -> a -> Bool
    p a
    x0 a
    x1
                           then (a
    x1a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    xs,[(a, [a])]
    ys)
                           else ([],[(a, [a])]
    yt)
                      [] -> ([],[(a, [a])]
    yt)
             in  (a
    x0,[a]
    xr)(a, [a]) -> [(a, [a])] -> [(a, [a])]
    forall a. a -> [a] -> [a]
    :[(a, [a])]
    yr)
          []

    groupByEmpty :: (a -> a -> Bool) -> [a] -> [[a]]
    groupByEmpty :: forall a. (a -> a -> Bool) -> [a] -> [[a]]
    groupByEmpty a -> a -> Bool
    p =
       ([a] -> [[a]] -> [[a]]) -> ([a], [[a]]) -> [[a]]
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry (:) (([a], [[a]]) -> [[a]]) -> ([a] -> ([a], [[a]])) -> [a] -> [[a]]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    .
       (a -> ([a], [[a]]) -> ([a], [[a]]))
    -> ([a], [[a]]) -> [a] -> ([a], [[a]])
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr
          (\a
    x0 ~([a]
    y,[[a]]
    ys) ->
             if (case [a]
    y of a
    x1:[a]
    _ -> a -> a -> Bool
    p a
    x0 a
    x1; [a]
    _ -> Bool
    True)
               then (a
    x0a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    y,[[a]]
    ys)
               else (a
    x0a -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[],[a]
    y[a] -> [[a]] -> [[a]]
    forall a. a -> [a] -> [a]
    :[[a]]
    ys))
          ([],[])

    mergeBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
    mergeBy :: forall a. (a -> a -> Bool) -> [a] -> [a] -> [a]
    mergeBy a -> a -> Bool
    p =
       let recourse :: [a] -> [a] -> [a]
    recourse [] [a]
    yl = [a]
    yl
           recourse [a]
    xl [] = [a]
    xl
           recourse xl :: [a]
    xl@(a
    x:[a]
    xs) yl :: [a]
    yl@(a
    y:[a]
    ys) =
             (a -> [a] -> [a]) -> (a, [a]) -> [a]
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry (:) ((a, [a]) -> [a]) -> (a, [a]) -> [a]
    forall a b. (a -> b) -> a -> b
    $
             if a -> a -> Bool
    p a
    x a
    y
               then (a
    x, [a] -> [a] -> [a]
    recourse [a]
    xs [a]
    yl)
               else (a
    y, [a] -> [a] -> [a]
    recourse [a]
    xl [a]
    ys)
       in  [a] -> [a] -> [a]
    recourse