{-# LANGUAGE CPP, TupleSections, ConstraintKinds #-}
{-# OPTIONS_GHC -fno-warn-duplicate-exports #-}
module Data.List.Extra(
module Data.List,
lower, upper, trim, trimStart, trimEnd, word1, line1,
escapeHTML, escapeJSON,
unescapeHTML, unescapeJSON,
dropEnd, takeEnd, splitAtEnd, breakEnd, spanEnd,
dropWhileEnd', takeWhileEnd,
stripSuffix, stripInfix, stripInfixEnd,
dropPrefix, dropSuffix,
wordsBy, linesBy,
breakOn, breakOnEnd, splitOn, split, chunksOf,
headDef, lastDef, (!?), notNull, list, unsnoc, cons, snoc,
drop1, dropEnd1, mconcatMap, compareLength, comparingLength,
enumerate,
groupSort, groupSortOn, groupSortBy,
nubOrd, nubOrdBy, nubOrdOn,
nubOn, groupOn, groupOnKey,
nubSort, nubSortBy, nubSortOn,
maximumOn, minimumOn,
sum', product',
sumOn', productOn',
disjoint, disjointOrd, disjointOrdBy, allSame, anySame,
repeatedly, repeatedlyNE, firstJust,
concatUnzip, concatUnzip3,
zipFrom, zipWithFrom, zipWithLongest,
replace, merge, mergeBy,
) where
import Partial
import Data.List
import Data.Maybe
import Data.Function
import Data.Char
import Data.Tuple.Extra
import Data.Monoid
import Numeric
import Data.Functor
import Data.Foldable
import Prelude
import Data.List.NonEmpty (NonEmpty ((:|)))
repeatedly :: ([a] -> (b, [a])) -> [a] -> [b]
repeatedly :: forall a b. ([a] -> (b, [a])) -> [a] -> [b]
repeatedly [a] -> (b, [a])
f [] = []
repeatedly [a] -> (b, [a])
f [a]
as = b
b b -> [b] -> [b]
forall a. a -> [a] -> [a]
: ([a] -> (b, [a])) -> [a] -> [b]
forall a b. ([a] -> (b, [a])) -> [a] -> [b]
repeatedly [a] -> (b, [a])
f [a]
as'
where (b
b, [a]
as') = [a] -> (b, [a])
f [a]
as
repeatedlyNE :: (NonEmpty a -> (b, [a])) -> [a] -> [b]
repeatedlyNE :: forall a b. (NonEmpty a -> (b, [a])) -> [a] -> [b]
repeatedlyNE NonEmpty a -> (b, [a])
f [] = []
repeatedlyNE NonEmpty a -> (b, [a])
f (a
a : [a]
as) = b
b b -> [b] -> [b]
forall a. a -> [a] -> [a]
: (NonEmpty a -> (b, [a])) -> [a] -> [b]
forall a b. (NonEmpty a -> (b, [a])) -> [a] -> [b]
repeatedlyNE NonEmpty a -> (b, [a])
f [a]
as'
where (b
b, [a]
as') = NonEmpty a -> (b, [a])
f (a
a a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [a]
as)
disjoint :: Eq a => [a] -> [a] -> Bool
disjoint :: forall a. Eq a => [a] -> [a] -> Bool
disjoint [a]
xs = [a] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null ([a] -> Bool) -> ([a] -> [a]) -> [a] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a] -> [a]
forall a. Eq a => [a] -> [a] -> [a]
intersect [a]
xs
disjointOrd :: Ord a => [a] -> [a] -> Bool
disjointOrd :: forall a. Ord a => [a] -> [a] -> Bool
disjointOrd = (a -> a -> Ordering) -> [a] -> [a] -> Bool
forall a. (a -> a -> Ordering) -> [a] -> [a] -> Bool
disjointOrdBy a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
disjointOrdBy :: (a -> a -> Ordering) -> [a] -> [a] -> Bool
disjointOrdBy :: forall a. (a -> a -> Ordering) -> [a] -> [a] -> Bool
disjointOrdBy a -> a -> Ordering
cmp [a]
xs [a]
ys
| [a] -> [a] -> Bool
forall {a} {a}. [a] -> [a] -> Bool
shorter [a]
xs [a]
ys = [a] -> [a] -> Bool
forall {t :: * -> *} {t :: * -> *}.
(Foldable t, Foldable t) =>
t a -> t a -> Bool
go [a]
xs [a]
ys
| Bool
otherwise = [a] -> [a] -> Bool
forall {t :: * -> *} {t :: * -> *}.
(Foldable t, Foldable t) =>
t a -> t a -> Bool
go [a]
ys [a]
xs
where
shorter :: [a] -> [a] -> Bool
shorter [a]
_ [] = Bool
False
shorter [] [a]
_ = Bool
True
shorter (a
_:[a]
xs) (a
_:[a]
ys) = [a] -> [a] -> Bool
shorter [a]
xs [a]
ys
go :: t a -> t a -> Bool
go t a
xs = Bool -> Bool
not (Bool -> Bool) -> (t a -> Bool) -> t a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> t a -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (\a
a -> (a -> a -> Ordering) -> a -> RB a -> Bool
forall a. (a -> a -> Ordering) -> a -> RB a -> Bool
memberRB a -> a -> Ordering
cmp a
a RB a
tree)
where
tree :: RB a
tree = (RB a -> a -> RB a) -> RB a -> t a -> RB a
forall b a. (b -> a -> b) -> b -> t a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((a -> RB a -> RB a) -> RB a -> a -> RB a
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((a -> a -> Ordering) -> a -> RB a -> RB a
forall a. (a -> a -> Ordering) -> a -> RB a -> RB a
insertRB a -> a -> Ordering
cmp)) RB a
forall a. RB a
E t a
xs
anySame :: Eq a => [a] -> Bool
anySame :: forall a. Eq a => [a] -> Bool
anySame = [a] -> [a] -> Bool
forall a. Eq a => [a] -> [a] -> Bool
f []
where
f :: [a] -> [a] -> Bool
f [a]
seen (a
x:[a]
xs) = a
x a -> [a] -> Bool
forall a. Eq a => a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [a]
seen Bool -> Bool -> Bool
|| [a] -> [a] -> Bool
f (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
seen) [a]
xs
f [a]
seen [] = Bool
False
allSame :: Eq a => [a] -> Bool
allSame :: forall a. Eq a => [a] -> Bool
allSame [] = Bool
True
allSame (a
x:[a]
xs) = (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==) [a]
xs
headDef :: a -> [a] -> a
headDef :: forall a. a -> [a] -> a
headDef a
d [] = a
d
headDef a
_ (a
x:[a]
_) = a
x
lastDef :: a -> [a] -> a
lastDef :: forall a. a -> [a] -> a
lastDef a
d [a]
xs = (a -> a -> a) -> a -> [a] -> a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl (\a
_ a
x -> a
x) a
d [a]
xs
{-# INLINE lastDef #-}
#if __GLASGOW_HASKELL__ <= 906
(!?) :: [a] -> Int -> Maybe a
[a]
xs !? :: forall a. [a] -> Int -> Maybe a
!? Int
n
| Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = Maybe a
forall a. Maybe a
Nothing
| Bool
otherwise = (a -> (Int -> Maybe a) -> Int -> Maybe a)
-> (Int -> Maybe a) -> [a] -> Int -> Maybe 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
x Int -> Maybe a
r Int
k -> case Int
k of
Int
0 -> a -> Maybe a
forall a. a -> Maybe a
Just a
x
Int
_ -> Int -> Maybe a
r (Int
kInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)) (Maybe a -> Int -> Maybe a
forall a b. a -> b -> a
const Maybe a
forall a. Maybe a
Nothing) [a]
xs Int
n
{-# INLINABLE (!?) #-}
#endif
notNull :: [a] -> Bool
notNull :: forall a. [a] -> Bool
notNull = Bool -> Bool
not (Bool -> Bool) -> ([a] -> Bool) -> [a] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null
list :: b -> (a -> [a] -> b) -> [a] -> b
list :: forall b a. b -> (a -> [a] -> b) -> [a] -> b
list b
nil a -> [a] -> b
cons [] = b
nil
list b
nil a -> [a] -> b
cons (a
x:[a]
xs) = a -> [a] -> b
cons a
x [a]
xs
#if __GLASGOW_HASKELL__ <= 906
unsnoc :: [a] -> Maybe ([a], a)
unsnoc :: forall a. [a] -> Maybe ([a], a)
unsnoc [] = Maybe ([a], a)
forall a. Maybe a
Nothing
unsnoc [a
x] = ([a], a) -> Maybe ([a], a)
forall a. a -> Maybe a
Just ([], a
x)
unsnoc (a
x:[a]
xs) = ([a], a) -> Maybe ([a], a)
forall a. a -> Maybe a
Just (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
a, a
b)
where Just ([a]
a,a
b) = [a] -> Maybe ([a], a)
forall a. [a] -> Maybe ([a], a)
unsnoc [a]
xs
#endif
cons :: a -> [a] -> [a]
cons :: forall a. a -> [a] -> [a]
cons = (:)
snoc :: [a] -> a -> [a]
snoc :: forall a. [a] -> a -> [a]
snoc [a]
xs a
x = [a]
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x]
enumerate :: (Enum a, Bounded a) => [a]
enumerate :: forall a. (Enum a, Bounded a) => [a]
enumerate = [a
forall a. Bounded a => a
minBound..a
forall a. Bounded a => a
maxBound]
takeEnd :: Int -> [a] -> [a]
takeEnd :: forall a. Int -> [a] -> [a]
takeEnd Int
i [a]
xs
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = []
| Bool
otherwise = [a] -> [a] -> [a]
forall {a} {a}. [a] -> [a] -> [a]
f [a]
xs (Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
drop Int
i [a]
xs)
where f :: [a] -> [a] -> [a]
f (a
x:[a]
xs) (a
y:[a]
ys) = [a] -> [a] -> [a]
f [a]
xs [a]
ys
f [a]
xs [a]
_ = [a]
xs
dropEnd :: Int -> [a] -> [a]
dropEnd :: forall a. Int -> [a] -> [a]
dropEnd Int
i [a]
xs
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = [a]
xs
| Bool
otherwise = [a] -> [a] -> [a]
forall {a} {a}. [a] -> [a] -> [a]
f [a]
xs (Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
drop Int
i [a]
xs)
where f :: [a] -> [a] -> [a]
f (a
x:[a]
xs) (a
y:[a]
ys) = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
f [a]
xs [a]
ys
f [a]
_ [a]
_ = []
splitAtEnd :: Int -> [a] -> ([a], [a])
splitAtEnd :: forall a. Int -> [a] -> ([a], [a])
splitAtEnd Int
i [a]
xs
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = ([a]
xs, [])
| Bool
otherwise = [a] -> [a] -> ([a], [a])
forall {a} {a}. [a] -> [a] -> ([a], [a])
f [a]
xs (Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
drop Int
i [a]
xs)
where f :: [a] -> [a] -> ([a], [a])
f (a
x:[a]
xs) (a
y:[a]
ys) = ([a] -> [a]) -> ([a], [a]) -> ([a], [a])
forall a a' b. (a -> a') -> (a, b) -> (a', b)
first (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) (([a], [a]) -> ([a], [a])) -> ([a], [a]) -> ([a], [a])
forall a b. (a -> b) -> a -> b
$ [a] -> [a] -> ([a], [a])
f [a]
xs [a]
ys
f [a]
xs [a]
_ = ([], [a]
xs)
zipFrom :: Enum a => a -> [b] -> [(a, b)]
zipFrom :: forall a b. Enum a => a -> [b] -> [(a, b)]
zipFrom = (a -> b -> (a, b)) -> a -> [b] -> [(a, b)]
forall a b c. Enum a => (a -> b -> c) -> a -> [b] -> [c]
zipWithFrom (,)
zipWithFrom :: Enum a => (a -> b -> c) -> a -> [b] -> [c]
zipWithFrom :: forall a b c. Enum a => (a -> b -> c) -> a -> [b] -> [c]
zipWithFrom a -> b -> c
f a
a = (a -> b -> c) -> [a] -> [b] -> [c]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith a -> b -> c
f [a
a..]
concatUnzip :: [([a], [b])] -> ([a], [b])
concatUnzip :: forall a b. [([a], [b])] -> ([a], [b])
concatUnzip = ([[a]] -> [a]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat ([[a]] -> [a]) -> ([[b]] -> [b]) -> ([[a]], [[b]]) -> ([a], [b])
forall a a' b b'. (a -> a') -> (b -> b') -> (a, b) -> (a', b')
*** [[b]] -> [b]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat) (([[a]], [[b]]) -> ([a], [b]))
-> ([([a], [b])] -> ([[a]], [[b]])) -> [([a], [b])] -> ([a], [b])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [([a], [b])] -> ([[a]], [[b]])
forall a b. [(a, b)] -> ([a], [b])
Prelude.unzip
concatUnzip3 :: [([a],[b],[c])] -> ([a],[b],[c])
concatUnzip3 :: forall a b c. [([a], [b], [c])] -> ([a], [b], [c])
concatUnzip3 [([a], [b], [c])]
xs = ([[a]] -> [a]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[a]]
a, [[b]] -> [b]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[b]]
b, [[c]] -> [c]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[c]]
c)
where ([[a]]
a,[[b]]
b,[[c]]
c) = [([a], [b], [c])] -> ([[a]], [[b]], [[c]])
forall a b c. [(a, b, c)] -> ([a], [b], [c])
unzip3 [([a], [b], [c])]
xs
takeWhileEnd :: (a -> Bool) -> [a] -> [a]
takeWhileEnd :: forall a. (a -> Bool) -> [a] -> [a]
takeWhileEnd a -> Bool
f = [a] -> [a]
forall a. [a] -> [a]
reverse ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile a -> Bool
f ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
forall a. [a] -> [a]
reverse
trimStart :: String -> String
trimStart :: String -> String
trimStart = (Char -> Bool) -> String -> String
forall a. (a -> Bool) -> [a] -> [a]
dropWhile Char -> Bool
isSpace
trimEnd :: String -> String
trimEnd :: String -> String
trimEnd = (Char -> Bool) -> String -> String
forall a. (a -> Bool) -> [a] -> [a]
dropWhileEnd Char -> Bool
isSpace
trim :: String -> String
trim :: String -> String
trim = String -> String
trimEnd (String -> String) -> (String -> String) -> String -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> String
trimStart
lower :: String -> String
lower :: String -> String
lower = (Char -> Char) -> String -> String
forall a b. (a -> b) -> [a] -> [b]
map Char -> Char
toLower
upper :: String -> String
upper :: String -> String
upper = (Char -> Char) -> String -> String
forall a b. (a -> b) -> [a] -> [b]
map Char -> Char
toUpper
word1 :: String -> (String, String)
word1 :: String -> (String, String)
word1 = (String -> String) -> (String, String) -> (String, String)
forall b b' a. (b -> b') -> (a, b) -> (a, b')
second String -> String
trimStart ((String, String) -> (String, String))
-> (String -> (String, String)) -> String -> (String, String)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Char -> Bool) -> String -> (String, String)
forall a. (a -> Bool) -> [a] -> ([a], [a])
break Char -> Bool
isSpace (String -> (String, String))
-> (String -> String) -> String -> (String, String)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> String
trimStart
line1 :: String -> (String, String)
line1 :: String -> (String, String)
line1 = (String -> String) -> (String, String) -> (String, String)
forall b b' a. (b -> b') -> (a, b) -> (a, b')
second String -> String
forall a. [a] -> [a]
drop1 ((String, String) -> (String, String))
-> (String -> (String, String)) -> String -> (String, String)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Char -> Bool) -> String -> (String, String)
forall a. (a -> Bool) -> [a] -> ([a], [a])
break (Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'\n')
escapeHTML :: String -> String
escapeHTML :: String -> String
escapeHTML = (Char -> String) -> String -> String
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Char -> String
f
where
f :: Char -> String
f Char
'>' = String
">"
f Char
'<' = String
"<"
f Char
'&' = String
"&"
f Char
'\"' = String
"""
f Char
'\'' = String
"'"
f Char
x = [Char
x]
unescapeHTML :: String -> String
unescapeHTML :: String -> String
unescapeHTML (Char
'&':String
xs)
| Just String
xs <- String -> String -> Maybe String
forall a. Eq a => [a] -> [a] -> Maybe [a]
stripPrefix String
"lt;" String
xs = Char
'<' Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
unescapeHTML String
xs
| Just String
xs <- String -> String -> Maybe String
forall a. Eq a => [a] -> [a] -> Maybe [a]
stripPrefix String
"gt;" String
xs = Char
'>' Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
unescapeHTML String
xs
| Just String
xs <- String -> String -> Maybe String
forall a. Eq a => [a] -> [a] -> Maybe [a]
stripPrefix String
"amp;" String
xs = Char
'&' Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
unescapeHTML String
xs
| Just String
xs <- String -> String -> Maybe String
forall a. Eq a => [a] -> [a] -> Maybe [a]
stripPrefix String
"quot;" String
xs = Char
'\"' Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
unescapeHTML String
xs
| Just String
xs <- String -> String -> Maybe String
forall a. Eq a => [a] -> [a] -> Maybe [a]
stripPrefix String
"#39;" String
xs = Char
'\'' Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
unescapeHTML String
xs
unescapeHTML (Char
x:String
xs) = Char
x Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
unescapeHTML String
xs
unescapeHTML [] = []
escapeJSON :: String -> String
escapeJSON :: String -> String
escapeJSON String
x = (Char -> String) -> String -> String
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Char -> String
f String
x
where f :: Char -> String
f Char
'\"' = String
"\\\""
f Char
'\\' = String
"\\\\"
f Char
'\b' = String
"\\b"
f Char
'\f' = String
"\\f"
f Char
'\n' = String
"\\n"
f Char
'\r' = String
"\\r"
f Char
'\t' = String
"\\t"
f Char
x | Char -> Bool
isControl Char
x = String
"\\u" String -> String -> String
forall a. [a] -> [a] -> [a]
++ Int -> String -> String
forall a. Int -> [a] -> [a]
takeEnd Int
4 (String
"0000" String -> String -> String
forall a. [a] -> [a] -> [a]
++ Int -> String -> String
forall a. Integral a => a -> String -> String
showHex (Char -> Int
ord Char
x) String
"")
f Char
x = [Char
x]
unescapeJSON :: String -> String
unescapeJSON :: String -> String
unescapeJSON (Char
'\\':Char
x:String
xs)
| Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'\"' = Char
'\"' Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
unescapeJSON String
xs
| Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'\\' = Char
'\\' Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
unescapeJSON String
xs
| Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'/' = Char
'/' Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
unescapeJSON String
xs
| Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'b' = Char
'\b' Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
unescapeJSON String
xs
| Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'f' = Char
'\f' Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
unescapeJSON String
xs
| Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'n' = Char
'\n' Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
unescapeJSON String
xs
| Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'r' = Char
'\r' Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
unescapeJSON String
xs
| Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
't' = Char
'\t' Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
unescapeJSON String
xs
| Char
x Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
'u', let (String
a,String
b) = Int -> String -> (String, String)
forall a. Int -> [a] -> ([a], [a])
splitAt Int
4 String
xs, String -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length String
a Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
4, [(Int
i, String
"")] <- ReadS Int
forall a. (Eq a, Num a) => ReadS a
readHex String
a = Int -> Char
chr Int
i Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
unescapeJSON String
b
unescapeJSON (Char
x:String
xs) = Char
x Char -> String -> String
forall a. a -> [a] -> [a]
: String -> String
unescapeJSON String
xs
unescapeJSON [] = []
groupOn :: Eq k => (a -> k) -> [a] -> [[a]]
groupOn :: forall k a. Eq k => (a -> k) -> [a] -> [[a]]
groupOn a -> k
f = (a -> a -> Bool) -> [a] -> [[a]]
forall a. (a -> a -> Bool) -> [a] -> [[a]]
groupBy (k -> k -> Bool
forall a. Eq a => a -> a -> Bool
(==) (k -> k -> Bool) -> (a -> k) -> a -> a -> Bool
forall {t} {t} {p}. (t -> t -> t) -> (p -> t) -> p -> p -> t
`on2` a -> k
f)
where t -> t -> t
(.*.) on2 :: (t -> t -> t) -> (p -> t) -> p -> p -> t
`on2` p -> t
f = \p
x -> let fx :: t
fx = p -> t
f p
x in \p
y -> t
fx t -> t -> t
.*. p -> t
f p
y
groupOnKey :: Eq k => (a -> k) -> [a] -> [(k, [a])]
groupOnKey :: forall k a. Eq k => (a -> k) -> [a] -> [(k, [a])]
groupOnKey a -> k
_ [] = []
groupOnKey a -> k
f (a
x:[a]
xs) = (k
fx, a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
yes) (k, [a]) -> [(k, [a])] -> [(k, [a])]
forall a. a -> [a] -> [a]
: (a -> k) -> [a] -> [(k, [a])]
forall k a. Eq k => (a -> k) -> [a] -> [(k, [a])]
groupOnKey a -> k
f [a]
no
where
fx :: k
fx = a -> k
f a
x
([a]
yes, [a]
no) = (a -> Bool) -> [a] -> ([a], [a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
span (\a
y -> k
fx k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== a -> k
f a
y) [a]
xs
{-# DEPRECATED nubOn "Use nubOrdOn, since this function is O(n^2)" #-}
nubOn :: Eq b => (a -> b) -> [a] -> [a]
nubOn :: forall b a. Eq b => (a -> b) -> [a] -> [a]
nubOn a -> b
f = ((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)]
forall a. (a -> a -> Bool) -> [a] -> [a]
nubBy (b -> b -> Bool
forall a. Eq a => a -> a -> Bool
(==) (b -> b -> Bool) -> ((b, a) -> b) -> (b, a) -> (b, a) -> Bool
forall {t} {t} {p}. (t -> t -> t) -> (p -> t) -> p -> p -> t
`on` (b, a) -> b
forall a b. (a, b) -> a
fst) ([(b, a)] -> [(b, a)]) -> ([a] -> [(b, a)]) -> [a] -> [(b, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> (b, a)) -> [a] -> [(b, a)]
forall a b. (a -> b) -> [a] -> [b]
map (\a
x -> let y :: b
y = a -> b
f a
x in b
y b -> (b, a) -> (b, a)
forall a b. a -> b -> b
`seq` (b
y, a
x))
maximumOn :: (Partial, Ord b) => (a -> b) -> [a] -> a
maximumOn :: forall b a. (Partial, Ord b) => (a -> b) -> [a] -> a
maximumOn a -> b
f [] = String -> a
forall a. Partial => String -> a
error String
"Data.List.Extra.maximumOn: empty list"
maximumOn a -> b
f (a
x:[a]
xs) = a -> b -> [a] -> a
g a
x (a -> b
f a
x) [a]
xs
where
g :: a -> b -> [a] -> a
g a
v b
mv [] = a
v
g a
v b
mv (a
x:[a]
xs) | b
mx b -> b -> Bool
forall a. Ord a => a -> a -> Bool
> b
mv = a -> b -> [a] -> a
g a
x b
mx [a]
xs
| Bool
otherwise = a -> b -> [a] -> a
g a
v b
mv [a]
xs
where mx :: b
mx = a -> b
f a
x
minimumOn :: (Partial, Ord b) => (a -> b) -> [a] -> a
minimumOn :: forall b a. (Partial, Ord b) => (a -> b) -> [a] -> a
minimumOn a -> b
f [] = String -> a
forall a. Partial => String -> a
error String
"Data.List.Extra.minimumOn: empty list"
minimumOn a -> b
f (a
x:[a]
xs) = a -> b -> [a] -> a
g a
x (a -> b
f a
x) [a]
xs
where
g :: a -> b -> [a] -> a
g a
v b
mv [] = a
v
g a
v b
mv (a
x:[a]
xs) | b
mx b -> b -> Bool
forall a. Ord a => a -> a -> Bool
< b
mv = a -> b -> [a] -> a
g a
x b
mx [a]
xs
| Bool
otherwise = a -> b -> [a] -> a
g a
v b
mv [a]
xs
where mx :: b
mx = a -> b
f a
x
groupSort :: Ord k => [(k, v)] -> [(k, [v])]
groupSort :: forall k v. Ord k => [(k, v)] -> [(k, [v])]
groupSort = ([(k, v)] -> (k, [v])) -> [[(k, v)]] -> [(k, [v])]
forall a b. (a -> b) -> [a] -> [b]
map (\[(k, v)]
x -> ((k, v) -> k
forall a b. (a, b) -> a
fst ((k, v) -> k) -> (k, v) -> k
forall a b. (a -> b) -> a -> b
$ [(k, v)] -> (k, v)
forall {a}. [a] -> a
headErr [(k, v)]
x, ((k, v) -> v) -> [(k, v)] -> [v]
forall a b. (a -> b) -> [a] -> [b]
map (k, v) -> v
forall a b. (a, b) -> b
snd [(k, v)]
x)) ([[(k, v)]] -> [(k, [v])])
-> ([(k, v)] -> [[(k, v)]]) -> [(k, v)] -> [(k, [v])]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k, v) -> k) -> [(k, v)] -> [[(k, v)]]
forall k a. Eq k => (a -> k) -> [a] -> [[a]]
groupOn (k, v) -> k
forall a b. (a, b) -> a
fst ([(k, v)] -> [[(k, v)]])
-> ([(k, v)] -> [(k, v)]) -> [(k, v)] -> [[(k, v)]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k, v) -> k) -> [(k, v)] -> [(k, v)]
forall b a. Ord b => (a -> b) -> [a] -> [a]
sortOn (k, v) -> k
forall a b. (a, b) -> a
fst
where headErr :: [a] -> a
headErr (a
x:[a]
_) = a
x
groupSortOn :: Ord b => (a -> b) -> [a] -> [[a]]
groupSortOn :: forall b a. Ord b => (a -> b) -> [a] -> [[a]]
groupSortOn a -> b
f = ([(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)]]
forall a. (a -> a -> Bool) -> [a] -> [[a]]
groupBy (b -> b -> Bool
forall a. Eq a => a -> a -> Bool
(==) (b -> b -> Bool) -> ((b, a) -> b) -> (b, a) -> (b, a) -> Bool
forall {t} {t} {p}. (t -> t -> t) -> (p -> t) -> p -> p -> t
`on` (b, a) -> b
forall a b. (a, b) -> a
fst) ([(b, a)] -> [[(b, a)]]) -> ([a] -> [(b, a)]) -> [a] -> [[(b, a)]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((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 (b -> b -> Ordering)
-> ((b, a) -> b) -> (b, a) -> (b, a) -> Ordering
forall {t} {t} {p}. (t -> t -> t) -> (p -> t) -> p -> p -> t
`on` (b, a) -> b
forall a b. (a, b) -> a
fst) ([(b, a)] -> [(b, a)]) -> ([a] -> [(b, a)]) -> [a] -> [(b, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> (b, a)) -> [a] -> [(b, a)]
forall a b. (a -> b) -> [a] -> [b]
map (a -> b
f (a -> b) -> (a -> a) -> a -> (b, a)
forall a b c. (a -> b) -> (a -> c) -> a -> (b, c)
&&& a -> a
forall a. a -> a
id)
groupSortBy :: (a -> a -> Ordering) -> [a] -> [[a]]
groupSortBy :: forall a. (a -> a -> Ordering) -> [a] -> [[a]]
groupSortBy a -> a -> Ordering
f = (a -> a -> Bool) -> [a] -> [[a]]
forall a. (a -> a -> Bool) -> [a] -> [[a]]
groupBy (\a
a a
b -> a -> a -> Ordering
f a
a a
b Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
== Ordering
EQ) ([a] -> [[a]]) -> ([a] -> [a]) -> [a] -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> Ordering) -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy a -> a -> Ordering
f
sum' :: (Num a) => [a] -> a
sum' :: forall a. Num a => [a] -> a
sum' = (a -> a -> a) -> a -> [a] -> a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' a -> a -> a
forall a. Num a => a -> a -> a
(+) a
0
sumOn' :: (Num b) => (a -> b) -> [a] -> b
sumOn' :: forall b a. Num b => (a -> b) -> [a] -> b
sumOn' a -> b
f = (b -> a -> b) -> b -> [a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\b
acc a
x -> b
acc b -> b -> b
forall a. Num a => a -> a -> a
+ a -> b
f a
x) b
0
product' :: (Num a) => [a] -> a
product' :: forall a. Num a => [a] -> a
product' = (a -> a -> a) -> a -> [a] -> a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' a -> a -> a
forall a. Num a => a -> a -> a
(*) a
1
productOn' :: (Num b) => (a -> b) -> [a] -> b
productOn' :: forall b a. Num b => (a -> b) -> [a] -> b
productOn' a -> b
f = (b -> a -> b) -> b -> [a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\b
acc a
x -> b
acc b -> b -> b
forall a. Num a => a -> a -> a
* a -> b
f a
x) b
1
merge :: Ord a => [a] -> [a] -> [a]
merge :: forall a. Ord a => [a] -> [a] -> [a]
merge = (a -> a -> Ordering) -> [a] -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
mergeBy a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
mergeBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
mergeBy :: forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
mergeBy a -> a -> Ordering
f [a]
xs [] = [a]
xs
mergeBy a -> a -> Ordering
f [] [a]
ys = [a]
ys
mergeBy a -> a -> Ordering
f (a
x:[a]
xs) (a
y:[a]
ys)
| a -> a -> Ordering
f a
x a
y Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
/= Ordering
GT = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: (a -> a -> Ordering) -> [a] -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
mergeBy a -> a -> Ordering
f [a]
xs (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ys)
| Bool
otherwise = a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
: (a -> a -> Ordering) -> [a] -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
mergeBy a -> a -> Ordering
f (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs) [a]
ys
replace :: Eq a => [a] -> [a] -> [a] -> [a]
replace :: forall a. Eq a => [a] -> [a] -> [a] -> [a]
replace [] [a]
to [a]
xs = [a] -> [a]
go [a]
xs
where go :: [a] -> [a]
go [] = [a]
to
go (a
x:[a]
xs) = [a]
to [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a]
go [a]
xs
replace [a]
from [a]
to [a]
xs | Just [a]
xs <- [a] -> [a] -> Maybe [a]
forall a. Eq a => [a] -> [a] -> Maybe [a]
stripPrefix [a]
from [a]
xs = [a]
to [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a] -> [a] -> [a] -> [a]
forall a. Eq a => [a] -> [a] -> [a] -> [a]
replace [a]
from [a]
to [a]
xs
replace [a]
from [a]
to (a
x:[a]
xs) = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a] -> [a]
forall a. Eq a => [a] -> [a] -> [a] -> [a]
replace [a]
from [a]
to [a]
xs
replace [a]
from [a]
to [] = []
breakEnd :: (a -> Bool) -> [a] -> ([a], [a])
breakEnd :: forall a. (a -> Bool) -> [a] -> ([a], [a])
breakEnd a -> Bool
f = ([a], [a]) -> ([a], [a])
forall a b. (a, b) -> (b, a)
swap (([a], [a]) -> ([a], [a]))
-> ([a] -> ([a], [a])) -> [a] -> ([a], [a])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([a] -> [a]) -> ([a], [a]) -> ([a], [a])
forall a b. (a -> b) -> (a, a) -> (b, b)
both [a] -> [a]
forall a. [a] -> [a]
reverse (([a], [a]) -> ([a], [a]))
-> ([a] -> ([a], [a])) -> [a] -> ([a], [a])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> [a] -> ([a], [a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
break a -> Bool
f ([a] -> ([a], [a])) -> ([a] -> [a]) -> [a] -> ([a], [a])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
forall a. [a] -> [a]
reverse
spanEnd :: (a -> Bool) -> [a] -> ([a], [a])
spanEnd :: forall a. (a -> Bool) -> [a] -> ([a], [a])
spanEnd a -> Bool
f = (a -> Bool) -> [a] -> ([a], [a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
breakEnd (Bool -> Bool
not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
f)
wordsBy :: (a -> Bool) -> [a] -> [[a]]
wordsBy :: forall a. (a -> Bool) -> [a] -> [[a]]
wordsBy a -> Bool
f [a]
s = case (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
dropWhile a -> Bool
f [a]
s of
[] -> []
a
x:[a]
xs -> (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
w) [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: (a -> Bool) -> [a] -> [[a]]
forall a. (a -> Bool) -> [a] -> [[a]]
wordsBy a -> Bool
f ([a] -> [a]
forall a. [a] -> [a]
drop1 [a]
z)
where ([a]
w,[a]
z) = (a -> Bool) -> [a] -> ([a], [a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
break a -> Bool
f [a]
xs
linesBy :: (a -> Bool) -> [a] -> [[a]]
linesBy :: forall a. (a -> Bool) -> [a] -> [[a]]
linesBy a -> Bool
f [] = []
linesBy a -> Bool
f [a]
s = ([a], [[a]]) -> [[a]]
forall {a}. (a, [a]) -> [a]
cons (([a], [[a]]) -> [[a]]) -> ([a], [[a]]) -> [[a]]
forall a b. (a -> b) -> a -> b
$ case (a -> Bool) -> [a] -> ([a], [a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
break a -> Bool
f [a]
s of
([a]
l, [a]
s) -> ([a]
l,) ([[a]] -> ([a], [[a]])) -> [[a]] -> ([a], [[a]])
forall a b. (a -> b) -> a -> b
$ case [a]
s of
[] -> []
a
_:[a]
s -> (a -> Bool) -> [a] -> [[a]]
forall a. (a -> Bool) -> [a] -> [[a]]
linesBy a -> Bool
f [a]
s
where
cons :: (a, [a]) -> [a]
cons ~(a
h, [a]
t) = a
h a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
t
firstJust :: (a -> Maybe b) -> [a] -> Maybe b
firstJust :: forall a b. (a -> Maybe b) -> [a] -> Maybe b
firstJust a -> Maybe b
f = [b] -> Maybe b
forall a. [a] -> Maybe a
listToMaybe ([b] -> Maybe b) -> ([a] -> [b]) -> [a] -> Maybe b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Maybe b) -> [a] -> [b]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe a -> Maybe b
f
drop1 :: [a] -> [a]
drop1 :: forall a. [a] -> [a]
drop1 [] = []
drop1 (a
x:[a]
xs) = [a]
xs
dropEnd1 :: [a] -> [a]
dropEnd1 :: forall a. [a] -> [a]
dropEnd1 [] = []
dropEnd1 (a
x:[a]
xs) = (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
z a -> [a]
f a
y -> a
y a -> [a] -> [a]
forall a. a -> [a] -> [a]
: a -> [a]
f a
z) ([a] -> a -> [a]
forall a b. a -> b -> a
const []) [a]
xs a
x
mconcatMap :: Monoid b => (a -> b) -> [a] -> b
mconcatMap :: forall b a. Monoid b => (a -> b) -> [a] -> b
mconcatMap a -> b
f = [b] -> b
forall a. Monoid a => [a] -> a
mconcat ([b] -> b) -> ([a] -> [b]) -> [a] -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b) -> [a] -> [b]
forall a b. (a -> b) -> [a] -> [b]
map a -> b
f
breakOn :: Eq a => [a] -> [a] -> ([a], [a])
breakOn :: forall a. Eq a => [a] -> [a] -> ([a], [a])
breakOn [a]
needle [a]
haystack | [a]
needle [a] -> [a] -> Bool
forall a. Eq a => [a] -> [a] -> Bool
`isPrefixOf` [a]
haystack = ([], [a]
haystack)
breakOn [a]
needle [] = ([], [])
breakOn [a]
needle (a
x:[a]
xs) = ([a] -> [a]) -> ([a], [a]) -> ([a], [a])
forall a a' b. (a -> a') -> (a, b) -> (a', b)
first (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) (([a], [a]) -> ([a], [a])) -> ([a], [a]) -> ([a], [a])
forall a b. (a -> b) -> a -> b
$ [a] -> [a] -> ([a], [a])
forall a. Eq a => [a] -> [a] -> ([a], [a])
breakOn [a]
needle [a]
xs
breakOnEnd :: Eq a => [a] -> [a] -> ([a], [a])
breakOnEnd :: forall a. Eq a => [a] -> [a] -> ([a], [a])
breakOnEnd [a]
needle [a]
haystack = ([a] -> [a]) -> ([a], [a]) -> ([a], [a])
forall a b. (a -> b) -> (a, a) -> (b, b)
both [a] -> [a]
forall a. [a] -> [a]
reverse (([a], [a]) -> ([a], [a])) -> ([a], [a]) -> ([a], [a])
forall a b. (a -> b) -> a -> b
$ ([a], [a]) -> ([a], [a])
forall a b. (a, b) -> (b, a)
swap (([a], [a]) -> ([a], [a])) -> ([a], [a]) -> ([a], [a])
forall a b. (a -> b) -> a -> b
$ [a] -> [a] -> ([a], [a])
forall a. Eq a => [a] -> [a] -> ([a], [a])
breakOn ([a] -> [a]
forall a. [a] -> [a]
reverse [a]
needle) ([a] -> [a]
forall a. [a] -> [a]
reverse [a]
haystack)
splitOn :: (Partial, Eq a) => [a] -> [a] -> [[a]]
splitOn :: forall a. (Partial, Eq a) => [a] -> [a] -> [[a]]
splitOn [] [a]
_ = String -> [[a]]
forall a. Partial => String -> a
error String
"splitOn, needle may not be empty"
splitOn [a]
_ [] = [[]]
splitOn [a]
needle [a]
haystack = [a]
a [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: if [a] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [a]
b then [] else [a] -> [a] -> [[a]]
forall a. (Partial, Eq a) => [a] -> [a] -> [[a]]
splitOn [a]
needle ([a] -> [[a]]) -> [a] -> [[a]]
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
drop ([a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
needle) [a]
b
where ([a]
a,[a]
b) = [a] -> [a] -> ([a], [a])
forall a. Eq a => [a] -> [a] -> ([a], [a])
breakOn [a]
needle [a]
haystack
split :: (a -> Bool) -> [a] -> [[a]]
split :: forall a. (a -> Bool) -> [a] -> [[a]]
split a -> Bool
f [] = [[]]
split a -> Bool
f (a
x:[a]
xs) | a -> Bool
f a
x = [] [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: (a -> Bool) -> [a] -> [[a]]
forall a. (a -> Bool) -> [a] -> [[a]]
split a -> Bool
f [a]
xs
split a -> Bool
f (a
x:[a]
xs) | [a]
y:[[a]]
ys <- (a -> Bool) -> [a] -> [[a]]
forall a. (a -> Bool) -> [a] -> [[a]]
split a -> Bool
f [a]
xs = (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
y) [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: [[a]]
ys
dropWhileEnd' :: (a -> Bool) -> [a] -> [a]
dropWhileEnd' :: forall a. (a -> Bool) -> [a] -> [a]
dropWhileEnd' a -> Bool
p = (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
x [a]
xs -> if [a] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [a]
xs Bool -> Bool -> Bool
&& a -> Bool
p a
x then [] else a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
xs) []
dropPrefix :: Eq a => [a] -> [a] -> [a]
dropPrefix :: forall a. Eq a => [a] -> [a] -> [a]
dropPrefix [a]
a [a]
b = [a] -> Maybe [a] -> [a]
forall a. a -> Maybe a -> a
fromMaybe [a]
b (Maybe [a] -> [a]) -> Maybe [a] -> [a]
forall a b. (a -> b) -> a -> b
$ [a] -> [a] -> Maybe [a]
forall a. Eq a => [a] -> [a] -> Maybe [a]
stripPrefix [a]
a [a]
b
dropSuffix :: Eq a => [a] -> [a] -> [a]
dropSuffix :: forall a. Eq a => [a] -> [a] -> [a]
dropSuffix [a]
a [a]
b = [a] -> Maybe [a] -> [a]
forall a. a -> Maybe a -> a
fromMaybe [a]
b (Maybe [a] -> [a]) -> Maybe [a] -> [a]
forall a b. (a -> b) -> a -> b
$ [a] -> [a] -> Maybe [a]
forall a. Eq a => [a] -> [a] -> Maybe [a]
stripSuffix [a]
a [a]
b
stripSuffix :: Eq a => [a] -> [a] -> Maybe [a]
stripSuffix :: forall a. Eq a => [a] -> [a] -> Maybe [a]
stripSuffix [a]
a [a]
b = [a] -> [a]
forall a. [a] -> [a]
reverse ([a] -> [a]) -> Maybe [a] -> Maybe [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a] -> [a] -> Maybe [a]
forall a. Eq a => [a] -> [a] -> Maybe [a]
stripPrefix ([a] -> [a]
forall a. [a] -> [a]
reverse [a]
a) ([a] -> [a]
forall a. [a] -> [a]
reverse [a]
b)
stripInfix :: Eq a => [a] -> [a] -> Maybe ([a], [a])
stripInfix :: forall a. Eq a => [a] -> [a] -> Maybe ([a], [a])
stripInfix [a]
needle [a]
haystack | Just [a]
rest <- [a] -> [a] -> Maybe [a]
forall a. Eq a => [a] -> [a] -> Maybe [a]
stripPrefix [a]
needle [a]
haystack = ([a], [a]) -> Maybe ([a], [a])
forall a. a -> Maybe a
Just ([], [a]
rest)
stripInfix [a]
needle [] = Maybe ([a], [a])
forall a. Maybe a
Nothing
stripInfix [a]
needle (a
x:[a]
xs) = ([a] -> [a]) -> ([a], [a]) -> ([a], [a])
forall a a' b. (a -> a') -> (a, b) -> (a', b)
first (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) (([a], [a]) -> ([a], [a])) -> Maybe ([a], [a]) -> Maybe ([a], [a])
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a] -> [a] -> Maybe ([a], [a])
forall a. Eq a => [a] -> [a] -> Maybe ([a], [a])
stripInfix [a]
needle [a]
xs
stripInfixEnd :: Eq a => [a] -> [a] -> Maybe ([a], [a])
stripInfixEnd :: forall a. Eq a => [a] -> [a] -> Maybe ([a], [a])
stripInfixEnd [a]
needle [a]
haystack = ([a] -> [a]) -> ([a], [a]) -> ([a], [a])
forall a b. (a -> b) -> (a, a) -> (b, b)
both [a] -> [a]
forall a. [a] -> [a]
reverse (([a], [a]) -> ([a], [a]))
-> (([a], [a]) -> ([a], [a])) -> ([a], [a]) -> ([a], [a])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([a], [a]) -> ([a], [a])
forall a b. (a, b) -> (b, a)
swap (([a], [a]) -> ([a], [a])) -> Maybe ([a], [a]) -> Maybe ([a], [a])
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a] -> [a] -> Maybe ([a], [a])
forall a. Eq a => [a] -> [a] -> Maybe ([a], [a])
stripInfix ([a] -> [a]
forall a. [a] -> [a]
reverse [a]
needle) ([a] -> [a]
forall a. [a] -> [a]
reverse [a]
haystack)
chunksOf :: Partial => Int -> [a] -> [[a]]
chunksOf :: forall a. Partial => Int -> [a] -> [[a]]
chunksOf Int
i [a]
xs | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = String -> [[a]]
forall a. Partial => String -> a
error (String -> [[a]]) -> String -> [[a]]
forall a b. (a -> b) -> a -> b
$ String
"chunksOf, number must be positive, got " String -> String -> String
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
i
chunksOf Int
i [a]
xs = ([a] -> ([a], [a])) -> [a] -> [[a]]
forall a b. ([a] -> (b, [a])) -> [a] -> [b]
repeatedly (Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
splitAt Int
i) [a]
xs
nubSort :: Ord a => [a] -> [a]
nubSort :: forall a. Ord a => [a] -> [a]
nubSort = (a -> a -> Ordering) -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a]
nubSortBy a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
nubSortOn :: Ord b => (a -> b) -> [a] -> [a]
nubSortOn :: forall b a. Ord b => (a -> b) -> [a] -> [a]
nubSortOn a -> b
f = (a -> a -> Ordering) -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a]
nubSortBy (b -> b -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (b -> b -> Ordering) -> (a -> b) -> a -> a -> Ordering
forall {t} {t} {p}. (t -> t -> t) -> (p -> t) -> p -> p -> t
`on` a -> b
f)
nubSortBy :: (a -> a -> Ordering) -> [a] -> [a]
nubSortBy :: forall a. (a -> a -> Ordering) -> [a] -> [a]
nubSortBy a -> a -> Ordering
cmp = [a] -> [a]
f ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> Ordering) -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy a -> a -> Ordering
cmp
where f :: [a] -> [a]
f (a
x1:a
x2:[a]
xs) | a -> a -> Ordering
cmp a
x1 a
x2 Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
== Ordering
EQ = [a] -> [a]
f (a
x1a -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs)
f (a
x:[a]
xs) = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a]
f [a]
xs
f [] = []
nubOrd :: Ord a => [a] -> [a]
nubOrd :: forall a. Ord a => [a] -> [a]
nubOrd = (a -> a -> Ordering) -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a]
nubOrdBy a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
nubOrdOn :: Ord b => (a -> b) -> [a] -> [a]
nubOrdOn :: forall b a. Ord b => (a -> b) -> [a] -> [a]
nubOrdOn a -> b
f = ((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)]
forall a. (a -> a -> Ordering) -> [a] -> [a]
nubOrdBy (b -> b -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (b -> b -> Ordering)
-> ((b, a) -> b) -> (b, a) -> (b, a) -> Ordering
forall {t} {t} {p}. (t -> t -> t) -> (p -> t) -> p -> p -> t
`on` (b, a) -> b
forall a b. (a, b) -> a
fst) ([(b, a)] -> [(b, a)]) -> ([a] -> [(b, a)]) -> [a] -> [(b, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> (b, a)) -> [a] -> [(b, a)]
forall a b. (a -> b) -> [a] -> [b]
map (a -> b
f (a -> b) -> (a -> a) -> a -> (b, a)
forall a b c. (a -> b) -> (a -> c) -> a -> (b, c)
&&& a -> a
forall a. a -> a
id)
nubOrdBy :: (a -> a -> Ordering) -> [a] -> [a]
nubOrdBy :: forall a. (a -> a -> Ordering) -> [a] -> [a]
nubOrdBy a -> a -> Ordering
cmp [a]
xs = RB a -> [a] -> [a]
f RB a
forall a. RB a
E [a]
xs
where f :: RB a -> [a] -> [a]
f RB a
seen [] = []
f RB a
seen (a
x:[a]
xs) | (a -> a -> Ordering) -> a -> RB a -> Bool
forall a. (a -> a -> Ordering) -> a -> RB a -> Bool
memberRB a -> a -> Ordering
cmp a
x RB a
seen = RB a -> [a] -> [a]
f RB a
seen [a]
xs
| Bool
otherwise = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: RB a -> [a] -> [a]
f ((a -> a -> Ordering) -> a -> RB a -> RB a
forall a. (a -> a -> Ordering) -> a -> RB a -> RB a
insertRB a -> a -> Ordering
cmp a
x RB a
seen) [a]
xs
data RB a = E | T_R (RB a) a (RB a) | T_B (RB a) a (RB a) deriving Int -> RB a -> String -> String
[RB a] -> String -> String
RB a -> String
(Int -> RB a -> String -> String)
-> (RB a -> String) -> ([RB a] -> String -> String) -> Show (RB a)
forall a. Show a => Int -> RB a -> String -> String
forall a. Show a => [RB a] -> String -> String
forall a. Show a => RB a -> String
forall a.
(Int -> a -> String -> String)
-> (a -> String) -> ([a] -> String -> String) -> Show a
$cshowsPrec :: forall a. Show a => Int -> RB a -> String -> String
showsPrec :: Int -> RB a -> String -> String
$cshow :: forall a. Show a => RB a -> String
show :: RB a -> String
$cshowList :: forall a. Show a => [RB a] -> String -> String
showList :: [RB a] -> String -> String
Show
insertRB :: (a -> a -> Ordering) -> a -> RB a -> RB a
insertRB :: forall a. (a -> a -> Ordering) -> a -> RB a -> RB a
insertRB a -> a -> Ordering
cmp a
x RB a
s = case RB a -> RB a
ins RB a
s of
T_R RB a
a a
z RB a
b -> RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_B RB a
a a
z RB a
b
RB a
x -> RB a
x
where
ins :: RB a -> RB a
ins RB a
E = RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_R RB a
forall a. RB a
E a
x RB a
forall a. RB a
E
ins s :: RB a
s@(T_B RB a
a a
y RB a
b) = case a -> a -> Ordering
cmp a
x a
y of
Ordering
LT -> RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
lbalance (RB a -> RB a
ins RB a
a) a
y RB a
b
Ordering
GT -> RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
rbalance RB a
a a
y (RB a -> RB a
ins RB a
b)
Ordering
EQ -> RB a
s
ins s :: RB a
s@(T_R RB a
a a
y RB a
b) = case a -> a -> Ordering
cmp a
x a
y of
Ordering
LT -> RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_R (RB a -> RB a
ins RB a
a) a
y RB a
b
Ordering
GT -> RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_R RB a
a a
y (RB a -> RB a
ins RB a
b)
Ordering
EQ -> RB a
s
memberRB :: (a -> a -> Ordering) -> a -> RB a -> Bool
memberRB :: forall a. (a -> a -> Ordering) -> a -> RB a -> Bool
memberRB a -> a -> Ordering
cmp a
x RB a
E = Bool
False
memberRB a -> a -> Ordering
cmp a
x (T_R RB a
a a
y RB a
b) = case a -> a -> Ordering
cmp a
x a
y of
Ordering
LT -> (a -> a -> Ordering) -> a -> RB a -> Bool
forall a. (a -> a -> Ordering) -> a -> RB a -> Bool
memberRB a -> a -> Ordering
cmp a
x RB a
a
Ordering
GT -> (a -> a -> Ordering) -> a -> RB a -> Bool
forall a. (a -> a -> Ordering) -> a -> RB a -> Bool
memberRB a -> a -> Ordering
cmp a
x RB a
b
Ordering
EQ -> Bool
True
memberRB a -> a -> Ordering
cmp a
x (T_B RB a
a a
y RB a
b) = case a -> a -> Ordering
cmp a
x a
y of
Ordering
LT -> (a -> a -> Ordering) -> a -> RB a -> Bool
forall a. (a -> a -> Ordering) -> a -> RB a -> Bool
memberRB a -> a -> Ordering
cmp a
x RB a
a
Ordering
GT -> (a -> a -> Ordering) -> a -> RB a -> Bool
forall a. (a -> a -> Ordering) -> a -> RB a -> Bool
memberRB a -> a -> Ordering
cmp a
x RB a
b
Ordering
EQ -> Bool
True
lbalance, rbalance :: RB a -> a -> RB a -> RB a
lbalance :: forall a. RB a -> a -> RB a -> RB a
lbalance (T_R RB a
a a
x RB a
b) a
y (T_R RB a
c a
z RB a
d) = RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_R (RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_B RB a
a a
x RB a
b) a
y (RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_B RB a
c a
z RB a
d)
lbalance (T_R (T_R RB a
a a
x RB a
b) a
y RB a
c) a
z RB a
d = RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_R (RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_B RB a
a a
x RB a
b) a
y (RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_B RB a
c a
z RB a
d)
lbalance (T_R RB a
a a
x (T_R RB a
b a
y RB a
c)) a
z RB a
d = RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_R (RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_B RB a
a a
x RB a
b) a
y (RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_B RB a
c a
z RB a
d)
lbalance RB a
a a
x RB a
b = RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_B RB a
a a
x RB a
b
rbalance :: forall a. RB a -> a -> RB a -> RB a
rbalance (T_R RB a
a a
x RB a
b) a
y (T_R RB a
c a
z RB a
d) = RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_R (RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_B RB a
a a
x RB a
b) a
y (RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_B RB a
c a
z RB a
d)
rbalance RB a
a a
x (T_R RB a
b a
y (T_R RB a
c a
z RB a
d)) = RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_R (RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_B RB a
a a
x RB a
b) a
y (RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_B RB a
c a
z RB a
d)
rbalance RB a
a a
x (T_R (T_R RB a
b a
y RB a
c) a
z RB a
d) = RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_R (RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_B RB a
a a
x RB a
b) a
y (RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_B RB a
c a
z RB a
d)
rbalance RB a
a a
x RB a
b = RB a -> a -> RB a -> RB a
forall a. RB a -> a -> RB a -> RB a
T_B RB a
a a
x RB a
b
zipWithLongest :: (Maybe a -> Maybe b -> c) -> [a] -> [b] -> [c]
zipWithLongest :: forall a b c. (Maybe a -> Maybe b -> c) -> [a] -> [b] -> [c]
zipWithLongest Maybe a -> Maybe b -> c
f [] [] = []
zipWithLongest Maybe a -> Maybe b -> c
f (a
x:[a]
xs) (b
y:[b]
ys) = Maybe a -> Maybe b -> c
f (a -> Maybe a
forall a. a -> Maybe a
Just a
x) (b -> Maybe b
forall a. a -> Maybe a
Just b
y) c -> [c] -> [c]
forall a. a -> [a] -> [a]
: (Maybe a -> Maybe b -> c) -> [a] -> [b] -> [c]
forall a b c. (Maybe a -> Maybe b -> c) -> [a] -> [b] -> [c]
zipWithLongest Maybe a -> Maybe b -> c
f [a]
xs [b]
ys
zipWithLongest Maybe a -> Maybe b -> c
f [] [b]
ys = (b -> c) -> [b] -> [c]
forall a b. (a -> b) -> [a] -> [b]
map (Maybe a -> Maybe b -> c
f Maybe a
forall a. Maybe a
Nothing (Maybe b -> c) -> (b -> Maybe b) -> b -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> Maybe b
forall a. a -> Maybe a
Just) [b]
ys
zipWithLongest Maybe a -> Maybe b -> c
f [a]
xs [] = (a -> c) -> [a] -> [c]
forall a b. (a -> b) -> [a] -> [b]
map ((Maybe a -> Maybe b -> c
`f` Maybe b
forall a. Maybe a
Nothing) (Maybe a -> c) -> (a -> Maybe a) -> a -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Maybe a
forall a. a -> Maybe a
Just) [a]
xs
compareLength :: (Ord b, Num b, Foldable f) => f a -> b -> Ordering
compareLength :: forall b (f :: * -> *) a.
(Ord b, Num b, Foldable f) =>
f a -> b -> Ordering
compareLength = (a -> (b -> Ordering) -> b -> Ordering)
-> (b -> Ordering) -> f a -> b -> Ordering
forall a b. (a -> b -> b) -> b -> f a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\a
_ b -> Ordering
acc b
n -> if b
n b -> b -> Bool
forall a. Ord a => a -> a -> Bool
> b
0 then b -> Ordering
acc (b
n b -> b -> b
forall a. Num a => a -> a -> a
- b
1) else Ordering
GT) (b -> b -> Ordering
forall a. Ord a => a -> a -> Ordering
compare b
0)
comparingLength :: (Foldable f1, Foldable f2) => f1 a -> f2 b -> Ordering
comparingLength :: forall (f1 :: * -> *) (f2 :: * -> *) a b.
(Foldable f1, Foldable f2) =>
f1 a -> f2 b -> Ordering
comparingLength f1 a
x f2 b
y = [a] -> [b] -> Ordering
forall {a} {a}. [a] -> [a] -> Ordering
go (f1 a -> [a]
forall a. f1 a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList f1 a
x) (f2 b -> [b]
forall a. f2 a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList f2 b
y)
where
go :: [a] -> [a] -> Ordering
go [] [] = Ordering
EQ
go [] (a
_:[a]
_) = Ordering
LT
go (a
_:[a]
_) [] = Ordering
GT
go (a
_:[a]
xs) (a
_:[a]
ys) = [a] -> [a] -> Ordering
go [a]
xs [a]
ys