{-# LANGUAGE CPP #-}
-- |
-- Module      : Test.Speculate.Utils.List
-- Copyright   : (c) 2016-2019 Rudy Matela
-- License     : 3-Clause BSD  (see the file LICENSE)
-- Maintainer  : Rudy Matela <rudy@matela.com.br>
--
-- This module is part of Speculate.
--
-- Utilities for manipulating lists.
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

-- | @xs +- ys@ superimposes @xs@ over @ys@.
--
-- [1,2,3] +- [0,0,0,0,0,0,0] == [1,2,3,0,0,0,0]
-- [x,y,z] +- [a,b,c,d,e,f,g] == [x,y,z,d,e,f,g]
-- "asdf" +- "this is a test" == "asdf is a test"
(+-) :: 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

-- TODO: rename this to classify!
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)

-- bad name, can't think of something better
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 x y [x,a,b,c,y,d,e,f,x,g] == ([a,b,c,g],[d,e,f])
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."

-- Total version of !! that works on lists of lists (returning [] for index not
-- found).
(!) :: [[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  =  []