-- | Utility functions for lists.
module Mikan.Utils.List
  ( -- * Variants of list case, cons, head, tail, init, last
    replicate'
  , (++!)
  , snoc
  , caseList, caseListM, listCase
  , headWithDefault
  , tailMaybe, tailWithDefault
  , lastMaybe, lastWithDefault
  , last1
  , last2
  , last2'
  , mcons
  , initLast
  , initLast1
  , initLast'
  , initLast1'
  , init1
  , initMaybe
  , initWithDefault
    -- * Iterators
  , asum
  , asum1
    -- * Lookup and indexing
  , (!!!)
  , (!!)
  , indexWithDefault
  , findWithIndex
  , findWithIndex'
  , genericElemIndex
  , downFrom
    -- * Traversals
  , map'
  , map''
  , mapMaybe'
  , concatMap'
  , concat'
    -- * Sublist extraction and partitioning
  , partition'
  , partitionEithers'
  , splitExactlyAt, splitExactlyAt'
  , splitAt'
  , take'
  , takeWhile'
  , break'
  , takeExactly
  , dropEnd
  , spanEnd
  , breakAfter1
  , breakAfter
  , breakJust
  , takeWhileJust
  , spanJust
  , partitionMaybe
  , catMaybe'
  , filterAndRest
  , filter'
  , mapMaybeAndRest
  , dropFrom
  , holes
  , replaceAt'
    -- * Prefix and suffix
    -- ** Prefix
  , Prefix
  , commonPrefix
  , dropCommon
  , stripPrefixBy
    -- ** Suffix
  , Suffix
  , commonSuffix
  , stripSuffix
  , stripReversedSuffix
  , suffixesSatisfying
    -- ** Finding overlap
  , findOverlap
    -- * Chunks
  , chop
  , chopWhen
    -- * Sorting
  , sortOnM
  , sorted
  , allConsecutive
  , mergeStrictlyOrderedBy
    -- * List as a set
  , hasElem
  , distinct
  , fastDistinct
  , duplicates
  , allDuplicates
  , nubAndDuplicatesOn
  , nubOn
  , nubFavouriteOn
  , uniqOn
  , allEqual
  , nubM
    -- * Zipping
  , zip'
  , zipWith'
  , zipWith''
  , zipWithSameLen
  , zipWithKeepRest
  , align
    -- * Unzipping
  , unzipWith
    -- * Edit Distance
  , editDistance
    -- * Reexports
  , module X
  ) where

-- Reexports

import Data.List as X (uncons)

-- Regular imports

import Prelude hiding ((!!))

import Control.Monad (filterM, forM)
import Control.Applicative (Alternative, (<|>))
import Control.Applicative qualified as A

import Data.Array (Array, array, listArray)
import Data.Array qualified as Array
import Data.Bifunctor
import Data.Containers.ListUtils qualified as List
import Data.Function (on)
import Data.Hashable
import Data.List.Split (splitOn)
import Data.List qualified as List
import Data.List.NonEmpty qualified as List1
import Data.List.NonEmpty (pattern (:|), (<|))
import Data.Maybe
import Data.Map qualified as Map
import Data.Map.Strict qualified as SMap
import Data.HashMap.Strict qualified as HMap
import Data.Set qualified as Set
import Data.Strict.These
import Data.Strict.Tuple (Pair(..))

import Mikan.Utils.CallStack.Base
import Mikan.Utils.Function (applyWhen)
import Mikan.Utils.Functor  ((<.>))

