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 :: (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 :: (((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' :: ((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 :: (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' :: (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 :: (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 :: (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 :: (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 :: (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 :: (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 :: (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 :: (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 :: (a -> a -> Bool) -> [a] -> [(a, [a])]
groupByNonEmpty a -> a -> Bool
p =
   (a -> [(a, [a])] -> [(a, [a])]) -> [(a, [a])] -> [a] -> [(a, [a])]
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
                  (x1,xs):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 :: (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 (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 :: (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