module Data.List.Util (
hasSubset
, disjoint
, replaceByFst
, noDuplicates
, sameElements
, notDuplicatedIn
, deleteOn
, maybeList
, elemPermutation
, groupOn
, nubOn
, sortOn
, sortedGroups
, sortedGroupsOn
, regroup
, regroupBy
, domain
, powerSet
, powerSetPermutations
, uniquePowerSetPermutations
, suffixes
, nest
, map2
, zipf
, lookupWithDefault
, lookupWithDefaultFunction
, replicateHead
, padHead
, padTail
, chunk
, stripHead
, discardEnds
, removeDuplicates
, removeDuplicatesBy
, extract
, rollback
, splitAtMatches
, splitAround
) where
import Control.Arrow ((&&&))
import Control.Monad (filterM)
import Data.Function (on)
import Data.List ((\\), deleteBy, deleteFirstsBy, elemIndex, groupBy, intersect, nub, nubBy, permutations, sort, sortBy, tails)
import Data.List.Split (chunksOf, wordsBy)
import Data.Maybe (fromMaybe)
hasSubset :: Eq a
=> [a]
-> [a]
-> Bool
hasSubset x y = null $ y \\ x
disjoint :: Eq a
=> [a]
-> [a]
-> Bool
disjoint x y = null $ x `intersect` y
replaceByFst :: Eq a
=> (a, b)
-> [(a, b)]
-> [(a, b)]
replaceByFst x = (x :) . deleteBy ((==) `on` fst) x
noDuplicates :: Eq a
=> [a]
-> Bool
noDuplicates x = length x == length (nub x)
sameElements :: Ord a
=> [a]
-> [a]
-> Bool
sameElements x y = sort x == sort y
notDuplicatedIn :: Eq b
=> (a -> b)
-> a
-> [a]
-> Bool
notDuplicatedIn f x ys = f x `notElem` map f ys
deleteOn :: Eq b => (a -> b) -> a -> [a] -> [a]
deleteOn f = deleteBy ((==) `on` f)
maybeList :: [a] -> Maybe [a]
maybeList [] = Nothing
maybeList xs = Just xs
elemPermutation :: Eq a => [a] -> [a] -> Maybe [Int]
elemPermutation = mapM . flip elemIndex
groupOn :: Eq b => (a -> b) -> [a] -> [[a]]
groupOn f = groupBy ((==) `on` f)
nubOn :: Eq b => (a -> b) -> [a] -> [a]
nubOn f = nubBy ((==) `on` f)
sortOn :: Ord b => (a -> b) -> [a] -> [a]
sortOn f = sortBy (compare `on` f)
sortedGroups :: Ord b => [(b, c)] -> [(b, [c])]
sortedGroups = sortedGroupsOn fst snd
sortedGroupsOn :: Ord b => (a -> b) -> (a -> c) -> [a] -> [(b, [c])]
sortedGroupsOn f g =
fmap ((f . head) &&& fmap g)
. groupOn f
. sortOn f
domain :: (Bounded a, Enum a) => [a]
domain = [minBound..maxBound]
powerSet :: [a] -> [[a]]
powerSet = filterM (const domain)
powerSetPermutations :: [a] -> [[a]]
powerSetPermutations = concatMap permutations . powerSet
uniquePowerSetPermutations :: Eq a => [a] -> [[a]]
uniquePowerSetPermutations = nub . powerSetPermutations
suffixes :: [a] -> [[a]]
suffixes = init . tails
nest :: Monad m => [a] -> [m a]
nest = map return
map2 :: (a -> b) -> [[a]] -> [[b]]
map2 = map . map
zipf :: [a -> b]
-> [a]
-> [b]
zipf (f:fs) (x:xs) = f x : zipf fs xs
zipf _ _ = []
lookupWithDefault :: Eq a =>
b
-> a
-> [(a, b)]
-> b
lookupWithDefault y = lookupWithDefaultFunction (const y)
lookupWithDefaultFunction :: Eq a =>
(a -> b)
-> a
-> [(a, b)]
-> b
lookupWithDefaultFunction f x = fromMaybe (f x) . lookup x
replicateHead :: Int
-> [a]
-> [a]
replicateHead n =
uncurry (++)
. (replicate n . head &&& id)
padHead ::
Int
-> a
-> [a]
-> [a]
padHead n y xs =
replicate (n length xs) y ++ xs
padTail ::
Int
-> a
-> [a]
-> [a]
padTail n y xs =
xs ++ replicate (n length xs) y
chunk ::
Int
-> [a]
-> [[a]]
chunk = chunksOf
stripHead :: Eq a =>
a
-> [a]
-> [a]
stripHead x y@(ye : ys)
| x == ye = stripHead x ys
| otherwise = y
stripHead _ [] = []
discardEnds :: [a]
-> [a]
discardEnds = init . tail
removeDuplicates :: Eq a => [a] -> [a]
removeDuplicates = removeDuplicatesBy (==)
removeDuplicatesBy ::
(a -> a -> Bool)
-> [a]
-> [a]
removeDuplicatesBy equals x =
let
duplicates = nubBy equals (deleteFirstsBy equals x (nubBy equals x))
in
deleteFirstsBy equals (nubBy equals x) duplicates
extract :: (a -> Bool) -> [a] -> ([a], Maybe a)
extract _ [] = ([], Nothing)
extract p x =
let
extract' a @ (_, _, Just _) = a
extract' a @ (_, [], Nothing) = a
extract' (y', ze : zs, Nothing)
| p ze = (y', zs, Just ze)
| otherwise = extract' (ze : y', zs, Nothing)
(y, z, w) = extract' ([], x, Nothing)
in
(rollback y z, w)
rollback ::
[a]
-> [a]
-> [a]
rollback = flip (foldl (flip (:)))
splitAtMatches :: Eq a =>
a
-> [a]
-> [[a]]
splitAtMatches = wordsBy . (==)
splitAround :: Int -> [a] -> ([a], a, [a])
splitAround n x =
let
(y, z) = splitAt (n + 1) x
in
(init y, last y, z)
regroup :: Ord a => [(a, b)] -> [(a, [b])]
regroup = regroupBy id
regroupBy :: Ord a =>
([b] -> c)
-> [(a, b)]
-> [(a, c)]
regroupBy f =
let
sorter (x, _) (y, _) = compare x y
grouper x y = fst x == fst y
crusher ys = (fst $ head ys, f $ map snd ys)
in
map crusher . groupBy grouper . sortBy sorter