import {-# SOURCE #-} Mikan.Utils.List1 (List1)

import Mikan.Utils.Impossible

---------------------------------------------------------------------------
-- Variants of list case, cons, head, tail, init, last
---------------------------------------------------------------------------

-- | \(\mathcal{O}(n)\). Spine-strict 'replicate'.
replicate' :: Int -> a -> [a]
replicate' :: forall a. Int -> a -> [a]
replicate' Int
n a
x
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = []
  | Bool
otherwise = let !xs :: [a]
xs = Int -> a -> [a]
forall a. Int -> a -> [a]
replicate' (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) a
x in a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
xs

infixr 5 ++!
-- | \(\mathcal{O}(n)\). Spine-strict '++'.
(++!) :: [a] -> [a] -> [a]
++! :: forall a. [a] -> [a] -> [a]
(++!) ![a]
xs [] = [a]
xs
(++!)  [a]
xs [a]
ys = [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
go [a]
xs [a]
ys where
  go :: [a] -> [a] -> [a]
go []     [a]
ys = [a]
ys
  go (a
x:[a]
xs) [a]
ys = let !res :: [a]
res = [a] -> [a] -> [a]
go [a]
xs [a]
ys in a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
res

-- | \(\mathcal{O}(n)\). Append a single element at the end.
--
-- This function should be avoided, even if the lists are very short.
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]

-- | \(\mathcal{O}(1)\). Case distinction for lists, with list first.
--
-- Cf. 'Mikan.Utils.Null.ifNull'.
caseList :: [a] -> b -> (a -> [a] -> b) -> b
caseList :: forall a b. [a] -> b -> (a -> [a] -> b) -> b
caseList [a]
xs b
n a -> [a] -> b
c = b -> (a -> [a] -> b) -> [a] -> b
forall b a. b -> (a -> [a] -> b) -> [a] -> b
listCase b
n a -> [a] -> b
c [a]
xs

-- | \(\mathcal{O}(1)\). Case distinction for lists, with list first.
--
-- Cf. 'Mikan.Utils.Null.ifNull'.
caseListM :: Monad m => m [a] -> m b -> (a -> [a] -> m b) -> m b
caseListM :: forall (m :: * -> *) a b.
Monad m =>
m [a] -> m b -> (a -> [a] -> m b) -> m b
caseListM m [a]
mxs m b
n a -> [a] -> m b
c = m b -> (a -> [a] -> m b) -> [a] -> m b
forall b a. b -> (a -> [a] -> b) -> [a] -> b
listCase m b
n a -> [a] -> m b
c ([a] -> m b) -> m [a] -> m b
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< m [a]
mxs

-- | \(\mathcal{O}(1)\). Case distinction for lists, with list last.
listCase :: b -> (a -> [a] -> b) -> [a] -> b
listCase :: forall b a. b -> (a -> [a] -> b) -> [a] -> b
listCase b
n a -> [a] -> b
c []     = b
n
listCase b
n a -> [a] -> b
c (a
x:[a]
xs) = a -> [a] -> b
c a
x [a]
xs

-- | \(\mathcal{O}(1)\). Head function (safe). Returns a default value on empty lists.
--
-- ==== __Examples__
--
-- >>> headWithDefault 42 []
-- 42
-- >>> headWithDefault 42 [1,2,3]
-- 1
headWithDefault :: a -> [a] -> a
headWithDefault :: forall a. a -> [a] -> a
headWithDefault a
def = a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe a
def (Maybe a -> a) -> ([a] -> Maybe a) -> [a] -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Maybe a
forall a. [a] -> Maybe a
listToMaybe

-- | \(\mathcal{O}(1)\). Safe variant of 'tail'.
tailMaybe :: [a] -> Maybe [a]
tailMaybe :: forall a. [a] -> Maybe [a]
tailMaybe = ((a, [a]) -> [a]) -> Maybe (a, [a]) -> Maybe [a]
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (a, [a]) -> [a]
forall a b. (a, b) -> b
snd (Maybe (a, [a]) -> Maybe [a])
-> ([a] -> Maybe (a, [a])) -> [a] -> Maybe [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Maybe (a, [a])
forall a. [a] -> Maybe (a, [a])
uncons

-- | \(\mathcal{O}(1)\). Safe variant of 'tail'.
-- Returns a default list on empty lists.
tailWithDefault :: [a] -> [a] -> [a]
tailWithDefault :: forall a. [a] -> [a] -> [a]
tailWithDefault [a]
def = [a] -> Maybe [a] -> [a]
forall a. a -> Maybe a -> a
fromMaybe [a]
def (Maybe [a] -> [a]) -> ([a] -> Maybe [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Maybe [a]
forall a. [a] -> Maybe [a]
tailMaybe

-- | \(\mathcal{O}(n)\). Safe variant of 'last'.
--
-- This function should be avoided when used inside of recursive functions.
-- If you find yourself reaching for 'lastMaybe', use a reversed
-- list as the accumulator.
lastMaybe :: [a] -> Maybe a
lastMaybe :: forall a. [a] -> Maybe a
lastMaybe = \case
  []   -> Maybe a
forall a. Maybe a
Nothing
  a
x:[a]
xs -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> a -> Maybe a
forall a b. (a -> b) -> a -> b
$ a -> [a] -> a
forall a. a -> [a] -> a
last1 a
x [a]
xs

-- | \(\mathcal{O}(n)\). Safe variant of 'last'.
-- Returns a default list on empty lists.
--
-- This function should be avoided when used inside of recursive functions.
-- If you find yourself reaching for 'lastWithDefault', use a reversed
-- list as the accumulator.
lastWithDefault :: a -> [a] -> a
lastWithDefault :: forall a. a -> [a] -> a
lastWithDefault = a -> [a] -> a
forall a. a -> [a] -> a
last1

-- | \(\mathcal{O}(n)\). Last element of non-empty list.
-- This function is safe.
--
-- ==== __Laws__
--
-- > last1 a as = last (a : as)
last1 :: a -> [a] -> a
last1 :: forall a. a -> [a] -> a
last1 a
a = \case
  [] -> a
a
  a
b:[a]
bs -> a -> [a] -> a
forall a. a -> [a] -> a
last1 a
b [a]
bs

-- | \(\mathcal{O}(n)\). Last two elements.
-- This function is safe.
last2 :: [a] -> Maybe (a, a)
last2 :: forall a. [a] -> Maybe (a, a)
last2 (a
x : a
y : [a]
xs) = (a, a) -> Maybe (a, a)
forall a. a -> Maybe a
Just ((a, a) -> Maybe (a, a)) -> (a, a) -> Maybe (a, a)
forall a b. (a -> b) -> a -> b
$ a -> a -> [a] -> (a, a)
forall a. a -> a -> [a] -> (a, a)
last2' a
x a
y [a]
xs
last2 [a]
_ = Maybe (a, a)
forall a. Maybe a
Nothing

-- | \(\mathcal{O}(n)\). @last2' x y zs@ computes the last two elements of @x:y:zs@.
last2' :: a -> a -> [a] -> (a, a)
last2' :: forall a. a -> a -> [a] -> (a, a)
last2' a
x a
y = \case
  []  -> (a
x, a
y)
  a
z:[a]
zs -> a -> a -> [a] -> (a, a)
forall a. a -> a -> [a] -> (a, a)
last2' a
y a
z [a]
zs

-- | \(\mathcal{O}(1)\). Maybe cons.
--
-- @mcons ma as = maybeToList ma ++ as@
mcons :: Maybe a -> [a] -> [a]
mcons :: forall a. Maybe a -> [a] -> [a]
mcons Maybe a
ma [a]
as = [a] -> (a -> [a]) -> Maybe a -> [a]
forall b a. b -> (a -> b) -> Maybe a -> b
maybe [a]
as (a -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
as) Maybe a
ma

-- | \(\mathcal{O}(n)\). 'init' and 'last' in one go.
-- This function is safe.
initLast :: [a] -> Maybe ([a],a)
initLast :: forall a. [a] -> Maybe ([a], a)
initLast []     = Maybe ([a], a)
forall a. Maybe a
Nothing
initLast (a
a:[a]
as) = ([a], a) -> Maybe ([a], a)
forall a. a -> Maybe a
Just (([a], a) -> Maybe ([a], a)) -> ([a], a) -> Maybe ([a], a)
forall a b. (a -> b) -> a -> b
$ a -> [a] -> ([a], a)
forall a. a -> [a] -> ([a], a)
initLast1 a
a [a]
as

-- | \(\mathcal{O}(n)\). 'init' and 'last' of non-empty list, safe.
--
-- @initLast1 a as = (init (a:as), last (a:as)@
initLast1 :: a -> [a] -> ([a], a)
initLast1 :: forall a. a -> [a] -> ([a], a)
initLast1 a
a = \case
  []   -> ([], a
a)
  a
b:[a]
bs -> ([a] -> [a]) -> ([a], a) -> ([a], a)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (a
aa -> [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. a -> [a] -> ([a], a)
initLast1 a
b [a]
bs

-- | \(\mathcal{O}(n)\). Spine-strict 'initLast'.
initLast' :: forall a. [a] -> Maybe ([a],a)
initLast' :: forall a. [a] -> Maybe ([a], a)
initLast' []     = Maybe ([a], a)
forall a. Maybe a
Nothing
initLast' (a
a:[a]
as) = ([a], a) -> Maybe ([a], a)
forall a. a -> Maybe a
Just (([a], a) -> Maybe ([a], a)) -> ([a], a) -> Maybe ([a], a)
forall a b. (a -> b) -> a -> b
$! a -> [a] -> ([a], a)
forall a. a -> [a] -> ([a], a)
initLast1' a
a [a]
as

-- | \(\mathcal{O}(n)\). Spine-strict 'initLast1'.
initLast1' :: a -> [a] -> ([a], a)
initLast1' :: forall a. a -> [a] -> ([a], a)
initLast1' a
a = \case
  []   -> ([], a
a)
  a
b:[a]
bs -> case a -> [a] -> ([a], a)
forall a. a -> [a] -> ([a], a)
initLast1' a
b [a]
bs of (![a]
bs, a
b) -> (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
bs, a
b)

-- | \(\mathcal{O}(n)\). 'init' of non-empty list.
-- This function is safe.
--
-- @init1 a as = init (a:as)@
init1 :: a -> [a] -> [a]
init1 :: forall a. a -> [a] -> [a]
init1 a
a = \case
  []   -> []
  a
b:[a]
bs -> a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: a -> [a] -> [a]
forall a. a -> [a] -> [a]
init1 a
b [a]
bs

-- | \(\mathcal{O}(n)\). @init@.
-- This function is safe.
initMaybe :: [a] -> Maybe [a]
initMaybe :: forall a. [a] -> Maybe [a]
initMaybe = \case
  []   -> Maybe [a]
forall a. Maybe a
Nothing
  a
a:[a]
as -> [a] -> Maybe [a]
forall a. a -> Maybe a
Just ([a] -> Maybe [a]) -> [a] -> Maybe [a]
forall a b. (a -> b) -> a -> b
$ a -> [a] -> [a]
forall a. a -> [a] -> [a]
init1 a
a [a]
as

-- | \(\mathcal{O}(n)\). @init@.
-- This function is safe.
initWithDefault :: [a] -> [a] -> [a]
initWithDefault :: forall a. [a] -> [a] -> [a]
initWithDefault [a]
as []     = [a]
as
initWithDefault [a]
_  (a
a:[a]
as) = a -> [a] -> [a]
forall a. a -> [a] -> [a]
init1 a
a [a]
as

---------------------------------------------------------------------------
-- Iterators
---------------------------------------------------------------------------

-- | \(\mathcal{O}(n)\). A version of 'Foldable.asum' that avoids a final 'A.empty'.
-- It is right-folding just like 'Foldable.asum'.
--
-- Precondition: the right-unit law holds, i.e. @m \<|\> A.empty = m@.
asum :: Alternative m => [m a] -> m a
asum :: forall (m :: * -> *) a. Alternative m => [m a] -> m a
asum []     = m a
forall a. m a
forall (f :: * -> *) a. Alternative f => f a
A.empty
asum (m a
x:[m a]
xs) = m a -> [m a] -> m a
forall (m :: * -> *) a. Alternative m => m a -> [m a] -> m a
asum1 m a
x [m a]
xs

-- | \(\mathcal{O}(n)\). A right-folding 'Foldable.asum' for nonempty lists,
-- never producing 'A.empty'.
asum1 :: Alternative m => m a -> [m a] -> m a
asum1 :: forall (m :: * -> *) a. Alternative m => m a -> [m a] -> m a
asum1 m a
x []     = m a
x
asum1 m a
x (m a
y:[m a]
ys) = m a
x m a -> m a -> m a
forall a. m a -> m a -> m a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> m a -> [m a] -> m a
forall (m :: * -> *) a. Alternative m => m a -> [m a] -> m a
asum1 m a
y [m a]
ys

---------------------------------------------------------------------------
-- Lookup and indexing
---------------------------------------------------------------------------

-- | \(\mathcal{O}(\min(n, i))\). Lookup an element in a list.
(!!!) :: [a] -> Int -> Maybe a
[a]
xs !!! :: forall a. [a] -> Int -> Maybe a
!!! (!Int
i)
  | Int
i 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
forall {t} {a}. (Eq t, Num t) => [a] -> t -> Maybe a
index [a]
xs Int
i
  where
  index :: [a] -> t -> Maybe a
index []       !t
i = Maybe a
forall a. Maybe a
Nothing
  index (a
x : [a]
xs) t
0  = a -> Maybe a
forall a. a -> Maybe a
Just a
x
  index (a
x : [a]
xs) t
i  = [a] -> t -> Maybe a
index [a]
xs (t
i t -> t -> t
forall a. Num a => a -> a -> a
- t
1)

-- | A variant of 'Prelude.!!' that might provide more informative
-- error messages if the index is out of bounds.
--
-- Precondition: The index should not be out of bounds.
(!!) :: HasCallStack => [a] -> Int -> a
[a]
xs !! :: forall a. HasCallStack => [a] -> Int -> a
!! Int
i = case [a]
xs [a] -> Int -> Maybe a
forall a. [a] -> Int -> Maybe a
!!! Int
i of
  Just a
x  -> a
x
  Maybe a
Nothing -> a
forall a. HasCallStack => a
__IMPOSSIBLE__

-- | \(\mathcal{O}(\min(n, i))\). Lookup function with default value for index out of range.
indexWithDefault :: a -> [a] -> Int -> a
indexWithDefault :: forall a. a -> [a] -> Int -> a
indexWithDefault a
a []       Int
_ = a
a
indexWithDefault a
a (a
x : [a]
_)  Int
0 = a
x
indexWithDefault a
a (a
_ : [a]
xs) Int
n = a -> [a] -> Int -> a
forall a. a -> [a] -> Int -> a
indexWithDefault a
a [a]
xs (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)

-- | \(\mathcal{O}(n)\). Find the first element satisfying a predicate and return it with its index.
findWithIndex :: (a -> Bool) -> [a] -> Maybe (a, Int)
findWithIndex :: forall a. (a -> Bool) -> [a] -> Maybe (a, Int)
findWithIndex a -> Bool
p = Int -> [a] -> Maybe (a, Int)
loop Int
0
  where
    loop :: Int -> [a] -> Maybe (a, Int)
loop Int
i [] = Maybe (a, Int)
forall a. Maybe a
Nothing
    loop !Int
i (a
x:[a]
xs)
      | a -> Bool
p a
x = (a, Int) -> Maybe (a, Int)
forall a. a -> Maybe a
Just (a
x, Int
i)
      | Bool
otherwise = Int -> [a] -> Maybe (a, Int)
loop (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) [a]
xs

{-# INLINE findWithIndex' #-}
-- | \(\mathcal{O}(n)\). Variant of 'findWithIndex' that returns a CPS'd Maybe result for
-- more reliable inlining.
findWithIndex' :: forall a b. (a -> Bool) -> [a] -> b -> (a -> Int -> b) -> b
findWithIndex' :: forall a b. (a -> Bool) -> [a] -> b -> (a -> Int -> b) -> b
findWithIndex' a -> Bool
f [a]
as b
notfound a -> Int -> b
found = Int -> [a] -> b
go Int
0 [a]
as where
  go :: Int -> [a] -> b
  go :: Int -> [a] -> b
go !Int
i [] = b
notfound
  go Int
i (a
a:[a]
as) | a -> Bool
f a
a       = a -> Int -> b
found a
a Int
i
              | Bool
otherwise = Int -> [a] -> b
go (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) [a]
as

-- | \(\mathcal{O}(n)\). A generalised variant of 'Data.List.elemIndex'.
genericElemIndex :: (Eq a, Integral i) => a -> [a] -> Maybe i
genericElemIndex :: forall a i. (Eq a, Integral i) => a -> [a] -> Maybe i
genericElemIndex a
x [a]
xs =
  [i] -> Maybe i
forall a. [a] -> Maybe a
listToMaybe ([i] -> Maybe i) -> [i] -> Maybe i
forall a b. (a -> b) -> a -> b
$
  ((i, Bool) -> i) -> [(i, Bool)] -> [i]
forall a b. (a -> b) -> [a] -> [b]
map (i, Bool) -> i
forall a b. (a, b) -> a
fst ([(i, Bool)] -> [i]) -> [(i, Bool)] -> [i]
forall a b. (a -> b) -> a -> b
$
  ((i, Bool) -> Bool) -> [(i, Bool)] -> [(i, Bool)]
forall a. (a -> Bool) -> [a] -> [a]
filter (i, Bool) -> Bool
forall a b. (a, b) -> b
snd ([(i, Bool)] -> [(i, Bool)]) -> [(i, Bool)] -> [(i, Bool)]
forall a b. (a -> b) -> a -> b
$
  [i] -> [Bool] -> [(i, Bool)]
forall a b. [a] -> [b] -> [(a, b)]
zip [i
0..] ([Bool] -> [(i, Bool)]) -> [Bool] -> [(i, Bool)]
forall a b. (a -> b) -> a -> b
$
  (a -> Bool) -> [a] -> [Bool]
forall a b. (a -> b) -> [a] -> [b]
map (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
x) [a]
xs

-- | \(\mathcal{O}(n)\). Return a descending list of numbers.
-- This function is spine-strict.
--
-- ==== __Laws__
--
-- > downFrom n = [n-1,..1,0]
downFrom :: Integral a => a -> [a]
downFrom :: forall a. Integral a => a -> [a]
downFrom a
n | a
n a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
0    = []
           | Bool
otherwise = let !n' :: a
n' = a
na -> a -> a
forall a. Num a => a -> a -> a
-a
1 in (a
n' a -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$! a -> [a]
forall a. Integral a => a -> [a]
downFrom a
n'

---------------------------------------------------------------------------
-- Traversals
---------------------------------------------------------------------------

{-# INLINE map' #-}
-- | \(\mathcal{O}(n)\). Strict map.
map' :: (a -> b) -> [a] -> [b]
map' :: forall a b. (a -> b) -> [a] -> [b]
map' a -> b
f = [a] -> [b]
go where
  go :: [a] -> [b]
go []     = []
  go (a
a:[a]
as) = let !b :: b
b = a -> b
f a
a; !bs :: [b]
bs = [a] -> [b]
go [a]
as in b
bb -> [b] -> [b]
forall a. a -> [a] -> [a]
:[b]
bs

{-# INLINE map'' #-}
-- | \(\mathcal{O}(n)\). Spine-strict map.
map'' :: (a -> b) -> [a] -> [b]
map'' :: forall a b. (a -> b) -> [a] -> [b]
map'' a -> b
f = [a] -> [b]
go where
  go :: [a] -> [b]
go []     = []
  go (a
a:[a]
as) = let !bs :: [b]
bs = [a] -> [b]
go [a]
as in a -> b
f a
ab -> [b] -> [b]
forall a. a -> [a] -> [a]
:[b]
bs

{-# INLINE mapMaybe' #-}
-- | \(\mathcal{O}(n)\). Strict 'mapMaybe'.
mapMaybe' :: (a -> Maybe b) -> [a] -> [b]
mapMaybe' :: forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe' a -> Maybe b
f = [a] -> [b]
go where
  go :: [a] -> [b]
go [] = []
  go (a
a:[a]
as) = case a -> Maybe b
f a
a of
    Maybe b
Nothing -> [a] -> [b]
go [a]
as
    Just !b
b -> (b
bb -> [b] -> [b]
forall a. a -> [a] -> [a]
:) ([b] -> [b]) -> [b] -> [b]
forall a b. (a -> b) -> a -> b
$! [a] -> [b]
go [a]
as

{-# INLINE concatMap' #-}
-- | \(\mathcal{O}(n)\). Strict 'concatMap'
concatMap' :: (a -> [b]) -> [a] -> [b]
concatMap' :: forall a b. (a -> [b]) -> [a] -> [b]
concatMap' a -> [b]
f = [a] -> [b]
go where
  go :: [a] -> [b]
go []     = []
  go (a
a:[a]
as) = a -> [b]
f a
a [b] -> [b] -> [b]
forall a. [a] -> [a] -> [a]
++! [a] -> [b]
go [a]
as

-- | \(\mathcal{O}(n)\). Strict 'concat'.
concat' :: [[a]] -> [a]
concat' :: forall a. [[a]] -> [a]
concat' = ([a] -> [a]) -> [[a]] -> [a]
forall a b. (a -> [b]) -> [a] -> [b]
concatMap' [a] -> [a]
forall a. a -> a
id

---------------------------------------------------------------------------
-- Sublist extraction and partitioning
---------------------------------------------------------------------------

{-# INLINE partition' #-}
-- | \(\mathcal{O}(n)\). Strict 'Data.List.partition'.
partition' :: (a -> Bool) -> [a] -> ([a], [a])
partition' :: forall a. (a -> Bool) -> [a] -> ([a], [a])
partition' a -> Bool
f = [a] -> ([a], [a])
go where
  go :: [a] -> ([a], [a])
go []     = ([], [])
  go (a
a:[a]
as) = case [a] -> ([a], [a])
go [a]
as of
    (![a]
xs, ![a]
ys) -> if a -> Bool
f a
a then (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs, [a]
ys) else ([a]
xs, a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ys)

-- | \(\mathcal{O}(n)\). Strict 'Data.Either.partitionEithers'.
partitionEithers' :: [Either a b] -> ([a], [b])
partitionEithers' :: forall a b. [Either a b] -> ([a], [b])
partitionEithers' [] = ([], [])
partitionEithers' (Left a
a:[Either a b]
abs) = case [Either a b] -> ([a], [b])
forall a b. [Either a b] -> ([a], [b])
partitionEithers' [Either a b]
abs of
  (![a]
as, ![b]
bs) -> (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
as, [b]
bs)
partitionEithers' (Right b
b:[Either a b]
abs) = case [Either a b] -> ([a], [b])
forall a b. [Either a b] -> ([a], [b])
partitionEithers' [Either a b]
abs of
  (![a]
as, ![b]
bs) -> ([a]
as, b
bb -> [b] -> [b]
forall a. a -> [a] -> [a]
:[b]
bs)

type Prefix a = [a]  -- ^ The list before the split point.
type Suffix a = [a]  -- ^ The list after the split point.

-- | \(\mathcal{O}(n)\). Split a list at some index.
-- If the index is out of bounds, return 'Nothing'.
--
-- ==== __Laws__
--
-- @splitExactlyAt n xs = Just (ys, zs)@ iff @xs = ys ++ zs@
-- and @genericLength ys = n@.
splitExactlyAt :: Integral n => n -> [a] -> Maybe (Prefix a, Suffix a)
splitExactlyAt :: forall n a. Integral n => n -> [a] -> Maybe ([a], [a])
splitExactlyAt n
0 [a]
xs       = ([a], [a]) -> Maybe ([a], [a])
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return ([], [a]
xs)
splitExactlyAt n
n []       = Maybe ([a], [a])
forall a. Maybe a
Nothing
splitExactlyAt n
n (a
x : [a]
xs) = ([a] -> [a]) -> ([a], [a]) -> ([a], [a])
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (a
x a -> [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
<$> n -> [a] -> Maybe ([a], [a])
forall n a. Integral n => n -> [a] -> Maybe ([a], [a])
splitExactlyAt (n
nn -> n -> n
forall a. Num a => a -> a -> a
-n
1) [a]
xs

-- | \(\mathcal{O}(n)\). Spine-strict 'splitExactlyAt'.
splitExactlyAt' :: Int -> [a] -> Maybe (Prefix a, Suffix a)
splitExactlyAt' :: forall a. Int -> [a] -> Maybe ([a], [a])
splitExactlyAt' Int
n ![a]
xs
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = ([a], [a]) -> Maybe ([a], [a])
forall a. a -> Maybe a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ([], [a]
xs)
splitExactlyAt' Int
n [] = Maybe ([a], [a])
forall a. Maybe a
Nothing
splitExactlyAt' Int
n (a
x:[a]
xs) = case Int -> [a] -> Maybe ([a], [a])
forall a. Int -> [a] -> Maybe ([a], [a])
splitExactlyAt' (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) [a]
xs of
  Just ([a]
as, [a]
bs) -> ([a], [a]) -> Maybe ([a], [a])
forall a. a -> Maybe a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
as, [a]
bs)
  Maybe ([a], [a])
Nothing       -> Maybe ([a], [a])
forall a. Maybe a
Nothing

-- | \(\mathcal{O}(n)\). Spine-strict splitAt.
splitAt' :: Int -> [a] -> ([a], [a])
splitAt' :: forall a. Int -> [a] -> ([a], [a])
splitAt' Int
n ![a]
as | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = ([], [a]
as)
splitAt' Int
n []           = ([], [])
splitAt' Int
n (a
a:[a]
as)       = case Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
splitAt' (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) [a]
as of ([a]
as, [a]
as') -> (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
as, [a]
as')

-- | \(\mathcal{O}(n)\). Spine-strict 'take'.
take' :: Int -> [a] -> [a]
take' :: forall a. Int -> [a] -> [a]
take' Int
n ![a]
as | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = []
take' Int
n []           = []
take' Int
n (a
a:[a]
as)       = (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$! Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
take' (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) [a]
as

{-# INLINE takeWhile' #-}
-- | \(\mathcal{O}(n)\). Strict 'takeWhile'.
takeWhile' :: (a -> Bool) -> [a] -> [a]
takeWhile' :: forall a. (a -> Bool) -> [a] -> [a]
takeWhile' a -> Bool
f = [a] -> [a]
go where
  go :: [a] -> [a]
go [] = []
  go (!a
a:[a]
as) | a -> Bool
f a
a       = (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$! [a] -> [a]
go [a]
as
             | Bool
otherwise = []

{-# INLINE break' #-}
-- | \(\mathcal{O}(n)\). Strict 'break'.
break' :: (a -> Bool) -> [a] -> ([a],[a])
break' :: forall a. (a -> Bool) -> [a] -> ([a], [a])
break' a -> Bool
p = [a] -> ([a], [a])
go where
  go :: [a] -> ([a], [a])
go xs :: [a]
xs@[] =  ([a]
xs, [a]
xs)
  go xs :: [a]
xs@(!a
x:[a]
xs')
    | a -> Bool
p a
x        =  ([],[a]
xs)
    | Bool
otherwise  =  case [a] -> ([a], [a])
go [a]
xs' of ([a]
ys,[a]
zs) -> (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ys,[a]
zs)

-- | \(\mathcal{O}(n)\). @takeExactly x n xs@ takes @n@
-- elements from @xs@, padding with @x@ if we reach the end of the
-- list.
--
-- ==== __Laws__
--
-- > takeExactly x n xs == take n (xs ++ repeat x)
{-# SPECIALIZE takeExactly :: a -> Int -> [a] -> [a] #-}
takeExactly :: forall a n. Integral n => a -> n -> [a] -> [a]
takeExactly :: forall a n. Integral n => a -> n -> [a] -> [a]
takeExactly a
a = n -> [a] -> [a]
go
  where
    go :: n -> [a] -> [a]
go n
n
      | n
n n -> n -> Bool
forall a. Ord a => a -> a -> Bool
<= n
0    = [a] -> [a] -> [a]
forall a b. a -> b -> a
const []
      | Bool
otherwise = \case
          []   -> n -> a -> [a]
forall i a. Integral i => i -> a -> [a]
List.genericReplicate n
n a
a
          a
x:[a]
xs -> a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: n -> [a] -> [a]
go (n
n n -> n -> n
forall a. Num a => a -> a -> a
- n
1) [a]
xs

-- | \(\mathcal{O}(n)\). Drop from the end of a list.
-- Forces the whole list even for @n==0@.
--
-- ==== __Laws__
--
-- > dropEnd n = reverse . drop n . reverse
dropEnd :: forall a. Int -> [a] -> Prefix a
dropEnd :: forall a. Int -> [a] -> [a]
dropEnd Int
n = (Int, Prefix a) -> Prefix a
forall a b. (a, b) -> b
snd ((Int, Prefix a) -> Prefix a)
-> (Prefix a -> (Int, Prefix a)) -> Prefix a -> Prefix a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> (Int, Prefix a) -> (Int, Prefix a))
-> (Int, Prefix a) -> Prefix a -> (Int, Prefix 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 -> (Int, Prefix a) -> (Int, Prefix a)
f (Int
n, [])
  where
  f :: a -> (Int, [a]) -> (Int, [a])
  f :: a -> (Int, Prefix a) -> (Int, Prefix a)
f a
x (Int
n, Prefix a
xs) = (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1, Bool -> (Prefix a -> Prefix a) -> Prefix a -> Prefix a
forall b a. IsBool b => b -> (a -> a) -> a -> a
applyWhen (Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0) (a
xa -> Prefix a -> Prefix a
forall a. a -> [a] -> [a]
:) Prefix a
xs)

-- | \(\mathcal{O}(n)\). Split off the largest suffix whose elements satisfy a predicate.
--
-- ==== __Laws__
--
-- > all p ys && maybe True (not . p) (lastMaybe xs) ==> spanEnd p (xs, zs) = (xs, ys)
spanEnd :: forall a. (a -> Bool) -> [a] -> (Prefix a, Suffix a)
spanEnd :: forall a. (a -> Bool) -> [a] -> ([a], [a])
spanEnd a -> Bool
p = (Bool, (Prefix a, Prefix a)) -> (Prefix a, Prefix a)
forall a b. (a, b) -> b
snd ((Bool, (Prefix a, Prefix a)) -> (Prefix a, Prefix a))
-> (Prefix a -> (Bool, (Prefix a, Prefix a)))
-> Prefix a
-> (Prefix a, Prefix a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> (Bool, (Prefix a, Prefix a)) -> (Bool, (Prefix a, Prefix a)))
-> (Bool, (Prefix a, Prefix a))
-> Prefix a
-> (Bool, (Prefix a, Prefix 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 -> (Bool, (Prefix a, Prefix a)) -> (Bool, (Prefix a, Prefix a))
f (Bool
True, ([], []))
  where
  f :: a -> (Bool, ([a], [a])) -> (Bool, ([a], [a]))
  f :: a -> (Bool, (Prefix a, Prefix a)) -> (Bool, (Prefix a, Prefix a))
f a
x (Bool
b', (Prefix a
xs, Prefix a
ys)) = (Bool
b, if Bool
b then (Prefix a
xs, a
xa -> Prefix a -> Prefix a
forall a. a -> [a] -> [a]
:Prefix a
ys) else (a
xa -> Prefix a -> Prefix a
forall a. a -> [a] -> [a]
:Prefix a
xs, Prefix a
ys))
    where b :: Bool
b = Bool
b' Bool -> Bool -> Bool
&& a -> Bool
p a
x

-- | \(\mathcal{O}(n)\). Breaks a non-empty list just /after/ an element satisfying the predicate is
--   found.
--
-- ==== __Examples__
--
-- >>> breakAfter1 even 1 [3,5,2,4,7,8]
-- (1 :| [3,5,2],[4,7,8])
breakAfter1 :: (a -> Bool) -> a -> [a] -> (List1 a, [a])
breakAfter1 :: forall a. (a -> Bool) -> a -> [a] -> (List1 a, [a])
breakAfter1 a -> Bool
p = a -> [a] -> (NonEmpty a, [a])
loop
  where
  loop :: a -> [a] -> (NonEmpty a, [a])
loop a
x = \case
    xs :: [a]
xs@[]         -> (a
x a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [], [a]
xs)
    xs :: [a]
xs@(a
y : [a]
ys)
      | a -> Bool
p a
x       -> (a
x a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [], [a]
xs)
      | Bool
otherwise -> let (NonEmpty a
vs, [a]
ws) = a -> [a] -> (NonEmpty a, [a])
loop a
y [a]
ys in (a
x a -> NonEmpty a -> NonEmpty a
forall a. a -> NonEmpty a -> NonEmpty a
<| NonEmpty a
vs, [a]
ws)

-- | Breaks a list just /after/ an element satisfying the predicate is
-- found.
--
-- ==== __Examples__
--
-- >>> breakAfter even [1,3,5,2,4,7,8]
-- ([1,3,5,2],[4,7,8])
breakAfter :: (a -> Bool) -> [a] -> ([a], [a])
breakAfter :: forall a. (a -> Bool) -> [a] -> ([a], [a])
breakAfter a -> Bool
p = \case
  []   -> ([], [])
  a
x:[a]
xs -> (NonEmpty a -> [a]) -> (NonEmpty a, [a]) -> ([a], [a])
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
List1.toList ((NonEmpty a, [a]) -> ([a], [a]))
-> (NonEmpty a, [a]) -> ([a], [a])
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> a -> [a] -> (NonEmpty a, [a])
forall a. (a -> Bool) -> a -> [a] -> (List1 a, [a])
breakAfter1 a -> Bool
p a
x [a]
xs

-- | Break a list when the given predicate returns @Just b@
-- and place @b@ as pivot between the prefix
-- (where the predicate returns 'Nothing') and the suffix.
--
-- Crashes when the predicate holds nowhere.
breakJust :: (a -> Maybe b) -> [a] -> (Prefix a, (b, Suffix a))
breakJust :: forall a b. (a -> Maybe b) -> [a] -> ([a], (b, [a]))
breakJust a -> Maybe b
f = [a] -> ([a], (b, [a]))
go
  where
    go :: [a] -> ([a], (b, [a]))
go = \case
      a
a : [a]
as | Just b
b <- a -> Maybe b
f a
a -> ([], (b
b, [a]
as))
             | Bool
otherwise     -> ([a] -> [a]) -> ([a], (b, [a])) -> ([a], (b, [a]))
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) (([a], (b, [a])) -> ([a], (b, [a])))
-> ([a], (b, [a])) -> ([a], (b, [a]))
forall a b. (a -> b) -> a -> b
$ [a] -> ([a], (b, [a]))
go [a]
as
      [] -> ([a], (b, [a]))
forall a. HasCallStack => a
__IMPOSSIBLE__

-- | \(\mathcal{O}(n)\). A generalized version of 'takeWhile'.
-- (Cf. 'mapMaybe' vs. 'filter').
--
-- ==== __Laws__
--
-- > takeWhileJust f = fst . spanJust f
takeWhileJust :: (a -> Maybe b) -> [a] -> Prefix b
takeWhileJust :: forall a b. (a -> Maybe b) -> [a] -> [b]
takeWhileJust a -> Maybe b
p = [a] -> [b]
loop
  where
    loop :: [a] -> [b]
loop (a
a : [a]
as) | Just b
b <- a -> Maybe b
p a
a = b
b b -> [b] -> [b]
forall a. a -> [a] -> [a]
: [a] -> [b]
loop [a]
as
    loop [a]
_ = []

-- | \(\mathcal{O}(n)\). A generalized version of 'span'.
spanJust :: (a -> Maybe b) -> [a] -> (Prefix b, Suffix a)
spanJust :: forall a b. (a -> Maybe b) -> [a] -> (Prefix b, [a])
spanJust a -> Maybe b
p = [a] -> ([b], [a])
loop
  where
    loop :: [a] -> ([b], [a])
loop (a
a : [a]
as) | Just b
b <- a -> Maybe b
p a
a = ([b] -> [b]) -> ([b], [a]) -> ([b], [a])
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (b
b b -> [b] -> [b]
forall a. a -> [a] -> [a]
:) (([b], [a]) -> ([b], [a])) -> ([b], [a]) -> ([b], [a])
forall a b. (a -> b) -> a -> b
$ [a] -> ([b], [a])
loop [a]
as
    loop [a]
as                       = ([], [a]
as)

-- | \(\mathcal{O}(n)\). Partition a list into 'Nothing's and 'Just's.
--
--
-- ==== __Laws__
--
-- > partitionMaybe f = partitionEithers . map (\ a -> maybe (Left a) Right (f a))
-- > mapMaybe f = snd . partitionMaybe f
partitionMaybe :: (a -> Maybe b) -> [a] -> ([a], [b])
partitionMaybe :: forall a b. (a -> Maybe b) -> [a] -> ([a], [b])
partitionMaybe a -> Maybe b
f = [a] -> ([a], [b])
loop
  where
    loop :: [a] -> ([a], [b])
loop []       = ([], [])
    loop (a
a : [a]
as) = case a -> Maybe b
f a
a of
      Maybe b
Nothing -> ([a] -> [a]) -> ([a], [b]) -> ([a], [b])
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first  (a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
:) (([a], [b]) -> ([a], [b])) -> ([a], [b]) -> ([a], [b])
forall a b. (a -> b) -> a -> b
$ [a] -> ([a], [b])
loop [a]
as
      Just b
b  -> ([b] -> [b]) -> ([a], [b]) -> ([a], [b])
forall b c a. (b -> c) -> (a, b) -> (a, c)
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second (b
b b -> [b] -> [b]
forall a. a -> [a] -> [a]
:) (([a], [b]) -> ([a], [b])) -> ([a], [b]) -> ([a], [b])
forall a b. (a -> b) -> a -> b
$ [a] -> ([a], [b])
loop [a]
as

-- | \(\mathcal{O}(n)\). Spine-strict 'catMaybes'.
catMaybe' :: [Maybe a] -> [a]
catMaybe' :: forall a. [Maybe a] -> [a]
catMaybe' []           = []
catMaybe' (Just a
a:[Maybe a]
as)  = (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$! [Maybe a] -> [a]
forall a. [Maybe a] -> [a]
catMaybe' [Maybe a]
as
catMaybe' (Maybe a
Nothing:[Maybe a]
as) = [Maybe a] -> [a]
forall a. [Maybe a] -> [a]
catMaybe' [Maybe a]
as


-- | \(\mathcal{O}(n)\). Like 'filter', but additionally return the last partition
-- of the list where the predicate is @False@ everywhere.
filterAndRest :: (a -> Bool) -> [a] -> ([a], Suffix a)
filterAndRest :: forall a. (a -> Bool) -> [a] -> ([a], [a])
filterAndRest a -> Bool
p = (a -> Maybe a) -> [a] -> ([a], [a])
forall a b. (a -> Maybe b) -> [a] -> (Prefix b, [a])
mapMaybeAndRest ((a -> Maybe a) -> [a] -> ([a], [a]))
-> (a -> Maybe a) -> [a] -> ([a], [a])
forall a b. (a -> b) -> a -> b
$ \ a
a -> if a -> Bool
p a
a then a -> Maybe a
forall a. a -> Maybe a
Just a
a else Maybe a
forall a. Maybe a
Nothing

{-# INLINE filter' #-}
-- | \(\mathcal{O}(n)\). Strict 'filter'.
filter' :: (a -> Bool) -> [a] -> [a]
filter' :: forall a. (a -> Bool) -> [a] -> [a]
filter' a -> Bool
f = [a] -> [a]
go where
  go :: [a] -> [a]
go [] = []
  go (!a
a:[a]
as) | a -> Bool
f a
a       = (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$! [a] -> [a]
go [a]
as
             | Bool
otherwise = [a] -> [a]
go [a]
as

-- | \(\mathcal{O}(n)\). Like 'mapMaybe', but additionally return the last partition
-- of the list where the function always returns 'Nothing'.
mapMaybeAndRest :: (a -> Maybe b) -> [a] -> ([b], Suffix a)
mapMaybeAndRest :: forall a b. (a -> Maybe b) -> [a] -> (Prefix b, [a])
mapMaybeAndRest a -> Maybe b
f = [a] -> [a] -> ([b], [a])
loop [] where
  loop :: [a] -> [a] -> ([b], [a])
loop [a]
acc = \case
    []                   -> ([], [a] -> [a]
forall a. [a] -> [a]
reverse [a]
acc)
    a
x:[a]
xs | Just b
y <- a -> Maybe b
f a
x -> ([b] -> [b]) -> ([b], [a]) -> ([b], [a])
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (b
yb -> [b] -> [b]
forall a. a -> [a] -> [a]
:) (([b], [a]) -> ([b], [a])) -> ([b], [a]) -> ([b], [a])
forall a b. (a -> b) -> a -> b
$ [a] -> [a] -> ([b], [a])
loop [] [a]
xs
         | Bool
otherwise     -> [a] -> [a] -> ([b], [a])
loop (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
acc) [a]
xs

-- | @dropFrom marker xs@ drops everything from @xs@
-- starting with (and including) @marker@.
--
-- If the marker does not appear, the string is returned unchanged.
--
-- The following two properties hold provided @marker@ has no overlap with @xs@:
--
-- @
--   dropFrom marker (xs ++ marker ++ ys) == xs
--   dropFrom marker xs == xs
-- @
dropFrom :: Eq a => List1 a -> [a] -> [a]
dropFrom :: forall a. Eq a => List1 a -> [a] -> [a]
dropFrom List1 a
marker [a]
xs = [a] -> [[a]] -> [a]
forall a. a -> [a] -> a
headWithDefault [a]
forall a. HasCallStack => a
__IMPOSSIBLE__ ([[a]] -> [a]) -> [[a]] -> [a]
forall a b. (a -> b) -> a -> b
$ [a] -> [a] -> [[a]]
forall a. Eq a => [a] -> [a] -> [[a]]
splitOn (List1 a -> [a]
forall a. NonEmpty a -> [a]
List1.toList List1 a
marker) [a]
xs

-- | \(\mathcal{O}(n^2)\). All ways of removing one element from a list.
holes :: [a] -> [(a, [a])]
holes :: forall a. [a] -> [(a, [a])]
holes []     = []
holes (a
x:[a]
xs) = (a
x, [a]
xs) (a, [a]) -> [(a, [a])] -> [(a, [a])]
forall a. a -> [a] -> [a]
: ((a, [a]) -> (a, [a])) -> [(a, [a])] -> [(a, [a])]
forall a b. (a -> b) -> [a] -> [b]
map (([a] -> [a]) -> (a, [a]) -> (a, [a])
forall b c a. (b -> c) -> (a, b) -> (a, c)
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:)) ([a] -> [(a, [a])]
forall a. [a] -> [(a, [a])]
holes [a]
xs)

-- | \(\mathcal{O}(n)\). Replace the element at the given index with the
-- given value.
--
-- Spine-strict.
replaceAt' :: Int -> a -> [a] -> [a]
replaceAt' :: forall a. Int -> a -> [a] -> [a]
replaceAt' Int
n a
x [a]
xs = [a]
xs0 [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++! (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs1)
  where ([a]
xs0,a
_:[a]
xs1) = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
splitAt' Int
n [a]
xs

---------------------------------------------------------------------------
-- Prefix and suffix
---------------------------------------------------------------------------

---------------------------------------------------------------------------
-- Prefix
---------------------------------------------------------------------------


-- | \(\mathcal{O}(\min(m, n))\). Compute the common prefix of two lists.
commonPrefix :: Eq a => [a] -> [a] -> Prefix a
commonPrefix :: forall a. Eq a => [a] -> [a] -> [a]
commonPrefix [] [a]
_ = []
commonPrefix [a]
_ [] = []
commonPrefix (a
x:[a]
xs) (a
y:[a]
ys)
  | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y    = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a] -> [a]
forall a. Eq a => [a] -> [a] -> [a]
commonPrefix [a]
xs [a]
ys
  | Bool
otherwise = []

-- | \(\mathcal{O}(\min(m, n))\). Drops from both lists simultaneously until one list is empty.
dropCommon :: [a] -> [b] -> (Suffix a, Suffix b)
dropCommon :: forall a b. [a] -> [b] -> ([a], [b])
dropCommon (a
x : [a]
xs) (b
y : [b]
ys) = [a] -> [b] -> ([a], [b])
forall a b. [a] -> [b] -> ([a], [b])
dropCommon [a]
xs [b]
ys
dropCommon [a]
xs [b]
ys = ([a]
xs, [b]
ys)

-- | \(\mathcal{O}(n)\). Check if a list has a given prefix. If so, return the list
-- minus the prefix.
stripPrefixBy :: (a -> a -> Bool) -> Prefix a -> [a] -> Maybe (Suffix a)
stripPrefixBy :: forall a.
(a -> a -> Bool) -> Prefix a -> Prefix a -> Maybe (Prefix a)
stripPrefixBy a -> a -> Bool
eq = [a] -> [a] -> Maybe [a]
loop
  where
  loop :: [a] -> [a] -> Maybe [a]
loop []    [a]
rest = [a] -> Maybe [a]
forall a. a -> Maybe a
Just [a]
rest
  loop (a
_:[a]
_) []   = Maybe [a]
forall a. Maybe a
Nothing
  loop (a
p:[a]
pat) (a
r:[a]
rest)
    | a -> a -> Bool
eq a
p a
r    = [a] -> [a] -> Maybe [a]
loop [a]
pat [a]
rest
    | Bool
otherwise = Maybe [a]
forall a. Maybe a
Nothing

---------------------------------------------------------------------------
-- Suffix
---------------------------------------------------------------------------

-- | \(\mathcal{O}(m + n)\). Compute the common suffix of two lists.
commonSuffix :: Eq a => [a] -> [a] -> Suffix a
commonSuffix :: forall a. Eq a => [a] -> [a] -> [a]
commonSuffix [a]
xs [a]
ys = [a] -> [a]
forall a. [a] -> [a]
reverse ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ ([a] -> [a] -> [a]
forall a. Eq a => [a] -> [a] -> [a]
commonPrefix ([a] -> [a] -> [a]) -> ([a] -> [a]) -> [a] -> [a] -> [a]
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` [a] -> [a]
forall a. [a] -> [a]
reverse) [a]
xs [a]
ys

-- | \(\mathcal{O}(n)\). @stripSuffix suf xs = Just pre@ iff @xs = pre ++ suf@.
--
-- ==== __Laws__
--
-- > stripSuffix suf (pre ++ sufh) = Just pre
stripSuffix :: Eq a => Suffix a -> [a] -> Maybe (Prefix a)
stripSuffix :: forall a. Eq a => Suffix a -> Suffix a -> Maybe (Suffix a)
stripSuffix [] = [a] -> Maybe [a]
forall a. a -> Maybe a
Just
stripSuffix [a]
s  = [a] -> [a] -> Maybe [a]
forall a. Eq a => Suffix a -> Suffix a -> Maybe (Suffix a)
stripReversedSuffix ([a] -> [a]
forall a. [a] -> [a]
reverse [a]
s)

type ReversedSuffix a = [a]

-- | \(\mathcal{O}(n)\).
--
-- ==== __Laws__
--
-- > stripReversedSuffix suf (pre ++ reverse suf) = Just pre
stripReversedSuffix :: forall a. Eq a => ReversedSuffix a -> [a] -> Maybe (Prefix a)
stripReversedSuffix :: forall a. Eq a => Suffix a -> Suffix a -> Maybe (Suffix a)
stripReversedSuffix ReversedSuffix a
rs = StrSufSt a -> Maybe (ReversedSuffix a)
final (StrSufSt a -> Maybe (ReversedSuffix a))
-> (ReversedSuffix a -> StrSufSt a)
-> ReversedSuffix a
-> Maybe (ReversedSuffix a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> StrSufSt a -> StrSufSt a)
-> StrSufSt a -> ReversedSuffix a -> StrSufSt 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 -> StrSufSt a -> StrSufSt a
step (ReversedSuffix a -> StrSufSt a
forall a. ReversedSuffix a -> StrSufSt a
SSSStrip ReversedSuffix a
rs)
  where
  -- Step of the automaton (reading input from right to left).
  step :: a -> StrSufSt a -> StrSufSt a
  step :: a -> StrSufSt a -> StrSufSt a
step a
x = \case
    StrSufSt a
SSSMismatch   -> StrSufSt a
forall a. StrSufSt a
SSSMismatch
    SSSResult ReversedSuffix a
xs  -> ReversedSuffix a -> StrSufSt a
forall a. ReversedSuffix a -> StrSufSt a
SSSResult (a
xa -> ReversedSuffix a -> ReversedSuffix a
forall a. a -> [a] -> [a]
:ReversedSuffix a
xs)
    SSSStrip []   -> ReversedSuffix a -> StrSufSt a
forall a. ReversedSuffix a -> StrSufSt a
SSSResult [a
x]
    SSSStrip (a
y:ReversedSuffix a
ys)
      | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y    -> ReversedSuffix a -> StrSufSt a
forall a. ReversedSuffix a -> StrSufSt a
SSSStrip ReversedSuffix a
ys
      | Bool
otherwise -> StrSufSt a
forall a. StrSufSt a
SSSMismatch

  -- Output of the automaton.
  final :: StrSufSt a -> Maybe (Prefix a)
  final :: StrSufSt a -> Maybe (ReversedSuffix a)
final = \case
    SSSResult ReversedSuffix a
xs -> ReversedSuffix a -> Maybe (ReversedSuffix a)
forall a. a -> Maybe a
Just ReversedSuffix a
xs
    SSSStrip []  -> ReversedSuffix a -> Maybe (ReversedSuffix a)
forall a. a -> Maybe a
Just []
    StrSufSt a
_            -> Maybe (ReversedSuffix a)
forall a. Maybe a
Nothing  -- We have not stripped the whole suffix or encountered a mismatch.

-- | Internal state for stripping suffix.
data StrSufSt a
  = SSSMismatch
  -- ^ Error.
  | SSSStrip (ReversedSuffix a)
  -- ^ "Negative string" to remove from end. List may be empty.
  | SSSResult [a]
  -- ^ "Positive string" (result). Non-empty list.

-- | Returns a list with one boolean for each non-empty suffix of the
-- list, starting with the longest suffix (the entire list). Each
-- boolean is 'True' exactly when every element in the corresponding
-- suffix satisfies the predicate.
--
-- ==== __Examples__
--
-- >>> suffixesSatisfying isLower "AbCde"
-- [False, False, False, True, True]
--
-- ==== __Laws__
--
-- For total predicates @p@ and finite and total lists @xs@ the
-- following holds:
--
-- > suffixesSatisfying p xs = map (all p) (init (tails xs))
suffixesSatisfying :: (a -> Bool) -> [a] -> [Bool]
suffixesSatisfying :: forall a. (a -> Bool) -> [a] -> [Bool]
suffixesSatisfying a -> Bool
p =
  (Bool, [Bool]) -> [Bool]
forall a b. (a, b) -> b
snd ((Bool, [Bool]) -> [Bool])
-> ([a] -> (Bool, [Bool])) -> [a] -> [Bool]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
  (a -> (Bool, [Bool]) -> (Bool, [Bool]))
-> (Bool, [Bool]) -> [a] -> (Bool, [Bool])
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 (Bool
b, [Bool]
bs) -> let !b' :: Bool
b' = a -> Bool
p a
x Bool -> Bool -> Bool
&& Bool
b in (Bool
b', Bool
b' Bool -> [Bool] -> [Bool]
forall a. a -> [a] -> [a]
: [Bool]
bs))
        (Bool
True, [])

---------------------------------------------------------------------------
-- Finding overlap
---------------------------------------------------------------------------

-- | \(\mathcal{O}(\min(m, n)^2)\). Find the longest suffix of the first string @xs@
-- that is a prefix of the second string @ys@.
-- So, basically, find the overlap where the strings can be glued together.
-- Returns the index where the overlap starts and the length of the overlap.
-- The length of the overlap plus the index is the length of the first string.
-- Note that in the worst case, the empty overlap @(length xs,0)@ is returned.
--
-- There might be asymptotically better implementations following
-- Knuth-Morris-Pratt or Boyer-Moore, but for rather short lists this is good enough.
findOverlap :: forall a. Eq a => [a] -> [a] -> (Int, Int)
findOverlap :: forall a. Eq a => [a] -> [a] -> (Int, Int)
findOverlap [a]
xs [a]
ys =
  (Int, Int) -> [(Int, Int)] -> (Int, Int)
forall a. a -> [a] -> a
headWithDefault (Int, Int)
forall a. HasCallStack => a
__IMPOSSIBLE__ ([(Int, Int)] -> (Int, Int)) -> [(Int, Int)] -> (Int, Int)
forall a b. (a -> b) -> a -> b
$ ((Int, [a]) -> Maybe (Int, Int)) -> [(Int, [a])] -> [(Int, Int)]
forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe (Int, [a]) -> Maybe (Int, Int)
maybePrefix ([(Int, [a])] -> [(Int, Int)]) -> [(Int, [a])] -> [(Int, Int)]
forall a b. (a -> b) -> a -> b
$ [Int] -> [[a]] -> [(Int, [a])]
forall a b. [a] -> [b] -> [(a, b)]
zip [Int
0..] ([a] -> [[a]]
forall a. [a] -> [[a]]
List.tails [a]
xs)
  where
  maybePrefix :: (Int, [a]) -> Maybe (Int, Int)
  maybePrefix :: (Int, [a]) -> Maybe (Int, Int)
maybePrefix (Int
k, [a]
xs')
    | [a]
xs' [a] -> [a] -> Bool
forall a. Eq a => [a] -> [a] -> Bool
`List.isPrefixOf` [a]
ys = (Int, Int) -> Maybe (Int, Int)
forall a. a -> Maybe a
Just (Int
k, [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs')
    | Bool
otherwise                = Maybe (Int, Int)
forall a. Maybe a
Nothing

---------------------------------------------------------------------------
-- Chunks
---------------------------------------------------------------------------

-- | \(\mathcal{O}(n)\). Chop up a list in chunks of a given length.
chop :: Int -> [a] -> [[a]]
chop :: forall a. Int -> [a] -> [[a]]
chop Int
_ [] = []
chop Int
n [a]
xs = [a]
ys [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: Int -> [a] -> [[a]]
forall a. Int -> [a] -> [[a]]
chop Int
n [a]
zs
    where ([a]
ys,[a]
zs) = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
splitAt Int
n [a]
xs

-- | \(\mathcal{O}(n)\). Chop a list at the positions when the predicate holds. Contrary to
-- 'Mikan.Utils.List1.wordsBy', consecutive separator elements will result in an empty segment
-- in the result.
--
-- ==== __Laws__
--
-- > intercalate [x] (chopWhen (== x) xs) == xs
chopWhen :: forall a. (a -> Bool) -> [a] -> [[a]]
chopWhen :: forall a. (a -> Bool) -> [a] -> [[a]]
chopWhen a -> Bool
p []     = []
chopWhen a -> Bool
p (a
x:[a]
xs) = List1 a -> [[a]]
loop (a
x a -> [a] -> List1 a
forall a. a -> [a] -> NonEmpty a
:| [a]
xs)
  where
  -- Local function to avoid unnecessary pattern matching.
  loop :: List1 a -> [[a]]
  loop :: List1 a -> [[a]]
loop List1 a
xs = case (a -> Bool) -> List1 a -> ([a], [a])
forall a. (a -> Bool) -> NonEmpty a -> ([a], [a])
List1.break a -> Bool
p List1 a
xs of
    ([a]
w, []        ) -> [[a]
w]
    ([a]
w, a
_ : []    ) -> [[a]
w, []]
    ([a]
w, a
_ : a
y : [a]
ys) -> [a]
w [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: List1 a -> [[a]]
loop (a
y a -> [a] -> List1 a
forall a. a -> [a] -> NonEmpty a
:| [a]
ys)

---------------------------------------------------------------------------
-- Sorting
---------------------------------------------------------------------------

-- | \(\mathcal{O}(n \log n)\). Monadic version of 'Data.List.sortOn'.
--
-- The effect is executed exactly once for each list element.
sortOnM :: (Monad m, Ord b) => (a -> m b) -> [a] -> m [a]
sortOnM :: forall (m :: * -> *) b a.
(Monad m, Ord b) =>
(a -> m b) -> [a] -> m [a]
sortOnM a -> m b
f [a]
xs =
  ((a, b) -> a) -> [(a, b)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (a, b) -> a
forall a b. (a, b) -> a
fst ([(a, b)] -> [a]) -> ([(a, b)] -> [(a, b)]) -> [(a, b)] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, b) -> (a, b) -> Ordering) -> [(a, b)] -> [(a, b)]
forall a. (a -> a -> Ordering) -> [a] -> [a]
List.sortBy (b -> b -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (b -> b -> Ordering)
-> ((a, b) -> b) -> (a, b) -> (a, b) -> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` (a, b) -> b
forall a b. (a, b) -> b
snd) ([(a, b)] -> [a]) -> m [(a, b)] -> m [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a] -> (a -> m (a, b)) -> m [(a, b)]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
t a -> (a -> m b) -> m (t b)
forM [a]
xs \ !a
x -> (a
x,) (b -> (a, b)) -> m b -> m (a, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> m b
f a
x

-- | \(\mathcal{O}(n)\). Check whether a list is sorted.
--
-- Assumes that the 'Ord' instance implements a partial order.
sorted :: Ord a => [a] -> Bool
sorted :: forall a. Ord a => [a] -> Bool
sorted = (a -> a -> Bool) -> [a] -> Bool
forall a. (a -> a -> Bool) -> [a] -> Bool
allConsecutive a -> a -> Bool
forall a. Ord a => a -> a -> Bool
(<=)

-- | \(\mathcal{O}(n)\). Check whether all consecutive elements of a list satisfy the given relation.
allConsecutive :: (a -> a -> Bool) -> [a] -> Bool
allConsecutive :: forall a. (a -> a -> Bool) -> [a] -> Bool
allConsecutive a -> a -> Bool
cmp [a]
xs = [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and ([Bool] -> Bool) -> [Bool] -> Bool
forall a b. (a -> b) -> a -> b
$ (a -> a -> Bool) -> [a] -> [a] -> [Bool]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith a -> a -> Bool
cmp [a]
xs ([a] -> [Bool]) -> [a] -> [Bool]
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
drop Int
1 [a]
xs

-- | \(\mathcal{O}(\min(m, n))\). Merge two lists using a comparison function.
--
-- If any of the elements of the list are incomparable, returns 'Nothing'.
-- Otherwise, returns a 'Just' containing a sorted list.
mergeStrictlyOrderedBy :: (a -> a -> Bool) -> [a] -> [a] -> Maybe [a]
mergeStrictlyOrderedBy :: forall a.
(a -> a -> Bool) -> Prefix a -> Prefix a -> Maybe (Prefix a)
mergeStrictlyOrderedBy a -> a -> Bool
(<) = [a] -> [a] -> Maybe [a]
loop where
  loop :: [a] -> [a] -> Maybe [a]
loop [] [a]
ys = [a] -> Maybe [a]
forall a. a -> Maybe a
Just [a]
ys
  loop [a]
xs [] = [a] -> Maybe [a]
forall a. a -> Maybe a
Just [a]
xs
  loop (a
x:[a]
xs) (a
y:[a]
ys)
    | a
x a -> a -> Bool
< a
y = (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [a]) -> Maybe [a] -> Maybe [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a] -> [a] -> Maybe [a]
loop [a]
xs (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ys)
    | a
y a -> a -> Bool
< a
x = (a
ya -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [a]) -> Maybe [a] -> Maybe [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a] -> [a] -> Maybe [a]
loop (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs) [a]
ys
    | Bool
otherwise = Maybe [a]
forall a. Maybe a
Nothing

---------------------------------------------------------------------------
-- List as sets
---------------------------------------------------------------------------

-- | Check membership for the same list often.
--   Use partially applied to create membership predicate
--   @hasElem xs :: a -> Bool@.
--
--   * First time: \(\mathcal{O}(n \log n)\) in the worst case.
--   * Subsequently: \(\mathcal{O}(\log n)\).
--
-- ==== __Laws__
--
-- > hasElem xs == (`elem` xs)
hasElem :: Ord a => [a] -> a -> Bool
hasElem :: forall a. Ord a => [a] -> a -> Bool
hasElem [a]
xs = (a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`Set.member` [a] -> Set a
forall a. Ord a => [a] -> Set a
Set.fromList [a]
xs)

-- | \(\mathcal{O}(n^2)\). Check whether all elements in a list are distinct from each other.
--   Assumes that the 'Eq' instance stands for an equivalence relation.
distinct :: Eq a => [a] -> Bool
distinct :: forall a. Eq a => [a] -> Bool
distinct []     = Bool
True
distinct (a
x:[a]
xs) = a
x a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`notElem` [a]
xs Bool -> Bool -> Bool
&& [a] -> Bool
forall a. Eq a => [a] -> Bool
distinct [a]
xs

-- | \(\mathcal{O}(n \log n)\). An optimised version of 'distinct'.
--
-- Precondition: The list's length must fit in an 'Int'.
fastDistinct :: Ord a => [a] -> Bool
fastDistinct :: forall a. Ord a => [a] -> Bool
fastDistinct [a]
xs = Set a -> Int
forall a. Set a -> Int
Set.size ([a] -> Set a
forall a. Ord a => [a] -> Set a
Set.fromList [a]
xs) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs

{-# INLINE duplicates #-}
-- | \(\mathcal{O}(n \log n)\). Returns an (arbitrary) representative for each list element
-- that occurs more than once.
--
-- 'duplicates' is strict in the spine of the list.
--
-- ==== __Examples__
--
-- >>> duplicates "abcbcdbb"
-- "bc"
--
-- >>> duplicates [1,0,2,2,2,2,1,9]
-- [2,2,2,1]
duplicates :: Ord a => [a] -> [a]
duplicates :: forall a. Ord a => [a] -> [a]
duplicates = Map a Integer -> [a] -> [a]
forall {k} {a}. (Ord k, Num a, Eq a) => Map k a -> [k] -> [k]
loop Map a Integer
forall k a. Map k a
SMap.empty where
  -- Most of our uses of @duplicates@ are checking for lists
  -- of user-written names contain duplicates, so it makes sense
  -- to optimize for short lists.
  --
  -- Moreover, benchmarking shows that this is slightly faster
  -- than an alterF based approach for small lists.
  loop :: Map k a -> [k] -> [k]
loop Map k a
counts [] = []
  loop Map k a
counts (k
x:[k]
xs) =
    case a -> k -> Map k a -> a
forall k a. Ord k => a -> k -> Map k a -> a
Map.findWithDefault a
0 k
x Map k a
counts of
      a
1 -> k
xk -> [k] -> [k]
forall a. a -> [a] -> [a]
:Map k a -> [k] -> [k]
loop (k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
x a
2 Map k a
counts) [k]
xs
      a
n -> Map k a -> [k] -> [k]
loop (k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
x (a
n a -> a -> a
forall a. Num a => a -> a -> a
+ a
1) Map k a
counts) [k]
xs

{-# INLINE allDuplicates #-}
-- | \(\mathcal{O}(n \log n)\) Remove the first representative for each list element.
--
-- The elements of the list are returned in the same order.
--
-- 'allDuplicates' is strict in the spine of the list.
--
-- ==== __Examples__
--
-- >>> duplicates [1,2,2,0,3,3,3,3,2,1,9]
-- [2,3,3,3,2,1]
allDuplicates :: Ord a => [a] -> [a]
allDuplicates :: forall a. Ord a => [a] -> [a]
allDuplicates = Set a -> [a] -> [a]
forall {a}. Ord a => Set a -> [a] -> [a]
loop Set a
forall a. Set a
Set.empty where
  -- Most of our uses of @allDuplicates@ are checking for lists
  -- of user-written names contain duplicates, so it makes sense
  -- to optimize for short lists.
  --
  -- Moreover, benchmarking shows that this is slightly faster
  -- than an alterF based approach for small lists.
  loop :: Set a -> [a] -> [a]
loop Set a
seen [] = []
  loop Set a
seen (a
x:[a]
xs)
    | a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member a
x Set a
seen = a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:Set a -> [a] -> [a]
loop Set a
seen [a]
xs
    | Bool
otherwise = Set a -> [a] -> [a]
loop (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
Set.insert a
x Set a
seen) [a]
xs

{-# INLINE nubAndDuplicatesOn #-}
-- | \(\mathcal{O}(n \log n)\). Partition a list into first and later occurrences of elements
--   (modulo some quotient given by a representation function).
--
-- ==== __Laws__
--
--  > nubAndDuplicatesOn f xs = (ys, xs List.\\ ys)
--  >   where ys = nubOn f xs
nubAndDuplicatesOn :: Ord b => (a -> b) -> [a] -> ([a], [a])
nubAndDuplicatesOn :: forall b a. Ord b => (a -> b) -> [a] -> ([a], [a])
nubAndDuplicatesOn a -> b
f = Set b -> [a] -> ([a], [a])
loop Set b
forall a. Set a
Set.empty where
  loop :: Set b -> [a] -> ([a], [a])
loop Set b
s [] = ([], [])
  loop Set b
s (a
a:[a]
as)
    | b
b b -> Set b -> Bool
forall a. Ord a => a -> Set a -> Bool
`Set.member` Set b
s = ([a] -> [a]) -> ([a], [a]) -> ([a], [a])
forall b c a. (b -> c) -> (a, b) -> (a, c)
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) (([a], [a]) -> ([a], [a])) -> ([a], [a]) -> ([a], [a])
forall a b. (a -> b) -> a -> b
$ Set b -> [a] -> ([a], [a])
loop Set b
s [a]
as
    | Bool
otherwise        = ([a] -> [a]) -> ([a], [a]) -> ([a], [a])
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first  (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) (([a], [a]) -> ([a], [a])) -> ([a], [a]) -> ([a], [a])
forall a b. (a -> b) -> a -> b
$ Set b -> [a] -> ([a], [a])
loop (b -> Set b -> Set b
forall a. Ord a => a -> Set a -> Set a
Set.insert b
b Set b
s) [a]
as
    where b :: b
b = a -> b
f a
a

{-# INLINE nubOn #-}
-- | \(\mathcal{O}(n \log n)\). Efficient variant of 'Data.List.nubBy' for lists, using a set to store already seen elements.
--
-- ==== __Laws__
--
-- > nubOn f xs == nubBy ((==) `on` f) xs.
nubOn :: Ord b => (a -> b) -> [a] -> [a]
nubOn :: forall b a. Ord b => (a -> b) -> [a] -> [a]
nubOn = (a -> b) -> [a] -> [a]
forall b a. Ord b => (a -> b) -> [a] -> [a]
List.nubOrdOn

-- | A variant of 'nubOn' that is parametrised by a function that is
-- used to select which element from a group of equal elements that is
-- returned. The returned elements keep the order that they had in the
-- input list.
--
-- Precondition: The length of the input list must be at most
-- @'maxBound' :: 'Int'@.
nubFavouriteOn
  :: forall a b c. (Ord b, Hashable c)
  => (a -> b)
     -- ^ The values returned by this function are used to determine
     -- which element from a group of equal elements that is returned:
     -- the smallest one is chosen (and if two elements are equally
     -- small, then the first one is chosen).
  -> (a -> c)
     -- ^ Two elements are treated as equal if this function returns
     -- the same value for both elements.
  -> [a] -> [a]
nubFavouriteOn :: forall a b c.
(Ord b, Hashable c) =>
(a -> b) -> (a -> c) -> [a] -> [a]
nubFavouriteOn a -> b
fav a -> c
f = Int -> HashMap c ((b, Int), a) -> [a] -> [a]
go Int
0 HashMap c ((b, Int), a)
forall k v. HashMap k v
HMap.empty
  where
  go :: Int -> HMap.HashMap c ((b, Int), a) -> [a] -> [a]
  go :: Int -> HashMap c ((b, Int), a) -> [a] -> [a]
go !Int
pos !HashMap c ((b, Int), a)
acc (a
x : [a]
xs) =
    Int -> HashMap c ((b, Int), a) -> [a] -> [a]
go (Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
pos)
       ((((b, Int), a) -> ((b, Int), a) -> ((b, Int), a))
-> c
-> ((b, Int), a)
-> HashMap c ((b, Int), a)
-> HashMap c ((b, Int), a)
forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
HMap.insertWith
          (\((b, Int), a)
new ((b, Int), a)
old -> if ((b, Int), a) -> (b, Int)
forall a b. (a, b) -> a
fst ((b, Int), a)
new (b, Int) -> (b, Int) -> Bool
forall a. Ord a => a -> a -> Bool
< ((b, Int), a) -> (b, Int)
forall a b. (a, b) -> a
fst ((b, Int), a)
old then ((b, Int), a)
new else ((b, Int), a)
old)
          (a -> c
f a
x) ((a -> b
fav a
x, Int
pos), a
x) HashMap c ((b, Int), a)
acc)
       [a]
xs
  go Int
_ HashMap c ((b, Int), a)
acc [] =
    (((b, Int), a) -> a) -> [((b, Int), a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map ((b, Int), a) -> a
forall a b. (a, b) -> b
snd ([((b, Int), a)] -> [a]) -> [((b, Int), a)] -> [a]
forall a b. (a -> b) -> a -> b
$ (((b, Int), a) -> ((b, Int), a) -> Ordering)
-> [((b, Int), a)] -> [((b, Int), a)]
forall a. (a -> a -> Ordering) -> [a] -> [a]
List.sortBy (Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Int -> Int -> Ordering)
-> (((b, Int), a) -> Int)
-> ((b, Int), a)
-> ((b, Int), a)
-> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` (b, Int) -> Int
forall a b. (a, b) -> b
snd ((b, Int) -> Int)
-> (((b, Int), a) -> (b, Int)) -> ((b, Int), a) -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((b, Int), a) -> (b, Int)
forall a b. (a, b) -> a
fst) ([((b, Int), a)] -> [((b, Int), a)])
-> [((b, Int), a)] -> [((b, Int), a)]
forall a b. (a -> b) -> a -> b
$
    HashMap c ((b, Int), a) -> [((b, Int), a)]
forall k v. HashMap k v -> [v]
HMap.elems HashMap c ((b, Int), a)
acc

-- | \(\mathcal{O}(n \log n)\). Efficient variant of 'Data.List.nubBy' for finite lists.
--
-- If there are several elements with the same @f@-representative,
-- the first of these is kept.
--
-- ==== __Laws__
--
-- > uniqOn f == 'List.sortBy' (compare `'on'` f) . 'List.nubBy' ((==) `'on'` f)
uniqOn :: Ord b => (a -> b) -> [a] -> [a]
uniqOn :: forall b a. Ord b => (a -> b) -> [a] -> [a]
uniqOn a -> b
key = Map b a -> [a]
forall k a. Map k a -> [a]
Map.elems (Map b a -> [a]) -> ([a] -> Map b a) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> a) -> [(b, a)] -> Map b a
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Map.fromListWith (\ a
_ -> a -> a
forall a. a -> a
id) ([(b, a)] -> Map b a) -> ([a] -> [(b, a)]) -> [a] -> Map 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
a -> (a -> b
key a
a, a
a))

-- | \(\mathcal{O}(n)\). Checks if all the elements in the list are equal. Assumes that
-- the 'Eq' instance stands for an equivalence relation.
allEqual :: Eq a => [a] -> Bool
allEqual :: forall a. Eq a => [a] -> Bool
allEqual []       = Bool
True
allEqual (a
x : [a]
xs) = (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
x) [a]
xs

-- | \(\mathcal{O}(n^2)\). Non-efficient, monadic 'Data.List.nub'.
nubM :: Monad m => (a -> a -> m Bool) -> [a] -> m [a]
nubM :: forall (m :: * -> *) a.
Monad m =>
(a -> a -> m Bool) -> [a] -> m [a]
nubM a -> a -> m Bool
eq = [a] -> m [a]
loop where
  loop :: [a] -> m [a]
loop []     = [a] -> m [a]
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return []
  loop (a
a:[a]
as) = (a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [a]) -> m [a] -> m [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> do [a] -> m [a]
loop ([a] -> m [a]) -> m [a] -> m [a]
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< (a -> m Bool) -> [a] -> m [a]
forall (m :: * -> *) a.
Applicative m =>
(a -> m Bool) -> [a] -> m [a]
filterM (Bool -> Bool
not (Bool -> Bool) -> (a -> m Bool) -> a -> m Bool
forall (m :: * -> *) b c a.
Functor m =>
(b -> c) -> (a -> m b) -> a -> m c
<.> a -> a -> m Bool
eq a
a) [a]
as

---------------------------------------------------------------------------
-- Zipping
---------------------------------------------------------------------------

-- | \(\mathcal{O}(\min(m, n))\). Spine-strict zipping.
zip' :: [a] -> [b] -> [(a, b)]
zip' :: forall a b. [a] -> [b] -> [(a, b)]
zip' (a
a:[a]
as) (b
b:[b]
bs) = ((a
a, b
b)(a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
:) ([(a, b)] -> [(a, b)]) -> [(a, b)] -> [(a, b)]
forall a b. (a -> b) -> a -> b
$! [a] -> [b] -> [(a, b)]
forall a b. [a] -> [b] -> [(a, b)]
zip' [a]
as [b]
bs
zip' [a]
as  ![b]
bs       = []

{-# INLINE zipWith' #-}
-- | \(\mathcal{O}(\min(m, n))\). Strict 'zipWith'.
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' :: forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' a -> b -> c
f = [a] -> [b] -> [c]
go where
  go :: [a] -> [b] -> [c]
go (a
a:[a]
as) (b
b:[b]
bs) = let !c :: c
c = a -> b -> c
f a
a b
b in (c
cc -> [c] -> [c]
forall a. a -> [a] -> [a]
:) ([c] -> [c]) -> [c] -> [c]
forall a b. (a -> b) -> a -> b
$! [a] -> [b] -> [c]
go [a]
as [b]
bs
  go [a]
as     ![b]
bs    = []

{-# INLINE zipWith'' #-}
-- | \(\mathcal{O}(\min(m, n))\). Spine-strict 'zipWith'.
zipWith'' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith'' :: forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith'' a -> b -> c
f = [a] -> [b] -> [c]
go where
  go :: [a] -> [b] -> [c]
go (a
a:[a]
as) (b
b:[b]
bs) = (a -> b -> c
f a
a b
bc -> [c] -> [c]
forall a. a -> [a] -> [a]
:) ([c] -> [c]) -> [c] -> [c]
forall a b. (a -> b) -> a -> b
$! [a] -> [b] -> [c]
go [a]
as [b]
bs
  go [a]
as     ![b]
bs    = []

-- | \(\mathcal{O}(\min(m, n))\). Requires both lists to have the same length.
-- Otherwise, @Nothing@ is returned.
zipWithSameLen :: (a -> b -> c) -> [a] -> [b] -> Maybe [c]
zipWithSameLen :: forall a b c. (a -> b -> c) -> [a] -> [b] -> Maybe [c]
zipWithSameLen a -> b -> c
f = [a] -> [b] -> Maybe [c]
loop
  where
  loop :: [a] -> [b] -> Maybe [c]
loop []        []      = [c] -> Maybe [c]
forall a. a -> Maybe a
Just []
  loop (a
x : [a]
xs) (b
y : [b]
ys) = (a -> b -> c
f a
x b
y c -> [c] -> [c]
forall a. a -> [a] -> [a]
:) ([c] -> [c]) -> Maybe [c] -> Maybe [c]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a] -> [b] -> Maybe [c]
loop [a]
xs [b]
ys
  loop []       (b
_ : [b]
_)  = Maybe [c]
forall a. Maybe a
Nothing
  loop (a
_ : [a]
_)  []       = Maybe [c]
forall a. Maybe a
Nothing

-- | \(\mathcal{O}(\min(m, n))\). Like 'zipWith' but keep the rest of the second list as-is
-- (in case the second list is longer).
--
-- ==== __Laws__
--
-- > zipWithKeepRest f as bs == zipWith f as bs ++ drop (length as) bs
zipWithKeepRest :: (a -> b -> b) -> [a] -> [b] -> [b]
zipWithKeepRest :: forall a b. (a -> b -> b) -> [a] -> [b] -> [b]
zipWithKeepRest a -> b -> b
f = [a] -> [b] -> [b]
loop
  where
  loop :: [a] -> [b] -> [b]
loop []       [b]
bs       = [b]
bs
  loop [a]
as       []       = []
  loop (a
a : [a]
as) (b
b : [b]
bs) = a -> b -> b
f a
a b
b b -> [b] -> [b]
forall a. a -> [a] -> [a]
: [a] -> [b] -> [b]
loop [a]
as [b]
bs

-- | \(\mathcal{O}(\max(m, n))\). Analogous to 'zip', combines two lists
-- by taking the union using a strict t'These'.
align :: [a] -> [b] -> [These a b]
align :: forall a b. [a] -> [b] -> [These a b]
align [a]
xs [] = a -> These a b
forall a b. a -> These a b
This (a -> These a b) -> [a] -> [These a b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a]
xs
align [] [b]
ys = b -> These a b
forall a b. b -> These a b
That (b -> These a b) -> [b] -> [These a b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [b]
ys
align (a
x:[a]
xs) (b
y:[b]
ys) = a -> b -> These a b
forall a b. a -> b -> These a b
These a
x b
y These a b -> [These a b] -> [These a b]
forall a. a -> [a] -> [a]
: [a] -> [b] -> [These a b]
forall a b. [a] -> [b] -> [These a b]
align [a]
xs [b]
ys

---------------------------------------------------------------------------
-- Unzipping
---------------------------------------------------------------------------

-- | Split a list into a pair of lists.
unzipWith :: (a -> (b, c)) -> [a] -> ([b], [c])
unzipWith :: forall a b c. (a -> (b, c)) -> [a] -> ([b], [c])
unzipWith a -> (b, c)
f = [(b, c)] -> ([b], [c])
forall a b. [(a, b)] -> ([a], [b])
unzip ([(b, c)] -> ([b], [c])) -> ([a] -> [(b, c)]) -> [a] -> ([b], [c])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> (b, c)) -> [a] -> [(b, c)]
forall a b. (a -> b) -> [a] -> [b]
map a -> (b, c)
f

---------------------------------------------------------------------------
-- Edit distance
---------------------------------------------------------------------------

-- | \(\mathcal{O}(mn)\). Find the edit distance between two lists.
editDistance :: forall a. Eq a => [a] -> [a] -> Int
editDistance :: forall a. Eq a => [a] -> [a] -> Int
editDistance [a]
xs [a]
ys = Int -> Int -> Int
editD Int
0 Int
0
  where
  editD :: Int -> Int -> Int
editD Int
i Int
j = Array (Int, Int) Int
tbl Array (Int, Int) Int -> (Int, Int) -> Int
forall i e. Ix i => Array i e -> i -> e
Array.! (Int
i, Int
j)
  -- Tabulate editD' in immutable boxed array (content computed lazily).
  tbl :: Array (Int,Int) Int
  tbl :: Array (Int, Int) Int
tbl = ((Int, Int), (Int, Int))
-> [((Int, Int), Int)] -> Array (Int, Int) Int
forall i e. Ix i => (i, i) -> [(i, e)] -> Array i e
array ((Int
0,Int
0), (Int
n,Int
m)) [ ((Int
i, Int
j), Int -> Int -> Int
editD' Int
i Int
j) | Int
i <- [Int
0..Int
n], Int
j <- [Int
0..Int
m] ]
  editD' :: Int -> Int -> Int
editD' Int
i Int
j =
    case (Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Int
i Int
n, Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Int
j Int
m) of
      -- Interior
      (Ordering
LT, Ordering
LT)
        | Array Int a
xsA Array Int a -> Int -> a
forall i e. Ix i => Array i e -> i -> e
Array.! Int
i a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== Array Int a
ysA Array Int a -> Int -> a
forall i e. Ix i => Array i e -> i -> e
Array.! Int
j
                    -> Int -> Int -> Int
editD Int
i' Int
j'
        | Bool
otherwise -> Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ [Int] -> Int
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum [ Int -> Int -> Int
editD Int
i' Int
j, Int -> Int -> Int
editD Int
i Int
j', Int -> Int -> Int
editD Int
i' Int
j' ]
      -- Border: one list is empty
      (Ordering
EQ, Ordering
LT)      ->  Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
j
      (Ordering
LT, Ordering
EQ)      ->  Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i
      -- Corner (EQ, EQ): both lists are empty
      (Ordering, Ordering)
_             -> Int
0
      -- GT cases are impossible.
    where (Int
i', Int
j') = (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1, Int
j Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
  n :: Int
n   = [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
xs
  m :: Int
m   = [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
ys
  xsA, ysA :: Array Int a
  xsA :: Array Int a
xsA = (Int, Int) -> [a] -> Array Int a
forall i e. Ix i => (i, i) -> [e] -> Array i e
listArray (Int
0, Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) [a]
xs
  ysA :: Array Int a
ysA = (Int, Int) -> [a] -> Array Int a
forall i e. Ix i => (i, i) -> [e] -> Array i e
listArray (Int
0, Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) [a]
ys