{-# LANGUAGE CPP #-}
module Test.Speculate.Utils.List
( pairsThat
, count, counts, countsOn, countsBy
, firsts
, nubSort, nubSortBy
, (+++), nubMerge, nubMergeBy, nubMergeOn, nubMerges, nubMergesBy, nubMergeMap
, ordIntersect, ordIntersectBy
, ordered, orderedBy, orderedOn, strictlyOrdered, strictlyOrderedOn
, areAll, areAny
, allLater
, (+-)
, sortOn
, groupOn
, collectOn, collectBy, collectWith, collectSndByFst
, discard, discardLater, discardEarlier, discardOthers, discardByOthers
, allUnique
, chain
, zipWithReverse
, medianate
, takeGreaterHalf
, accum
, partitionByMarkers
, (!)
, halve
)
where
import Data.List
import Data.Function (on)
import Test.LeanCheck.Stats
pairsThat :: (a -> a -> Bool) -> [a] -> [(a,a)]
pairsThat :: forall a. (a -> a -> Bool) -> [a] -> [(a, a)]
pairsThat a -> a -> Bool
p [a]
xs = [(a
x,a
y) | a
x <- [a]
xs, a
y <- [a]
xs, a -> a -> Bool
p a
x a
y]
count :: Eq a => a -> [a] -> Int
count :: forall a. Eq a => a -> [a] -> Int
count a
x = [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([a] -> Int) -> ([a] -> [a]) -> [a] -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==a
x)
firsts :: Eq a => [a] -> [a]
firsts :: forall a. Eq a => [a] -> [a]
firsts [] = []
firsts (a
x:[a]
xs) = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a]
forall a. Eq a => [a] -> [a]
firsts ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
x) [a]
xs)
halve :: [a] -> ([a],[a])
halve :: forall a. [a] -> ([a], [a])
halve [] = ([],[])
halve [a]
xs = (Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
take Int
h [a]
xs, Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
drop Int
h [a]
xs)
where
h :: Int
h = [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
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
nubSortBy :: (a -> a -> Ordering) -> [a] -> [a]
nubSortBy :: forall a. (a -> a -> Ordering) -> [a] -> [a]
nubSortBy a -> a -> Ordering
cmp [a]
xs =
case [a] -> ([a], [a])
forall a. [a] -> ([a], [a])
halve [a]
xs of
([],[a]
zs) -> [a]
zs
([a]
ys,[a]
zs) -> (a -> a -> Ordering) -> [a] -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
nubMergeBy a -> a -> Ordering
cmp ((a -> a -> Ordering) -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a]
nubSortBy a -> a -> Ordering
cmp [a]
ys) ((a -> a -> Ordering) -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a]
nubSortBy a -> a -> Ordering
cmp [a]
zs)
nubMergeBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
nubMergeBy :: forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
nubMergeBy a -> a -> Ordering
cmp (a
x:[a]
xs) (a
y:[a]
ys) = case a
x a -> a -> Ordering
`cmp` a
y of
Ordering
LT -> a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:(a -> a -> Ordering) -> [a] -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
nubMergeBy a -> a -> Ordering
cmp [a]
xs (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ys)
Ordering
GT -> a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:(a -> a -> Ordering) -> [a] -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
nubMergeBy a -> a -> Ordering
cmp (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs) [a]
ys
Ordering
EQ -> a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:(a -> a -> Ordering) -> [a] -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
nubMergeBy a -> a -> Ordering
cmp [a]
xs [a]
ys
nubMergeBy a -> a -> Ordering
_ [a]
xs [a]
ys = [a]
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
ys
nubMergeOn :: Ord b => (a -> b) -> [a] -> [a] -> [a]
nubMergeOn :: forall b a. Ord b => (a -> b) -> [a] -> [a] -> [a]
nubMergeOn a -> b
f = (a -> a -> Ordering) -> [a] -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
nubMergeBy (b -> b -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (b -> b -> Ordering) -> (a -> b) -> a -> a -> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` a -> b
f)
nubMerge :: Ord a => [a] -> [a] -> [a]
nubMerge :: forall a. Ord a => [a] -> [a] -> [a]
nubMerge = (a -> a -> Ordering) -> [a] -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
nubMergeBy a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
(+++) :: Ord a => [a] -> [a] -> [a]
+++ :: forall a. Ord a => [a] -> [a] -> [a]
(+++) = [a] -> [a] -> [a]
forall a. Ord a => [a] -> [a] -> [a]
nubMerge
infixr 5 +++
ordIntersectBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
ordIntersectBy :: forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
ordIntersectBy a -> a -> Ordering
cmp (a
x:[a]
xs) (a
y:[a]
ys) = case a
x a -> a -> Ordering
`cmp` a
y of
Ordering
LT -> (a -> a -> Ordering) -> [a] -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
ordIntersectBy a -> a -> Ordering
cmp [a]
xs (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ys)
Ordering
GT -> (a -> a -> Ordering) -> [a] -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
ordIntersectBy a -> a -> Ordering
cmp (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs) [a]
ys
Ordering
EQ -> a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:(a -> a -> Ordering) -> [a] -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
ordIntersectBy a -> a -> Ordering
cmp [a]
xs [a]
ys
ordIntersectBy a -> a -> Ordering
_ [a]
xs [a]
ys = []
ordIntersect :: Ord a => [a] -> [a] -> [a]
ordIntersect :: forall a. Ord a => [a] -> [a] -> [a]
ordIntersect = (a -> a -> Ordering) -> [a] -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
ordIntersectBy a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
nubMerges :: Ord a => [[a]] -> [a]
nubMerges :: forall a. Ord a => [[a]] -> [a]
nubMerges = (a -> a -> Ordering) -> [[a]] -> [a]
forall a. Ord a => (a -> a -> Ordering) -> [[a]] -> [a]
nubMergesBy a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
nubMergesBy :: Ord a => (a -> a -> Ordering) -> [[a]] -> [a]
nubMergesBy :: forall a. Ord a => (a -> a -> Ordering) -> [[a]] -> [a]
nubMergesBy a -> a -> Ordering
cmp [] = []
nubMergesBy a -> a -> Ordering
cmp [[a]
xs] = [a]
xs
nubMergesBy a -> a -> Ordering
cmp [[a]]
xss = (a -> a -> Ordering) -> [a] -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
nubMergeBy a -> a -> Ordering
cmp ([[a]] -> [a]
forall a. Ord a => [[a]] -> [a]
nubMerges [[a]]
yss) ([[a]] -> [a]
forall a. Ord a => [[a]] -> [a]
nubMerges [[a]]
zss)
where
([[a]]
yss,[[a]]
zss) = [[a]] -> ([[a]], [[a]])
forall a. [a] -> ([a], [a])
splitHalf [[a]]
xss
splitHalf :: [a] -> ([a], [a])
splitHalf [a]
xs = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
splitAt ([a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2) [a]
xs
nubMergeMap :: Ord b => (a -> [b]) -> [a] -> [b]
nubMergeMap :: forall b a. Ord b => (a -> [b]) -> [a] -> [b]
nubMergeMap a -> [b]
f = [[b]] -> [b]
forall a. Ord a => [[a]] -> [a]
nubMerges ([[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
orderedBy :: (a -> a -> Bool) -> [a] -> Bool
orderedBy :: forall a. (a -> a -> Bool) -> [a] -> Bool
orderedBy a -> a -> Bool
(<) (a
x:a
y:[a]
xs) = a
x a -> a -> Bool
< a
y Bool -> Bool -> Bool
&& (a -> a -> Bool) -> [a] -> Bool
forall a. (a -> a -> Bool) -> [a] -> Bool
orderedBy a -> a -> Bool
(<) (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs)
orderedBy a -> a -> Bool
_ [a]
_ = Bool
True
orderedOn :: Ord b => (a -> b) -> [a] -> Bool
orderedOn :: forall b a. Ord b => (a -> b) -> [a] -> Bool
orderedOn a -> b
f = (b -> b -> Bool) -> [b] -> Bool
forall a. (a -> a -> Bool) -> [a] -> Bool
orderedBy b -> b -> Bool
forall a. Ord a => a -> a -> Bool
(<=) ([b] -> Bool) -> ([a] -> [b]) -> [a] -> Bool
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
ordered :: Ord a => [a] -> Bool
ordered :: forall a. Ord a => [a] -> Bool
ordered = (a -> a -> Bool) -> [a] -> Bool
forall a. (a -> a -> Bool) -> [a] -> Bool
orderedBy a -> a -> Bool
forall a. Ord a => a -> a -> Bool
(<=)
strictlyOrderedOn :: Ord b => (a -> b) -> [a] -> Bool
strictlyOrderedOn :: forall b a. Ord b => (a -> b) -> [a] -> Bool
strictlyOrderedOn a -> b
f = (b -> b -> Bool) -> [b] -> Bool
forall a. (a -> a -> Bool) -> [a] -> Bool
orderedBy b -> b -> Bool
forall a. Ord a => a -> a -> Bool
(<) ([b] -> Bool) -> ([a] -> [b]) -> [a] -> Bool
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
strictlyOrdered :: Ord a => [a] -> Bool
strictlyOrdered :: forall a. Ord a => [a] -> Bool
strictlyOrdered = (a -> a -> Bool) -> [a] -> Bool
forall a. (a -> a -> Bool) -> [a] -> Bool
orderedBy a -> a -> Bool
forall a. Ord a => a -> a -> Bool
(<)
areAll :: [a] -> (a -> Bool) -> Bool
[a]
xs areAll :: forall a. [a] -> (a -> Bool) -> Bool
`areAll` a -> Bool
p = (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all a -> Bool
p [a]
xs
areAny :: [a] -> (a -> Bool) -> Bool
[a]
xs areAny :: forall a. [a] -> (a -> Bool) -> Bool
`areAny` a -> Bool
p = (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any a -> Bool
p [a]
xs
allLater :: (a -> a -> Bool) -> [a] -> Bool
allLater :: forall a. (a -> a -> Bool) -> [a] -> Bool
allLater a -> a -> Bool
(<) (a
x:[a]
xs) = (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (a -> a -> Bool
< a
x) [a]
xs Bool -> Bool -> Bool
&& (a -> a -> Bool) -> [a] -> Bool
forall a. (a -> a -> Bool) -> [a] -> Bool
allLater a -> a -> Bool
(<) [a]
xs
allLater a -> a -> Bool
_ [a]
_ = Bool
True
(+-) :: Eq a => [a] -> [a] -> [a]
[a]
xs +- :: forall a. Eq a => [a] -> [a] -> [a]
+- [a]
ys = [a]
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ 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]
xs) [a]
ys
groupOn :: Eq b => (a -> b) -> [a] -> [[a]]
groupOn :: forall b a. Eq b => (a -> b) -> [a] -> [[a]]
groupOn a -> b
f = (a -> a -> Bool) -> [a] -> [[a]]
forall a. (a -> a -> Bool) -> [a] -> [[a]]
groupBy (b -> b -> Bool
forall a. Eq a => a -> a -> Bool
(==) (b -> b -> Bool) -> (a -> b) -> a -> a -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` a -> b
f)
#if __GLASGOW_HASKELL__ < 710
sortOn :: Ord b => (a -> b) -> [a] -> [a]
sortOn f = sortBy (compare `on` f)
#endif
collectOn :: Ord b => (a -> b) -> [a] -> [[a]]
collectOn :: forall b a. Ord b => (a -> b) -> [a] -> [[a]]
collectOn a -> b
f = (a -> b) -> [a] -> [[a]]
forall b a. Eq b => (a -> b) -> [a] -> [[a]]
groupOn a -> b
f ([a] -> [[a]]) -> ([a] -> [a]) -> [a] -> [[a]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b) -> [a] -> [a]
forall b a. Ord b => (a -> b) -> [a] -> [a]
sortOn a -> b
f
collectBy :: (a -> a -> Ordering) -> [a] -> [[a]]
collectBy :: forall a. (a -> a -> Ordering) -> [a] -> [[a]]
collectBy a -> a -> Ordering
cmp = (a -> a -> Bool) -> [a] -> [[a]]
forall a. (a -> a -> Bool) -> [a] -> [[a]]
groupBy a -> a -> Bool
(===) ([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
a
x === :: a -> a -> Bool
=== a
y = a
x a -> a -> Ordering
`cmp` a
y Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
== Ordering
EQ
collectWith :: Ord b
=> (a -> b) -> (a -> c) -> (b -> [c] -> d)
-> [a] -> [d]
collectWith :: forall b a c d.
Ord b =>
(a -> b) -> (a -> c) -> (b -> [c] -> d) -> [a] -> [d]
collectWith a -> b
f a -> c
g b -> [c] -> d
h = ([a] -> d) -> [[a]] -> [d]
forall a b. (a -> b) -> [a] -> [b]
map [a] -> d
collapse
([[a]] -> [d]) -> ([a] -> [[a]]) -> [a] -> [d]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b) -> [a] -> [[a]]
forall b a. Eq b => (a -> b) -> [a] -> [[a]]
groupOn a -> b
f
where
collapse :: [a] -> d
collapse (a
x:[a]
xs) = a -> b
f a
x b -> [c] -> d
`h` (a -> c) -> [a] -> [c]
forall a b. (a -> b) -> [a] -> [b]
map a -> c
g (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs)
collapse [a]
_ = [Char] -> d
forall a. HasCallStack => [Char] -> a
error [Char]
"collectWith: the impossible happened! (see source)"
collectSndByFst :: Ord a => [(a,b)] -> [(a,[b])]
collectSndByFst :: forall a b. Ord a => [(a, b)] -> [(a, [b])]
collectSndByFst = ((a, b) -> a)
-> ((a, b) -> b)
-> (a -> [b] -> (a, [b]))
-> [(a, b)]
-> [(a, [b])]
forall b a c d.
Ord b =>
(a -> b) -> (a -> c) -> (b -> [c] -> d) -> [a] -> [d]
collectWith (a, b) -> a
forall a b. (a, b) -> a
fst (a, b) -> b
forall a b. (a, b) -> b
snd (,)
discard :: (a -> Bool) -> [a] -> [a]
discard :: forall a. (a -> Bool) -> [a] -> [a]
discard a -> Bool
p = (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
p)
discardLater :: (a -> a -> Bool) -> [a] -> [a]
discardLater :: forall a. (a -> a -> Bool) -> [a] -> [a]
discardLater a -> a -> Bool
d [] = []
discardLater a -> a -> Bool
d (a
x:[a]
xs) = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: (a -> a -> Bool) -> [a] -> [a]
forall a. (a -> a -> Bool) -> [a] -> [a]
discardLater a -> a -> Bool
d ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
discard (a -> a -> Bool
`d` a
x) [a]
xs)
discardEarlier :: (a -> a -> Bool) -> [a] -> [a]
discardEarlier :: forall a. (a -> a -> Bool) -> [a] -> [a]
discardEarlier a -> a -> Bool
d = [a] -> [a]
forall a. [a] -> [a]
reverse ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> Bool) -> [a] -> [a]
forall a. (a -> a -> Bool) -> [a] -> [a]
discardLater a -> a -> Bool
d ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
forall a. [a] -> [a]
reverse
discardOthers :: (a -> a -> Bool) -> [a] -> [a]
discardOthers :: forall a. (a -> a -> Bool) -> [a] -> [a]
discardOthers a -> a -> Bool
d = [a] -> [a] -> [a]
dis []
where
dis :: [a] -> [a] -> [a]
dis [a]
xs [] = [a]
xs
dis [a]
xs (a
y:[a]
ys) = [a] -> [a] -> [a]
dis (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:(a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
discard (a -> a -> Bool
`d` a
y) [a]
xs) ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
discard (a -> a -> Bool
`d` a
y) [a]
ys)
discardByOthers :: (a -> [a] -> Bool) -> [a] -> [a]
discardByOthers :: forall a. (a -> [a] -> Bool) -> [a] -> [a]
discardByOthers a -> [a] -> Bool
f = [a] -> [a] -> [a]
d []
where
d :: [a] -> [a] -> [a]
d [a]
xs [] = [a]
xs
d [a]
xs (a
y:[a]
ys) | a -> [a] -> Bool
f a
y ([a]
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
ys) = [a] -> [a] -> [a]
d [a]
xs [a]
ys
| Bool
otherwise = [a] -> [a] -> [a]
d ([a]
xs[a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++[a
y]) [a]
ys
allUnique :: Ord a => [a] -> Bool
allUnique :: forall a. Ord a => [a] -> Bool
allUnique [a]
xs = [a] -> [a]
forall a. Ord a => [a] -> [a]
nubSort [a]
xs [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== [a] -> [a]
forall a. Ord a => [a] -> [a]
sort [a]
xs
chain :: [a -> a] -> a -> a
chain :: forall a. [a -> a] -> a -> a
chain = ((a -> a) -> (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 -> a) -> (a -> a) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
(.) a -> a
forall a. a -> a
id
zipWithReverse :: (a -> a -> b) -> [a] -> [b]
zipWithReverse :: forall a b. (a -> a -> b) -> [a] -> [b]
zipWithReverse a -> a -> b
f [a]
xs = (a -> a -> b) -> [a] -> [a] -> [b]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith a -> a -> b
f [a]
xs ([a] -> [a]
forall a. [a] -> [a]
reverse [a]
xs)
medianate :: (a -> a -> b) -> [a] -> [b]
medianate :: forall a b. (a -> a -> b) -> [a] -> [b]
medianate a -> a -> b
f [a]
xs = (a -> a -> b) -> [a] -> [a] -> [b]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith a -> a -> b
f ([a] -> [a]
forall a. [a] -> [a]
takeGreaterHalf [a]
xs) ([a] -> [a]
forall a. [a] -> [a]
takeGreaterHalf ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ [a] -> [a]
forall a. [a] -> [a]
reverse [a]
xs)
takeGreaterHalf :: [a] -> [a]
takeGreaterHalf :: forall a. [a] -> [a]
takeGreaterHalf [a]
xs = Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
take ((Int -> Int -> Int) -> (Int, Int) -> Int
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) ((Int, Int) -> Int) -> (Int, Int) -> Int
forall a b. (a -> b) -> a -> b
$ [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs Int -> Int -> (Int, Int)
forall a. Integral a => a -> a -> (a, a)
`divMod` Int
2) [a]
xs
accum :: Num a => [a] -> [a]
accum :: forall a. Num a => [a] -> [a]
accum = a -> [a] -> [a]
forall {t}. Num t => t -> [t] -> [t]
a a
0
where
a :: t -> [t] -> [t]
a t
_ [] = []
a t
s (t
x:[t]
xs) = t
st -> t -> t
forall a. Num a => a -> a -> a
+t
x t -> [t] -> [t]
forall a. a -> [a] -> [a]
: t -> [t] -> [t]
a (t
st -> t -> t
forall a. Num a => a -> a -> a
+t
x) [t]
xs
partitionByMarkers :: Eq a => a -> a -> [a] -> ([a],[a])
partitionByMarkers :: forall a. Eq a => a -> a -> [a] -> ([a], [a])
partitionByMarkers a
y a
z [a]
xs =
case (a -> Bool) -> [a] -> ([a], [a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
span (\a
x -> a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
y Bool -> Bool -> Bool
&& a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
/= a
z) [a]
xs of
([a]
ys,[]) -> ([a]
ys,[])
([a]
ys,a
x:[a]
zs)
| a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y -> let ([a]
ys',[a]
zs') = a -> a -> [a] -> ([a], [a])
forall a. Eq a => a -> a -> [a] -> ([a], [a])
partitionByMarkers a
y a
z [a]
zs in ([a]
ys[a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++[a]
ys',[a]
zs')
| a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
z -> let ([a]
zs',[a]
ys') = a -> a -> [a] -> ([a], [a])
forall a. Eq a => a -> a -> [a] -> ([a], [a])
partitionByMarkers a
z a
y [a]
zs in ([a]
ys[a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++[a]
ys',[a]
zs')
| Bool
otherwise -> [Char] -> ([a], [a])
forall a. HasCallStack => [Char] -> a
error [Char]
"partitionByMarkers: the impossible happened, this is definitely a bug. See source."
(!) :: [[a]] -> Int -> [a]
([a]
xs:[[a]]
xss) ! :: forall a. [[a]] -> Int -> [a]
! Int
0 = [a]
xs
([a]
xs:[[a]]
xss) ! Int
n = [[a]]
xss [[a]] -> Int -> [a]
forall a. [[a]] -> Int -> [a]
! (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)
[] ! Int
n = []