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 = 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 (forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
compose2 key -> key -> b
cmpFunc forall a b. (a, b) -> a
fst) forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 (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 = forall a b. (a -> b) -> [a] -> [b]
map (forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> b
snd) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall key a b c.
(((key, a) -> (key, a) -> b) -> [(key, a)] -> c)
-> (key -> key -> b) -> (a -> key) -> [a] -> c
aux forall a. (a -> a -> Bool) -> [a] -> [[a]]
groupBy 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'  =  forall a b c key.
((a -> a -> b) -> [a] -> c)
-> (key -> key -> b) -> (a -> key) -> [a] -> c
aux' forall a. (a -> a -> Bool) -> [a] -> [[a]]
groupBy 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 =
   forall b a. Eq b => (a -> b) -> [a] -> [[a]]
group a -> b
key [a]
xs forall a. Eq a => a -> a -> Bool
== 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  =  forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall key a b c.
(((key, a) -> (key, a) -> b) -> [(key, a)] -> c)
-> (key -> key -> b) -> (a -> key) -> [a] -> c
aux forall (t :: * -> *) a.
Foldable t =>
(a -> a -> Ordering) -> t a -> a
minimumBy 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  =  forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall key a b c.
(((key, a) -> (key, a) -> b) -> [(key, a)] -> c)
-> (key -> key -> b) -> (a -> key) -> [a] -> c
aux forall (t :: * -> *) a.
Foldable t =>
(a -> a -> Ordering) -> t a -> a
maximumBy 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  =  forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall key a b c.
(((key, a) -> (key, a) -> b) -> [(key, a)] -> c)
-> (key -> key -> b) -> (a -> key) -> [a] -> c
aux forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy 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  =
   forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> b
snd forall a b. (a -> b) -> a -> b
$
   forall a. (a -> a -> Bool) -> [a] -> [a] -> [a]
mergeBy
      (forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
compose2 forall a. Ord a => a -> a -> Bool
(<=) forall a b. (a, b) -> a
fst)
      (forall a b. (a -> b) -> [a] -> [(b, a)]
attach a -> b
key [a]
xs) (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  =  forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall key a b c.
(((key, a) -> (key, a) -> b) -> [(key, a)] -> c)
-> (key -> key -> b) -> (a -> key) -> [a] -> c
aux forall a. (a -> a -> Bool) -> [a] -> [a]
nubBy 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 = forall a b. (a -> b) -> [a] -> [b]
map (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (:)) forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 =
   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
x1forall a. a -> [a] -> [a]
:[a]
xs,[(a, [a])]
ys)
                       else ([],[(a, [a])]
yt)
                  [] -> ([],[(a, [a])]
yt)
         in  (a
x0,[a]
xr)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 =
   forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (:) forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   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
x0forall a. a -> [a] -> [a]
:[a]
y,[[a]]
ys)
           else (a
x0forall a. a -> [a] -> [a]
:[],[a]
yforall 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) =
         forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (:) 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