module Data.OrdList
( member, memberBy, has, hasBy
, isSorted, isSortedBy
, insertBag, insertBagBy
, insertSet, insertSetBy
, isect, isectBy
, union, unionBy
, minus, minusBy
, xunion, xunionBy
, merge, mergeBy
, subset, subsetBy
, sort, sortBy
, sortOn, sortOn'
, nubSort, nubSortBy
, nubSortOn, nubSortOn'
, nub, nubBy
) where
import Data.List(sort,sortBy)
isSorted :: (Ord a) => [a] -> Bool
isSorted = isSortedBy (<=)
isSortedBy :: (a -> a -> Bool) -> [a] -> Bool
isSortedBy lte = loop
where
loop [] = True
loop [_] = True
loop (x:y:zs) = (x `lte` y) && loop (y:zs)
member :: (Ord a) => a -> [a] -> Bool
member = memberBy compare
memberBy :: (a -> a -> Ordering) -> a -> [a] -> Bool
memberBy cmp x = loop
where
loop [] = False
loop (y:ys) = case cmp x y of
LT -> False
EQ -> True
GT -> loop ys
has :: (Ord a) => [a] -> a -> Bool
has xs y = memberBy compare y xs
hasBy :: (a -> a -> Ordering) -> [a] -> a -> Bool
hasBy cmp xs y = memberBy cmp y xs
insertBag :: (Ord a) => a -> [a] -> [a]
insertBag = insertBagBy compare
insertBagBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
insertBagBy cmp = loop
where
loop x [] = [x]
loop x (y:ys)
= case cmp x y of
LT -> y:loop x ys
_ -> x:y:ys
insertSet :: (Ord a) => a -> [a] -> [a]
insertSet = insertSetBy compare
insertSetBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
insertSetBy cmp = loop
where
loop x [] = [x]
loop x (y:ys) = case cmp x y of
LT -> y:loop x ys
EQ -> y:ys
GT -> x:y:ys
isect :: (Ord a) => [a] -> [a] -> [a]
isect = isectBy compare
isectBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
isectBy cmp = loop
where
loop [] _ys = []
loop _xs [] = []
loop (x:xs) (y:ys)
= case cmp x y of
LT -> loop xs (y:ys)
EQ -> x : loop xs ys
GT -> loop (x:xs) ys
union :: (Ord a) => [a] -> [a] -> [a]
union = unionBy compare
unionBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
unionBy cmp = loop
where
loop [] ys = ys
loop xs [] = xs
loop (x:xs) (y:ys)
= case cmp x y of
LT -> x : loop xs (y:ys)
EQ -> x : loop xs ys
GT -> y : loop (x:xs) ys
minus :: (Ord a) => [a] -> [a] -> [a]
minus = minusBy compare
minusBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
minusBy cmp = loop
where
loop [] _ys = []
loop xs [] = xs
loop (x:xs) (y:ys)
= case cmp x y of
LT -> x : loop xs (y:ys)
EQ -> loop xs ys
GT -> loop (x:xs) ys
xunion :: (Ord a) => [a] -> [a] -> [a]
xunion = xunionBy compare
xunionBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
xunionBy cmp = loop
where
loop [] ys = ys
loop xs [] = xs
loop (x:xs) (y:ys)
= case cmp x y of
LT -> x : loop xs (y:ys)
EQ -> loop xs ys
GT -> y : loop (x:xs) ys
merge :: (Ord a) => [a] -> [a] -> [a]
merge = mergeBy compare
mergeBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
mergeBy cmp = loop
where
loop [] ys = ys
loop xs [] = xs
loop (x:xs) (y:ys)
= case cmp x y of
GT -> y : loop (x:xs) ys
_ -> x : loop xs (y:ys)
subset :: (Ord a) => [a] -> [a] -> Bool
subset = subsetBy compare
subsetBy :: (a -> a -> Ordering) -> [a] -> [a] -> Bool
subsetBy cmp = loop
where
loop [] _ys = True
loop _xs [] = False
loop (x:xs) (y:ys)
= case cmp x y of
LT -> False
EQ -> loop xs ys
GT -> loop (x:xs) ys
sortOn :: Ord b => (a -> b) -> [a] -> [a]
sortOn f = map snd . sortOn' fst . map (\x -> (f x, x))
sortOn' :: Ord b => (a -> b) -> [a] -> [a]
sortOn' f = sortBy (\x y -> compare (f x) (f y))
nubSort :: Ord a => [a] -> [a]
nubSort = nubSortBy compare
nubSortBy :: (a -> a -> Ordering) -> [a] -> [a]
nubSortBy cmp = loop . map (\x -> [x])
where
loop [] = []
loop [xs] = xs
loop xss = loop (union_pairs xss)
union_pairs [] = []
union_pairs [xs] = [xs]
union_pairs (xs:ys:xss) = unionBy cmp xs ys : union_pairs xss
nubSortOn :: Ord b => (a -> b) -> [a] -> [a]
nubSortOn f = map snd . nubSortOn' fst . map (\x -> (f x, x))
nubSortOn' :: Ord b => (a -> b) -> [a] -> [a]
nubSortOn' f = nubSortBy (\x y -> compare (f x) (f y))
nub :: (Ord a) => [a] -> [a]
nub = nubBy (>)
nubBy :: (a -> a -> Bool) -> [a] -> [a]
nubBy p xs = case xs of
[] -> []
(x:xs') -> x : loop x xs'
where
loop _ [] = []
loop x (y:ys)
| p x y = loop x ys
| otherwise = y : loop y ys