{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE CPP #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE ViewPatterns #-}
module Slist
(
Slist
, Size
, slist
, infiniteSlist
, one
, iterate
#if ( __GLASGOW_HASKELL__ > 802 )
, iterate'
#endif
, repeat
, replicate
, cycle
, fromRange
, len
, size
, isEmpty
, head
, safeHead
, last
, safeLast
, init
, tail
, uncons
, map
, reverse
, safeReverse
, intersperse
, intercalate
, transpose
, subsequences
, permutations
, concat
, concatMap
, scanl
, scanl'
, scanl1
, scanr
, scanr1
, unfoldr
, take
, drop
, splitAt
, takeWhile
, dropWhile
, span
, break
, stripPrefix
, safeStripPrefix
, group
, groupBy
, inits
, tails
, isPrefixOf
, safeIsPrefixOf
, isSuffixOf
, safeIsSuffixOf
, isInfixOf
, safeIsInfixOf
, isSubsequenceOf
, safeIsSubsequenceOf
, lookup
, filter
, partition
, at
, unsafeAt
, elemIndex
, elemIndices
, findIndex
, findIndices
, zip
, zip3
, zipWith
, zipWith3
, unzip
, unzip3
, nub
, nubBy
, delete
, deleteBy
, deleteFirstsBy
, diff
, union
, unionBy
, intersect
, intersectBy
, sort
, sortBy
, sortOn
, insert
, insertBy
, genericLength
, genericTake
, genericDrop
, genericSplitAt
, genericAt
, genericUnsafeAt
, genericReplicate
) where
import Control.Applicative (Alternative (empty, (<|>)), liftA2)
import Data.Bifunctor (bimap, first, second)
#if ( __GLASGOW_HASKELL__ == 802 )
import Data.Semigroup (Semigroup (..))
#endif
import Prelude hiding (break, concat, concatMap, cycle, drop, dropWhile, filter, head, init,
iterate, last, lookup, map, repeat, replicate, reverse, scanl, scanl1, scanr,
scanr1, span, splitAt, tail, take, takeWhile, unzip, unzip3, zip, zip3, zipWith,
zipWith3)
import Slist.Size (Size (..), sizes)
import qualified Data.Foldable as F (Foldable (..))
import qualified Data.List as L
import qualified GHC.Exts as L (IsList (..))
import qualified Prelude as P
data Slist a = Slist
{ Slist a -> [a]
sList :: [a]
, Slist a -> Size
sSize :: Size
} deriving stock (Int -> Slist a -> ShowS
[Slist a] -> ShowS
Slist a -> String
(Int -> Slist a -> ShowS)
-> (Slist a -> String) -> ([Slist a] -> ShowS) -> Show (Slist a)
forall a. Show a => Int -> Slist a -> ShowS
forall a. Show a => [Slist a] -> ShowS
forall a. Show a => Slist a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Slist a] -> ShowS
$cshowList :: forall a. Show a => [Slist a] -> ShowS
show :: Slist a -> String
$cshow :: forall a. Show a => Slist a -> String
showsPrec :: Int -> Slist a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Slist a -> ShowS
Show, ReadPrec [Slist a]
ReadPrec (Slist a)
Int -> ReadS (Slist a)
ReadS [Slist a]
(Int -> ReadS (Slist a))
-> ReadS [Slist a]
-> ReadPrec (Slist a)
-> ReadPrec [Slist a]
-> Read (Slist a)
forall a. Read a => ReadPrec [Slist a]
forall a. Read a => ReadPrec (Slist a)
forall a. Read a => Int -> ReadS (Slist a)
forall a. Read a => ReadS [Slist a]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [Slist a]
$creadListPrec :: forall a. Read a => ReadPrec [Slist a]
readPrec :: ReadPrec (Slist a)
$creadPrec :: forall a. Read a => ReadPrec (Slist a)
readList :: ReadS [Slist a]
$creadList :: forall a. Read a => ReadS [Slist a]
readsPrec :: Int -> ReadS (Slist a)
$creadsPrec :: forall a. Read a => Int -> ReadS (Slist a)
Read)
instance (Eq a) => Eq (Slist a) where
(Slist l1 :: [a]
l1 s1 :: Size
s1) == :: Slist a -> Slist a -> Bool
== (Slist l2 :: [a]
l2 s2 :: Size
s2) = Size
s1 Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Size
s2 Bool -> Bool -> Bool
&& [a]
l1 [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== [a]
l2
{-# INLINE (==) #-}
instance (Ord a) => Ord (Slist a) where
compare :: Slist a -> Slist a -> Ordering
compare (Slist l1 :: [a]
l1 _) (Slist l2 :: [a]
l2 _) = [a] -> [a] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare [a]
l1 [a]
l2
{-# INLINE compare #-}
instance Semigroup (Slist a) where
(<>) :: Slist a -> Slist a -> Slist a
(Slist l1 :: [a]
l1 s1 :: Size
s1) <> :: Slist a -> Slist a -> Slist a
<> (Slist l2 :: [a]
l2 s2 :: Size
s2) = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist ([a]
l1 [a] -> [a] -> [a]
forall a. Semigroup a => a -> a -> a
<> [a]
l2) (Size
s1 Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
s2)
{-# INLINE (<>) #-}
instance Monoid (Slist a) where
mempty :: Slist a
mempty :: Slist a
mempty = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [] 0
{-# INLINE mempty #-}
mappend :: Slist a -> Slist a -> Slist a
mappend :: Slist a -> Slist a -> Slist a
mappend = Slist a -> Slist a -> Slist a
forall a. Semigroup a => a -> a -> a
(<>)
{-# INLINE mappend #-}
mconcat :: [Slist a] -> Slist a
mconcat :: [Slist a] -> Slist a
mconcat ls :: [Slist a]
ls = let (l :: [a]
l, s :: Size
s) = (Slist a -> ([a], Size) -> ([a], Size))
-> ([a], Size) -> [Slist a] -> ([a], Size)
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Slist a -> ([a], Size) -> ([a], Size)
f ([], 0) [Slist a]
ls in [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
l Size
s
where
f :: Slist a -> ([a], Size) -> ([a], Size)
f :: Slist a -> ([a], Size) -> ([a], Size)
f (Slist l :: [a]
l s :: Size
s) (xL :: [a]
xL, !Size
xS) = ([a]
l [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
xL, Size
s Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
xS)
{-# INLINE mconcat #-}
instance Functor Slist where
fmap :: (a -> b) -> Slist a -> Slist b
fmap :: (a -> b) -> Slist a -> Slist b
fmap = (a -> b) -> Slist a -> Slist b
forall a b. (a -> b) -> Slist a -> Slist b
map
{-# INLINE fmap #-}
instance Applicative Slist where
pure :: a -> Slist a
pure :: a -> Slist a
pure = a -> Slist a
forall a. a -> Slist a
one
{-# INLINE pure #-}
(<*>) :: Slist (a -> b) -> Slist a -> Slist b
fsl :: Slist (a -> b)
fsl <*> :: Slist (a -> b) -> Slist a -> Slist b
<*> sl :: Slist a
sl = Slist :: forall a. [a] -> Size -> Slist a
Slist
{ sList :: [b]
sList = Slist (a -> b) -> [a -> b]
forall a. Slist a -> [a]
sList Slist (a -> b)
fsl [a -> b] -> [a] -> [b]
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Slist a -> [a]
forall a. Slist a -> [a]
sList Slist a
sl
, sSize :: Size
sSize = Slist (a -> b) -> Size
forall a. Slist a -> Size
sSize Slist (a -> b)
fsl Size -> Size -> Size
forall a. Num a => a -> a -> a
* Slist a -> Size
forall a. Slist a -> Size
sSize Slist a
sl
}
{-# INLINE (<*>) #-}
liftA2 :: (a -> b -> c) -> Slist a -> Slist b -> Slist c
liftA2 :: (a -> b -> c) -> Slist a -> Slist b -> Slist c
liftA2 f :: a -> b -> c
f sla :: Slist a
sla slb :: Slist b
slb = Slist :: forall a. [a] -> Size -> Slist a
Slist
{ sList :: [c]
sList = (a -> b -> c) -> [a] -> [b] -> [c]
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 a -> b -> c
f (Slist a -> [a]
forall a. Slist a -> [a]
sList Slist a
sla) (Slist b -> [b]
forall a. Slist a -> [a]
sList Slist b
slb)
, sSize :: Size
sSize = Slist a -> Size
forall a. Slist a -> Size
sSize Slist a
sla Size -> Size -> Size
forall a. Num a => a -> a -> a
* Slist b -> Size
forall a. Slist a -> Size
sSize Slist b
slb
}
{-# INLINE liftA2 #-}
instance Alternative Slist where
empty :: Slist a
empty :: Slist a
empty = Slist a
forall a. Monoid a => a
mempty
{-# INLINE empty #-}
(<|>) :: Slist a -> Slist a -> Slist a
<|> :: Slist a -> Slist a -> Slist a
(<|>) = Slist a -> Slist a -> Slist a
forall a. Semigroup a => a -> a -> a
(<>)
{-# INLINE (<|>) #-}
instance Monad Slist where
return :: a -> Slist a
return :: a -> Slist a
return = a -> Slist a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
{-# INLINE return #-}
(>>=) :: Slist a -> (a -> Slist b) -> Slist b
sl :: Slist a
sl >>= :: Slist a -> (a -> Slist b) -> Slist b
>>= f :: a -> Slist b
f = [Slist b] -> Slist b
forall a. Monoid a => [a] -> a
mconcat ([Slist b] -> Slist b) -> [Slist b] -> Slist b
forall a b. (a -> b) -> a -> b
$ (a -> Slist b) -> [a] -> [Slist b]
forall a b. (a -> b) -> [a] -> [b]
P.map a -> Slist b
f ([a] -> [Slist b]) -> [a] -> [Slist b]
forall a b. (a -> b) -> a -> b
$ Slist a -> [a]
forall a. Slist a -> [a]
sList Slist a
sl
{-# INLINE (>>=) #-}
instance Foldable Slist where
foldMap :: (Monoid m) => (a -> m) -> Slist a -> m
foldMap :: (a -> m) -> Slist a -> m
foldMap f :: a -> m
f = (a -> m) -> [a] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f ([a] -> m) -> (Slist a -> [a]) -> Slist a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Slist a -> [a]
forall a. Slist a -> [a]
sList
{-# INLINE foldMap #-}
foldr :: (a -> b -> b) -> b -> Slist a -> b
foldr :: (a -> b -> b) -> b -> Slist a -> b
foldr f :: a -> b -> b
f b :: b
b = (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f b
b ([a] -> b) -> (Slist a -> [a]) -> Slist a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Slist a -> [a]
forall a. Slist a -> [a]
sList
{-# INLINE foldr #-}
elem :: (Eq a) => a -> Slist a -> Bool
elem :: a -> Slist a -> Bool
elem a :: a
a = a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
elem a
a ([a] -> Bool) -> (Slist a -> [a]) -> Slist a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Slist a -> [a]
forall a. Slist a -> [a]
sList
{-# INLINE elem #-}
maximum :: (Ord a) => Slist a -> a
maximum :: Slist a -> a
maximum = [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum ([a] -> a) -> (Slist a -> [a]) -> Slist a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Slist a -> [a]
forall a. Slist a -> [a]
sList
{-# INLINE maximum #-}
minimum :: (Ord a) => Slist a -> a
minimum :: Slist a -> a
minimum = [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum ([a] -> a) -> (Slist a -> [a]) -> Slist a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Slist a -> [a]
forall a. Slist a -> [a]
sList
{-# INLINE minimum #-}
sum :: (Num a) => Slist a -> a
sum :: Slist a -> a
sum = (a -> a -> a) -> a -> [a] -> a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' a -> a -> a
forall a. Num a => a -> a -> a
(+) 0 ([a] -> a) -> (Slist a -> [a]) -> Slist a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Slist a -> [a]
forall a. Slist a -> [a]
sList
{-# INLINE sum #-}
product :: (Num a) => Slist a -> a
product :: Slist a -> a
product = (a -> a -> a) -> a -> [a] -> a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' a -> a -> a
forall a. Num a => a -> a -> a
(*) 1 ([a] -> a) -> (Slist a -> [a]) -> Slist a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Slist a -> [a]
forall a. Slist a -> [a]
sList
{-# INLINE product #-}
null :: Slist a -> Bool
null :: Slist a -> Bool
null = Slist a -> Bool
forall a. Slist a -> Bool
isEmpty
{-# INLINE null #-}
length :: Slist a -> Int
length :: Slist a -> Int
length = Slist a -> Int
forall a. Slist a -> Int
len
{-# INLINE length #-}
toList :: Slist a -> [a]
toList :: Slist a -> [a]
toList = Slist a -> [a]
forall a. Slist a -> [a]
sList
{-# INLINE toList #-}
instance Traversable Slist where
traverse :: (Applicative f) => (a -> f b) -> Slist a -> f (Slist b)
traverse :: (a -> f b) -> Slist a -> f (Slist b)
traverse f :: a -> f b
f (Slist l :: [a]
l s :: Size
s) = ([b] -> Size -> Slist b
forall a. [a] -> Size -> Slist a
`Slist` Size
s) ([b] -> Slist b) -> f [b] -> f (Slist b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> [a] -> f [b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse a -> f b
f [a]
l
{-# INLINE traverse #-}
instance L.IsList (Slist a) where
type (Item (Slist a)) = a
fromList :: [a] -> Slist a
fromList :: [a] -> Slist a
fromList = [a] -> Slist a
forall a. [a] -> Slist a
slist
{-# INLINE fromList #-}
toList :: Slist a -> [a]
toList :: Slist a -> [a]
toList = Slist a -> [a]
forall a. Slist a -> [a]
sList
{-# INLINE toList #-}
fromListN :: Int -> [a] -> Slist a
fromListN :: Int -> [a] -> Slist a
fromListN n :: Int
n l :: [a]
l = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
l (Size -> Slist a) -> Size -> Slist a
forall a b. (a -> b) -> a -> b
$ Int -> Size
Size Int
n
{-# INLINE fromListN #-}
slist :: [a] -> Slist a
slist :: [a] -> Slist a
slist l :: [a]
l = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
l (Int -> Size
Size (Int -> Size) -> Int -> Size
forall a b. (a -> b) -> a -> b
$ [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
l)
{-# INLINE slist #-}
infiniteSlist :: [a] -> Slist a
infiniteSlist :: [a] -> Slist a
infiniteSlist l :: [a]
l = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
l Size
Infinity
{-# INLINE infiniteSlist #-}
one :: a -> Slist a
one :: a -> Slist a
one a :: a
a = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a
a] 1
{-# INLINE one #-}
iterate :: (a -> a) -> a -> Slist a
iterate :: (a -> a) -> a -> Slist a
iterate f :: a -> a
f = [a] -> Slist a
forall a. [a] -> Slist a
infiniteSlist ([a] -> Slist a) -> (a -> [a]) -> a -> Slist a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a) -> a -> [a]
forall a. (a -> a) -> a -> [a]
L.iterate a -> a
f
{-# INLINE iterate #-}
#if ( __GLASGOW_HASKELL__ > 802 )
iterate' :: (a -> a) -> a -> Slist a
iterate' :: (a -> a) -> a -> Slist a
iterate' f :: a -> a
f = [a] -> Slist a
forall a. [a] -> Slist a
infiniteSlist ([a] -> Slist a) -> (a -> [a]) -> a -> Slist a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a) -> a -> [a]
forall a. (a -> a) -> a -> [a]
L.iterate' a -> a
f
{-# INLINE iterate' #-}
#endif
repeat :: a -> Slist a
repeat :: a -> Slist a
repeat = [a] -> Slist a
forall a. [a] -> Slist a
infiniteSlist ([a] -> Slist a) -> (a -> [a]) -> a -> Slist a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> [a]
forall a. a -> [a]
L.repeat
{-# INLINE repeat #-}
replicate :: Int -> a -> Slist a
replicate :: Int -> a -> Slist a
replicate n :: Int
n x :: a
x
| Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= 0 = Slist a
forall a. Monoid a => a
mempty
| Bool
otherwise = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist (Int -> a -> [a]
forall a. Int -> a -> [a]
L.replicate Int
n a
x) (Size -> Slist a) -> Size -> Slist a
forall a b. (a -> b) -> a -> b
$ Int -> Size
Size Int
n
{-# INLINE replicate #-}
cycle :: Slist a -> Slist a
cycle :: Slist a -> Slist a
cycle sl :: Slist a
sl@(Slist _ Infinity) = Slist a
sl
cycle Slist{..} = [a] -> Slist a
forall a. [a] -> Slist a
infiniteSlist ([a] -> Slist a) -> [a] -> Slist a
forall a b. (a -> b) -> a -> b
$ [a] -> [a]
forall a. [a] -> [a]
L.cycle [a]
sList
{-# INLINE cycle #-}
fromRange :: Enum a => a -> a -> Slist a
fromRange :: a -> a -> Slist a
fromRange from :: a
from to :: a
to = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a
from..a
to] Size
s
where
s :: Size
s :: Size
s = Int -> Size
Size (Int -> Size) -> Int -> Size
forall a b. (a -> b) -> a -> b
$ Int -> Int -> Int
forall a. Ord a => a -> a -> a
max 0 (a -> Int
forall a. Enum a => a -> Int
fromEnum a
to Int -> Int -> Int
forall a. Num a => a -> a -> a
- a -> Int
forall a. Enum a => a -> Int
fromEnum a
from Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1)
{-# INLINE fromRange #-}
len :: Slist a -> Int
len :: Slist a -> Int
len Slist{..} = case Size
sSize of
Infinity -> Int
forall a. Bounded a => a
maxBound
Size n :: Int
n -> Int
n
{-# INLINE len #-}
size :: Slist a -> Size
size :: Slist a -> Size
size = Slist a -> Size
forall a. Slist a -> Size
sSize
{-# INLINE size #-}
isEmpty :: Slist a -> Bool
isEmpty :: Slist a -> Bool
isEmpty = (Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== 0) (Size -> Bool) -> (Slist a -> Size) -> Slist a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Slist a -> Size
forall a. Slist a -> Size
size
{-# INLINE isEmpty #-}
head :: Slist a -> a
head :: Slist a -> a
head = [a] -> a
forall a. [a] -> a
P.head ([a] -> a) -> (Slist a -> [a]) -> Slist a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Slist a -> [a]
forall a. Slist a -> [a]
sList
{-# INLINE head #-}
safeHead :: Slist a -> Maybe a
safeHead :: Slist a -> Maybe a
safeHead Slist{..} = case Size
sSize of
Size 0 -> Maybe a
forall a. Maybe a
Nothing
_ -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> a -> Maybe a
forall a b. (a -> b) -> a -> b
$ [a] -> a
forall a. [a] -> a
P.head [a]
sList
{-# INLINE safeHead #-}
last :: Slist a -> a
last :: Slist a -> a
last = [a] -> a
forall a. [a] -> a
P.last ([a] -> a) -> (Slist a -> [a]) -> Slist a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Slist a -> [a]
forall a. Slist a -> [a]
sList
{-# INLINE last #-}
safeLast :: Slist a -> Maybe a
safeLast :: Slist a -> Maybe a
safeLast Slist{..} = case Size
sSize of
Infinity -> Maybe a
forall a. Maybe a
Nothing
Size 0 -> Maybe a
forall a. Maybe a
Nothing
_ -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> a -> Maybe a
forall a b. (a -> b) -> a -> b
$ [a] -> a
forall a. [a] -> a
P.last [a]
sList
{-# INLINE safeLast #-}
tail :: Slist a -> Slist a
tail :: Slist a -> Slist a
tail Slist{..} = case Size
sSize of
Size 0 -> Slist a
forall a. Monoid a => a
mempty
_ -> [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist (Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
P.drop 1 [a]
sList) (Size
sSize Size -> Size -> Size
forall a. Num a => a -> a -> a
- 1)
{-# INLINE tail #-}
init :: Slist a -> Slist a
init :: Slist a -> Slist a
init sl :: Slist a
sl@Slist{..} = case Size
sSize of
Infinity -> Slist a
sl
Size 0 -> Slist a
forall a. Monoid a => a
mempty
_ -> [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist ([a] -> [a]
forall a. [a] -> [a]
P.init [a]
sList) (Size
sSize Size -> Size -> Size
forall a. Num a => a -> a -> a
- 1)
{-# INLINE init #-}
uncons :: Slist a -> Maybe (a, Slist a)
uncons :: Slist a -> Maybe (a, Slist a)
uncons (Slist [] _) = Maybe (a, Slist a)
forall a. Maybe a
Nothing
uncons (Slist (x :: a
x:xs :: [a]
xs) s :: Size
s) = (a, Slist a) -> Maybe (a, Slist a)
forall a. a -> Maybe a
Just (a
x, [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
xs (Size -> Slist a) -> Size -> Slist a
forall a b. (a -> b) -> a -> b
$ Size
s Size -> Size -> Size
forall a. Num a => a -> a -> a
- 1)
{-# INLINE uncons #-}
map :: (a -> b) -> Slist a -> Slist b
map :: (a -> b) -> Slist a -> Slist b
map f :: a -> b
f Slist{..} = [b] -> Size -> Slist b
forall a. [a] -> Size -> Slist a
Slist ((a -> b) -> [a] -> [b]
forall a b. (a -> b) -> [a] -> [b]
P.map a -> b
f [a]
sList) Size
sSize
{-# INLINE map #-}
reverse :: Slist a -> Slist a
reverse :: Slist a -> Slist a
reverse Slist{..} = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist ([a] -> [a]
forall a. [a] -> [a]
L.reverse [a]
sList) Size
sSize
{-# INLINE reverse #-}
safeReverse :: Slist a -> Slist a
safeReverse :: Slist a -> Slist a
safeReverse sl :: Slist a
sl@(Slist _ Infinity) = Slist a
sl
safeReverse sl :: Slist a
sl = Slist a -> Slist a
forall a. Slist a -> Slist a
reverse Slist a
sl
{-# INLINE safeReverse #-}
intersperse :: a -> Slist a -> Slist a
intersperse :: a -> Slist a -> Slist a
intersperse _ sl :: Slist a
sl@(Slist _ (Size 0)) = Slist a
sl
intersperse a :: a
a Slist{..} = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist (a -> [a] -> [a]
forall a. a -> [a] -> [a]
L.intersperse a
a [a]
sList) (2 Size -> Size -> Size
forall a. Num a => a -> a -> a
* Size
sSize Size -> Size -> Size
forall a. Num a => a -> a -> a
- 1)
{-# INLINE intersperse #-}
intercalate :: Slist a -> Slist (Slist a) -> Slist a
intercalate :: Slist a -> Slist (Slist a) -> Slist a
intercalate x :: Slist a
x = (Slist a -> Slist a -> Slist a)
-> Slist a -> Slist (Slist a) -> Slist a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Slist a -> Slist a -> Slist a
forall a. Semigroup a => a -> a -> a
(<>) Slist a
forall a. Monoid a => a
mempty (Slist (Slist a) -> Slist a)
-> (Slist (Slist a) -> Slist (Slist a))
-> Slist (Slist a)
-> Slist a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Slist a -> Slist (Slist a) -> Slist (Slist a)
forall a. a -> Slist a -> Slist a
intersperse Slist a
x
{-# INLINE intercalate #-}
transpose :: Slist (Slist a) -> Slist (Slist a)
transpose :: Slist (Slist a) -> Slist (Slist a)
transpose (Slist l :: [Slist a]
l _) = Slist :: forall a. [a] -> Size -> Slist a
Slist
{ sList :: [Slist a]
sList = ([a] -> Slist a) -> [[a]] -> [Slist a]
forall a b. (a -> b) -> [a] -> [b]
P.map [a] -> Slist a
forall a. [a] -> Slist a
slist ([[a]] -> [Slist a]) -> [[a]] -> [Slist a]
forall a b. (a -> b) -> a -> b
$ [[a]] -> [[a]]
forall a. [[a]] -> [[a]]
L.transpose ([[a]] -> [[a]]) -> [[a]] -> [[a]]
forall a b. (a -> b) -> a -> b
$ (Slist a -> [a]) -> [Slist a] -> [[a]]
forall a b. (a -> b) -> [a] -> [b]
P.map Slist a -> [a]
forall a. Slist a -> [a]
sList [Slist a]
l
, sSize :: Size
sSize = [Size] -> Size
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum ([Size] -> Size) -> [Size] -> Size
forall a b. (a -> b) -> a -> b
$ (Slist a -> Size) -> [Slist a] -> [Size]
forall a b. (a -> b) -> [a] -> [b]
P.map Slist a -> Size
forall a. Slist a -> Size
sSize [Slist a]
l
}
{-# INLINE transpose #-}
subsequences :: Slist a -> Slist (Slist a)
subsequences :: Slist a -> Slist (Slist a)
subsequences Slist{..} = Slist :: forall a. [a] -> Size -> Slist a
Slist
{ sList :: [Slist a]
sList = ([a] -> Slist a) -> [[a]] -> [Slist a]
forall a b. (a -> b) -> [a] -> [b]
P.map [a] -> Slist a
forall a. [a] -> Slist a
slist ([[a]] -> [Slist a]) -> [[a]] -> [Slist a]
forall a b. (a -> b) -> a -> b
$ [a] -> [[a]]
forall a. [a] -> [[a]]
L.subsequences [a]
sList
, sSize :: Size
sSize = Size -> Size
newSize Size
sSize
}
where
newSize :: Size -> Size
newSize :: Size -> Size
newSize Infinity = Size
Infinity
newSize (Size n :: Int
n) = Int -> Size
Size (Int -> Size) -> Int -> Size
forall a b. (a -> b) -> a -> b
$ 2 Int -> Integer -> Int
forall a b. (Num a, Integral b) => a -> b -> a
^ Int -> Integer
forall a. Integral a => a -> Integer
toInteger Int
n
{-# INLINE subsequences #-}
permutations :: Slist a -> Slist (Slist a)
permutations :: Slist a -> Slist (Slist a)
permutations (Slist l :: [a]
l s :: Size
s) = Slist :: forall a. [a] -> Size -> Slist a
Slist
{ sList :: [Slist a]
sList = ([a] -> Slist a) -> [[a]] -> [Slist a]
forall a b. (a -> b) -> [a] -> [b]
P.map ([a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
`Slist` Size
s) ([[a]] -> [Slist a]) -> [[a]] -> [Slist a]
forall a b. (a -> b) -> a -> b
$ [a] -> [[a]]
forall a. [a] -> [[a]]
L.permutations [a]
l
, sSize :: Size
sSize = Size -> Size
fact Size
s
}
where
fact :: Size -> Size
fact :: Size -> Size
fact Infinity = Size
Infinity
fact (Size n :: Int
n) = Int -> Size
Size (Int -> Size) -> Int -> Size
forall a b. (a -> b) -> a -> b
$ Int -> Int -> Int
go 1 Int
n
go :: Int -> Int -> Int
go :: Int -> Int -> Int
go !Int
acc 0 = Int
acc
go !Int
acc n :: Int
n = Int -> Int -> Int
go (Int
acc Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
n) (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- 1)
{-# INLINE permutations #-}
concat :: Foldable t => t (Slist a) -> Slist a
concat :: t (Slist a) -> Slist a
concat = (Slist a -> Slist a -> Slist a)
-> Slist a -> t (Slist a) -> Slist a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Slist a -> Slist a -> Slist a
forall a. Semigroup a => a -> a -> a
(<>) Slist a
forall a. Monoid a => a
mempty
{-# INLINE concat #-}
concatMap :: Foldable t => (a -> Slist b) -> t a -> Slist b
concatMap :: (a -> Slist b) -> t a -> Slist b
concatMap = (a -> Slist b) -> t a -> Slist b
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap
{-# INLINE concatMap #-}
scanl :: (b -> a -> b) -> b -> Slist a -> Slist b
scanl :: (b -> a -> b) -> b -> Slist a -> Slist b
scanl f :: b -> a -> b
f b :: b
b Slist{..} = [b] -> Size -> Slist b
forall a. [a] -> Size -> Slist a
Slist ((b -> a -> b) -> b -> [a] -> [b]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
L.scanl b -> a -> b
f b
b [a]
sList) (Size
sSize Size -> Size -> Size
forall a. Num a => a -> a -> a
+ 1)
{-# INLINE scanl #-}
scanl' :: (b -> a -> b) -> b -> Slist a -> Slist b
scanl' :: (b -> a -> b) -> b -> Slist a -> Slist b
scanl' f :: b -> a -> b
f b :: b
b Slist{..} = [b] -> Size -> Slist b
forall a. [a] -> Size -> Slist a
Slist ((b -> a -> b) -> b -> [a] -> [b]
forall b a. (b -> a -> b) -> b -> [a] -> [b]
L.scanl' b -> a -> b
f b
b [a]
sList) (Size
sSize Size -> Size -> Size
forall a. Num a => a -> a -> a
+ 1)
{-# INLINE scanl' #-}
scanl1 :: (a -> a -> a) -> Slist a -> Slist a
scanl1 :: (a -> a -> a) -> Slist a -> Slist a
scanl1 f :: a -> a -> a
f Slist{..} = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist ((a -> a -> a) -> [a] -> [a]
forall a. (a -> a -> a) -> [a] -> [a]
L.scanl1 a -> a -> a
f [a]
sList) Size
sSize
{-# INLINE scanl1 #-}
scanr :: (a -> b -> b) -> b -> Slist a -> Slist b
scanr :: (a -> b -> b) -> b -> Slist a -> Slist b
scanr f :: a -> b -> b
f b :: b
b Slist{..} = [b] -> Size -> Slist b
forall a. [a] -> Size -> Slist a
Slist ((a -> b -> b) -> b -> [a] -> [b]
forall a b. (a -> b -> b) -> b -> [a] -> [b]
L.scanr a -> b -> b
f b
b [a]
sList) (Size
sSize Size -> Size -> Size
forall a. Num a => a -> a -> a
+ 1)
{-# INLINE scanr #-}
scanr1 :: (a -> a -> a) -> Slist a -> Slist a
scanr1 :: (a -> a -> a) -> Slist a -> Slist a
scanr1 f :: a -> a -> a
f Slist{..} = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist ((a -> a -> a) -> [a] -> [a]
forall a. (a -> a -> a) -> [a] -> [a]
L.scanr1 a -> a -> a
f [a]
sList) Size
sSize
{-# INLINE scanr1 #-}
unfoldr :: forall a b . (b -> Maybe (a, b)) -> b -> Slist a
unfoldr :: (b -> Maybe (a, b)) -> b -> Slist a
unfoldr f :: b -> Maybe (a, b)
f def :: b
def = let (s :: Int
s, l :: [a]
l) = b -> (Int, [a])
go b
def in [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
l (Size -> Slist a) -> Size -> Slist a
forall a b. (a -> b) -> a -> b
$ Int -> Size
Size Int
s
where
go :: b -> (Int, [a])
go :: b -> (Int, [a])
go b :: b
b = case b -> Maybe (a, b)
f b
b of
Just (a :: a
a, newB :: b
newB) -> (Int -> Int) -> ([a] -> [a]) -> (Int, [a]) -> (Int, [a])
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap (Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1) (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ((Int, [a]) -> (Int, [a])) -> (Int, [a]) -> (Int, [a])
forall a b. (a -> b) -> a -> b
$ b -> (Int, [a])
go b
newB
Nothing -> (0, [])
{-# INLINE unfoldr #-}
take :: Int -> Slist a -> Slist a
take :: Int -> Slist a -> Slist a
take i :: Int
i sl :: Slist a
sl@Slist{..}
| Int -> Size
Size Int
i Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
>= Size
sSize = Slist a
sl
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= 0 = Slist a
forall a. Monoid a => a
mempty
| Bool
otherwise = Slist :: forall a. [a] -> Size -> Slist a
Slist
{ sList :: [a]
sList = Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
P.take Int
i [a]
sList
, sSize :: Size
sSize = Int -> Size
Size Int
i
}
{-# INLINE take #-}
drop :: Int -> Slist a -> Slist a
drop :: Int -> Slist a -> Slist a
drop i :: Int
i sl :: Slist a
sl@Slist{..}
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= 0 = Slist a
sl
| Int -> Size
Size Int
i Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
>= Size
sSize = Slist a
forall a. Monoid a => a
mempty
| Bool
otherwise = Slist :: forall a. [a] -> Size -> Slist a
Slist
{ sList :: [a]
sList = Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
P.drop Int
i [a]
sList
, sSize :: Size
sSize = Size
sSize Size -> Size -> Size
forall a. Num a => a -> a -> a
- Int -> Size
Size Int
i
}
{-# INLINE drop #-}
splitAt :: Int -> Slist a -> (Slist a, Slist a)
splitAt :: Int -> Slist a -> (Slist a, Slist a)
splitAt i :: Int
i sl :: Slist a
sl@Slist{..}
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= 0 = (Slist a
forall a. Monoid a => a
mempty, Slist a
sl)
| Int -> Size
Size Int
i Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
>= Size
sSize = (Slist a
sl, Slist a
forall a. Monoid a => a
mempty)
| Bool
otherwise =
let (l1 :: [a]
l1, l2 :: [a]
l2) = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
P.splitAt Int
i [a]
sList
s2 :: Size
s2 = Size
sSize Size -> Size -> Size
forall a. Num a => a -> a -> a
- Int -> Size
Size Int
i
in ([a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
l1 (Size -> Slist a) -> Size -> Slist a
forall a b. (a -> b) -> a -> b
$ Int -> Size
Size Int
i, [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
l2 Size
s2)
{-# INLINE splitAt #-}
takeWhile :: forall a . (a -> Bool) -> Slist a -> Slist a
takeWhile :: (a -> Bool) -> Slist a -> Slist a
takeWhile p :: a -> Bool
p Slist{..} = let (s :: Int
s, l :: [a]
l) = Int -> [a] -> (Int, [a])
go 0 [a]
sList in
[a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
l (Size -> Slist a) -> Size -> Slist a
forall a b. (a -> b) -> a -> b
$ Int -> Size
Size Int
s
where
go :: Int -> [a] -> (Int, [a])
go :: Int -> [a] -> (Int, [a])
go !Int
n [] = (Int
n, [])
go !Int
n (x :: a
x:xs :: [a]
xs) =
if a -> Bool
p a
x
then let (i :: Int
i, l :: [a]
l) = Int -> [a] -> (Int, [a])
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1) [a]
xs in (Int
i, a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
l)
else (Int
n, [])
{-# INLINE takeWhile #-}
dropWhile :: forall a . (a -> Bool) -> Slist a -> Slist a
dropWhile :: (a -> Bool) -> Slist a -> Slist a
dropWhile p :: a -> Bool
p (Slist l :: [a]
l Infinity) = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist ((a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
P.dropWhile a -> Bool
p [a]
l) Size
Infinity
dropWhile p :: a -> Bool
p Slist{..} = let (s :: Int
s, l :: [a]
l) = Int -> [a] -> (Int, [a])
go 0 [a]
sList in
[a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
l (Size
sSize Size -> Size -> Size
forall a. Num a => a -> a -> a
- Int -> Size
Size Int
s)
where
go :: Int -> [a] -> (Int, [a])
go :: Int -> [a] -> (Int, [a])
go !Int
n [] = (Int
n, [])
go !Int
n (x :: a
x:xs :: [a]
xs) =
if a -> Bool
p a
x
then Int -> [a] -> (Int, [a])
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1) [a]
xs
else (Int
n, a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs)
{-# INLINE dropWhile #-}
span :: forall a . (a -> Bool) -> Slist a -> (Slist a, Slist a)
span :: (a -> Bool) -> Slist a -> (Slist a, Slist a)
span p :: a -> Bool
p Slist{..} = let (s :: Int
s, l :: [a]
l, r :: [a]
r) = Int -> [a] -> (Int, [a], [a])
go 0 [a]
sList in
( [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
l (Size -> Slist a) -> Size -> Slist a
forall a b. (a -> b) -> a -> b
$ Int -> Size
Size Int
s
, [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
r (Size
sSize Size -> Size -> Size
forall a. Num a => a -> a -> a
- Int -> Size
Size Int
s)
)
where
go :: Int -> [a] -> (Int, [a], [a])
go :: Int -> [a] -> (Int, [a], [a])
go !Int
n [] = (Int
n, [], [])
go !Int
n (x :: a
x:xs :: [a]
xs) =
if a -> Bool
p a
x
then let (s :: Int
s, l :: [a]
l, r :: [a]
r) = Int -> [a] -> (Int, [a], [a])
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1) [a]
xs in (Int
s, a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
l, [a]
r)
else (Int
n, [], a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs)
{-# INLINE span #-}
break :: (a -> Bool) -> Slist a -> (Slist a, Slist a)
break :: (a -> Bool) -> Slist a -> (Slist a, Slist a)
break p :: a -> Bool
p = (a -> Bool) -> Slist a -> (Slist a, Slist a)
forall a. (a -> Bool) -> Slist a -> (Slist a, Slist a)
span (Bool -> Bool
not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
p)
{-# INLINE break #-}
stripPrefix :: Eq a => Slist a -> Slist a -> Maybe (Slist a)
stripPrefix :: Slist a -> Slist a -> Maybe (Slist a)
stripPrefix (Slist l1 :: [a]
l1 s1 :: Size
s1) f :: Slist a
f@(Slist l2 :: [a]
l2 s2 :: Size
s2)
| Size
s1 Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Int -> Size
Size 0 = Slist a -> Maybe (Slist a)
forall a. a -> Maybe a
Just Slist a
f
| Size
s1 Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
> Size
s2 = Maybe (Slist a)
forall a. Maybe a
Nothing
| Bool
otherwise = (\l :: [a]
l -> [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
l (Size -> Slist a) -> Size -> Slist a
forall a b. (a -> b) -> a -> b
$ Size
s2 Size -> Size -> Size
forall a. Num a => a -> a -> a
- Size
s1) ([a] -> Slist a) -> Maybe [a] -> Maybe (Slist a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a] -> [a] -> Maybe [a]
forall a. Eq a => [a] -> [a] -> Maybe [a]
L.stripPrefix [a]
l1 [a]
l2
{-# INLINE stripPrefix #-}
safeStripPrefix :: Eq a => Slist a -> Slist a -> Maybe (Slist a)
safeStripPrefix :: Slist a -> Slist a -> Maybe (Slist a)
safeStripPrefix (Slist _ Infinity) (Slist _ Infinity) = Maybe (Slist a)
forall a. Maybe a
Nothing
safeStripPrefix sl1 :: Slist a
sl1 sl2 :: Slist a
sl2 = Slist a -> Slist a -> Maybe (Slist a)
forall a. Eq a => Slist a -> Slist a -> Maybe (Slist a)
stripPrefix Slist a
sl1 Slist a
sl2
{-# INLINE safeStripPrefix #-}
group :: Eq a => Slist a -> Slist (Slist a)
group :: Slist a -> Slist (Slist a)
group = (a -> a -> Bool) -> Slist a -> Slist (Slist a)
forall a. (a -> a -> Bool) -> Slist a -> Slist (Slist a)
groupBy a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)
{-# INLINE group #-}
groupBy :: (a -> a -> Bool) -> Slist a -> Slist (Slist a)
groupBy :: (a -> a -> Bool) -> Slist a -> Slist (Slist a)
groupBy p :: a -> a -> Bool
p (Slist l :: [a]
l Infinity) = [Slist a] -> Slist (Slist a)
forall a. [a] -> Slist a
infiniteSlist ([Slist a] -> Slist (Slist a)) -> [Slist a] -> Slist (Slist a)
forall a b. (a -> b) -> a -> b
$ ([a] -> Slist a) -> [[a]] -> [Slist a]
forall a b. (a -> b) -> [a] -> [b]
P.map [a] -> Slist a
forall a. [a] -> Slist a
slist ([[a]] -> [Slist a]) -> [[a]] -> [Slist a]
forall a b. (a -> b) -> a -> b
$ (a -> a -> Bool) -> [a] -> [[a]]
forall a. (a -> a -> Bool) -> [a] -> [[a]]
L.groupBy a -> a -> Bool
p [a]
l
groupBy p :: a -> a -> Bool
p Slist{..} = [Slist a] -> Slist (Slist a)
forall a. [a] -> Slist a
slist ([Slist a] -> Slist (Slist a)) -> [Slist a] -> Slist (Slist a)
forall a b. (a -> b) -> a -> b
$ ([a] -> Slist a) -> [[a]] -> [Slist a]
forall a b. (a -> b) -> [a] -> [b]
P.map [a] -> Slist a
forall a. [a] -> Slist a
slist ([[a]] -> [Slist a]) -> [[a]] -> [Slist a]
forall a b. (a -> b) -> a -> b
$ (a -> a -> Bool) -> [a] -> [[a]]
forall a. (a -> a -> Bool) -> [a] -> [[a]]
L.groupBy a -> a -> Bool
p [a]
sList
{-# INLINE groupBy #-}
inits :: Slist a -> Slist (Slist a)
inits :: Slist a -> Slist (Slist a)
inits (Slist l :: [a]
l s :: Size
s) = Slist :: forall a. [a] -> Size -> Slist a
Slist
{ sList :: [Slist a]
sList = ([a] -> Size -> Slist a) -> [[a]] -> [Size] -> [Slist a]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
L.zipWith [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist ([a] -> [[a]]
forall a. [a] -> [[a]]
L.inits [a]
l) ([Size] -> [Slist a]) -> [Size] -> [Slist a]
forall a b. (a -> b) -> a -> b
$ Size -> [Size]
sizes Size
s
, sSize :: Size
sSize = Size
s Size -> Size -> Size
forall a. Num a => a -> a -> a
+ 1
}
{-# INLINE inits #-}
tails :: Slist a -> Slist (Slist a)
tails :: Slist a -> Slist (Slist a)
tails (Slist l :: [a]
l Infinity) = [Slist a] -> Slist (Slist a)
forall a. [a] -> Slist a
infiniteSlist ([Slist a] -> Slist (Slist a)) -> [Slist a] -> Slist (Slist a)
forall a b. (a -> b) -> a -> b
$ ([a] -> Slist a) -> [[a]] -> [Slist a]
forall a b. (a -> b) -> [a] -> [b]
P.map [a] -> Slist a
forall a. [a] -> Slist a
infiniteSlist ([a] -> [[a]]
forall a. [a] -> [[a]]
L.tails [a]
l)
tails (Slist l :: [a]
l s :: Size
s@(Size n :: Int
n)) = Slist :: forall a. [a] -> Size -> Slist a
Slist
{ sList :: [Slist a]
sList = ([a] -> Int -> Slist a) -> [[a]] -> [Int] -> [Slist a]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
L.zipWith (\li :: [a]
li i :: Int
i -> [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
li (Size -> Slist a) -> Size -> Slist a
forall a b. (a -> b) -> a -> b
$ Int -> Size
Size Int
i) ([a] -> [[a]]
forall a. [a] -> [[a]]
L.tails [a]
l) [Int
n, Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- 1 .. 0]
, sSize :: Size
sSize = Size
s Size -> Size -> Size
forall a. Num a => a -> a -> a
+ 1
}
{-# INLINE tails #-}
isPrefixOf :: Eq a => Slist a -> Slist a -> Bool
isPrefixOf :: Slist a -> Slist a -> Bool
isPrefixOf (Slist l1 :: [a]
l1 s1 :: Size
s1) (Slist l2 :: [a]
l2 s2 :: Size
s2)
| Size
s1 Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
> Size
s2 = Bool
False
| Bool
otherwise = [a]
l1 [a] -> [a] -> Bool
forall a. Eq a => [a] -> [a] -> Bool
`L.isPrefixOf` [a]
l2
{-# INLINE isPrefixOf #-}
safeIsPrefixOf :: Eq a => Slist a -> Slist a -> Bool
safeIsPrefixOf :: Slist a -> Slist a -> Bool
safeIsPrefixOf sl1 :: Slist a
sl1@(Slist _ s1 :: Size
s1) sl2 :: Slist a
sl2@(Slist _ s2 :: Size
s2)
| Size
s1 Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Size
Infinity Bool -> Bool -> Bool
&& Size
s2 Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Size
Infinity = Bool
False
| Bool
otherwise = Slist a
sl1 Slist a -> Slist a -> Bool
forall a. Eq a => Slist a -> Slist a -> Bool
`isPrefixOf` Slist a
sl2
{-# INLINE safeIsPrefixOf #-}
isSuffixOf :: Eq a => Slist a -> Slist a -> Bool
isSuffixOf :: Slist a -> Slist a -> Bool
isSuffixOf (Slist l1 :: [a]
l1 s1 :: Size
s1) (Slist l2 :: [a]
l2 s2 :: Size
s2)
| Size
s1 Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
> Size
s2 = Bool
False
| Bool
otherwise = [a]
l1 [a] -> [a] -> Bool
forall a. Eq a => [a] -> [a] -> Bool
`L.isSuffixOf` [a]
l2
{-# INLINE isSuffixOf #-}
safeIsSuffixOf :: Eq a => Slist a -> Slist a -> Bool
safeIsSuffixOf :: Slist a -> Slist a -> Bool
safeIsSuffixOf sl1 :: Slist a
sl1 sl2 :: Slist a
sl2@(Slist _ s2 :: Size
s2)
| Size
s2 Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Size
Infinity = Bool
False
| Bool
otherwise = Slist a
sl1 Slist a -> Slist a -> Bool
forall a. Eq a => Slist a -> Slist a -> Bool
`isSuffixOf` Slist a
sl2
{-# INLINE safeIsSuffixOf #-}
isInfixOf :: Eq a => Slist a -> Slist a -> Bool
isInfixOf :: Slist a -> Slist a -> Bool
isInfixOf (Slist l1 :: [a]
l1 s1 :: Size
s1) (Slist l2 :: [a]
l2 s2 :: Size
s2)
| Size
s1 Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
> Size
s2 = Bool
False
| Bool
otherwise = [a]
l1 [a] -> [a] -> Bool
forall a. Eq a => [a] -> [a] -> Bool
`L.isInfixOf` [a]
l2
{-# INLINE isInfixOf #-}
safeIsInfixOf :: Eq a => Slist a -> Slist a -> Bool
safeIsInfixOf :: Slist a -> Slist a -> Bool
safeIsInfixOf sl1 :: Slist a
sl1@(Slist _ s1 :: Size
s1) sl2 :: Slist a
sl2@(Slist _ s2 :: Size
s2)
| Size
s1 Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Size
Infinity Bool -> Bool -> Bool
&& Size
s2 Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Size
Infinity = Bool
False
| Bool
otherwise = Slist a
sl1 Slist a -> Slist a -> Bool
forall a. Eq a => Slist a -> Slist a -> Bool
`isInfixOf` Slist a
sl2
{-# INLINE safeIsInfixOf #-}
isSubsequenceOf :: Eq a => Slist a -> Slist a -> Bool
isSubsequenceOf :: Slist a -> Slist a -> Bool
isSubsequenceOf (Slist l1 :: [a]
l1 s1 :: Size
s1) (Slist l2 :: [a]
l2 s2 :: Size
s2)
| Size
s1 Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
> Size
s2 = Bool
False
| Bool
otherwise = [a] -> [a] -> Bool
forall a. Eq a => [a] -> [a] -> Bool
L.isSubsequenceOf [a]
l1 [a]
l2
{-# INLINE isSubsequenceOf #-}
safeIsSubsequenceOf :: Eq a => Slist a -> Slist a -> Bool
safeIsSubsequenceOf :: Slist a -> Slist a -> Bool
safeIsSubsequenceOf sl1 :: Slist a
sl1@(Slist _ s1 :: Size
s1) sl2 :: Slist a
sl2@(Slist _ s2 :: Size
s2)
| Size
s1 Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Size
Infinity Bool -> Bool -> Bool
&& Size
s2 Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Size
Infinity = Bool
False
| Bool
otherwise = Slist a -> Slist a -> Bool
forall a. Eq a => Slist a -> Slist a -> Bool
isSubsequenceOf Slist a
sl1 Slist a
sl2
{-# INLINE safeIsSubsequenceOf #-}
lookup :: Eq a => a -> Slist (a, b) -> Maybe b
lookup :: a -> Slist (a, b) -> Maybe b
lookup a :: a
a = a -> [(a, b)] -> Maybe b
forall a b. Eq a => a -> [(a, b)] -> Maybe b
L.lookup a
a ([(a, b)] -> Maybe b)
-> (Slist (a, b) -> [(a, b)]) -> Slist (a, b) -> Maybe b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Slist (a, b) -> [(a, b)]
forall a. Slist a -> [a]
sList
{-# INLINE lookup #-}
filter :: forall a . (a -> Bool) -> Slist a -> Slist a
filter :: (a -> Bool) -> Slist a -> Slist a
filter p :: a -> Bool
p (Slist l :: [a]
l Infinity) = [a] -> Slist a
forall a. [a] -> Slist a
infiniteSlist ([a] -> Slist a) -> [a] -> Slist a
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
L.filter a -> Bool
p [a]
l
filter p :: a -> Bool
p Slist{..} = let (newS :: Int
newS, newL :: [a]
newL) = Int -> [a] -> (Int, [a])
go 0 [a]
sList in
[a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
newL (Int -> Size
Size Int
newS)
where
go :: Int -> [a] -> (Int, [a])
go :: Int -> [a] -> (Int, [a])
go !Int
n [] = (Int
n, [])
go n :: Int
n (x :: a
x:xs :: [a]
xs) =
if a -> Bool
p a
x
then ([a] -> [a]) -> (Int, [a]) -> (Int, [a])
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]
:) ((Int, [a]) -> (Int, [a])) -> (Int, [a]) -> (Int, [a])
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> (Int, [a])
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1) [a]
xs
else Int -> [a] -> (Int, [a])
go Int
n [a]
xs
{-# INLINE filter #-}
partition :: forall a . (a -> Bool) -> Slist a -> (Slist a, Slist a)
partition :: (a -> Bool) -> Slist a -> (Slist a, Slist a)
partition p :: a -> Bool
p (Slist l :: [a]
l Infinity) = ([a] -> Slist a)
-> ([a] -> Slist a) -> ([a], [a]) -> (Slist a, Slist a)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [a] -> Slist a
forall a. [a] -> Slist a
infiniteSlist [a] -> Slist a
forall a. [a] -> Slist a
infiniteSlist (([a], [a]) -> (Slist a, Slist a))
-> ([a], [a]) -> (Slist a, Slist a)
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> [a] -> ([a], [a])
forall a. (a -> Bool) -> [a] -> ([a], [a])
L.partition a -> Bool
p [a]
l
partition p :: a -> Bool
p Slist{..} = let (s1 :: Int
s1, l1 :: [a]
l1, l2 :: [a]
l2) = Int -> [a] -> (Int, [a], [a])
go 0 [a]
sList in
([a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
l1 (Size -> Slist a) -> Size -> Slist a
forall a b. (a -> b) -> a -> b
$ Int -> Size
Size Int
s1, [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
l2 (Size -> Slist a) -> Size -> Slist a
forall a b. (a -> b) -> a -> b
$ Size
sSize Size -> Size -> Size
forall a. Num a => a -> a -> a
- Int -> Size
Size Int
s1)
where
go :: Int -> [a] -> (Int, [a], [a])
go :: Int -> [a] -> (Int, [a], [a])
go !Int
n [] = (Int
n, [], [])
go n :: Int
n (x :: a
x:xs :: [a]
xs) =
if a -> Bool
p a
x
then ([a] -> [a]) -> (Int, [a], [a]) -> (Int, [a], [a])
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ((Int, [a], [a]) -> (Int, [a], [a]))
-> (Int, [a], [a]) -> (Int, [a], [a])
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> (Int, [a], [a])
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1) [a]
xs
else ([a] -> [a]) -> (Int, [a], [a]) -> (Int, [a], [a])
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]
:) ((Int, [a], [a]) -> (Int, [a], [a]))
-> (Int, [a], [a]) -> (Int, [a], [a])
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> (Int, [a], [a])
go Int
n [a]
xs
{-# INLINE partition #-}
at :: Int -> Slist a -> Maybe a
at :: Int -> Slist a -> Maybe a
at n :: Int
n Slist{..}
| Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< 0 Bool -> Bool -> Bool
|| Int -> Size
Size Int
n Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
>= Size
sSize = Maybe a
forall a. Maybe a
Nothing
| Bool
otherwise = a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> a -> Maybe a
forall a b. (a -> b) -> a -> b
$ [a]
sList [a] -> Int -> a
forall a. [a] -> Int -> a
L.!! Int
n
{-# INLINE at #-}
unsafeAt :: Int -> Slist a -> a
unsafeAt :: Int -> Slist a -> a
unsafeAt n :: Int
n Slist{..} = [a]
sList [a] -> Int -> a
forall a. [a] -> Int -> a
L.!! Int
n
{-# INLINE unsafeAt #-}
elemIndex :: Eq a => a -> Slist a -> Maybe Int
elemIndex :: a -> Slist a -> Maybe Int
elemIndex a :: a
a = a -> [a] -> Maybe Int
forall a. Eq a => a -> [a] -> Maybe Int
L.elemIndex a
a ([a] -> Maybe Int) -> (Slist a -> [a]) -> Slist a -> Maybe Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Slist a -> [a]
forall a. Slist a -> [a]
sList
{-# INLINE elemIndex #-}
elemIndices :: Eq a => a -> Slist a -> Slist Int
elemIndices :: a -> Slist a -> Slist Int
elemIndices a :: a
a = (a -> Bool) -> Slist a -> Slist Int
forall a. (a -> Bool) -> Slist a -> Slist Int
findIndices (a
a a -> a -> Bool
forall a. Eq a => a -> a -> Bool
==)
{-# INLINE elemIndices #-}
findIndex :: (a -> Bool) -> Slist a -> Maybe Int
findIndex :: (a -> Bool) -> Slist a -> Maybe Int
findIndex p :: a -> Bool
p = (a -> Bool) -> [a] -> Maybe Int
forall a. (a -> Bool) -> [a] -> Maybe Int
L.findIndex a -> Bool
p ([a] -> Maybe Int) -> (Slist a -> [a]) -> Slist a -> Maybe Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Slist a -> [a]
forall a. Slist a -> [a]
sList
{-# INLINE findIndex #-}
findIndices :: forall a . (a -> Bool) -> Slist a -> Slist Int
findIndices :: (a -> Bool) -> Slist a -> Slist Int
findIndices p :: a -> Bool
p (Slist l :: [a]
l Infinity) = [Int] -> Slist Int
forall a. [a] -> Slist a
infiniteSlist ([Int] -> Slist Int) -> [Int] -> Slist Int
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> [a] -> [Int]
forall a. (a -> Bool) -> [a] -> [Int]
L.findIndices a -> Bool
p [a]
l
findIndices p :: a -> Bool
p Slist{..} = let (newS :: Int
newS, newL :: [Int]
newL) = Int -> Int -> [a] -> (Int, [Int])
go 0 0 [a]
sList in
[Int] -> Size -> Slist Int
forall a. [a] -> Size -> Slist a
Slist [Int]
newL (Int -> Size
Size Int
newS)
where
go :: Int -> Int -> [a] -> (Int, [Int])
go :: Int -> Int -> [a] -> (Int, [Int])
go !Int
n _ [] = (Int
n, [])
go n :: Int
n !Int
cur (x :: a
x:xs :: [a]
xs) =
if a -> Bool
p a
x
then ([Int] -> [Int]) -> (Int, [Int]) -> (Int, [Int])
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second (Int
curInt -> [Int] -> [Int]
forall a. a -> [a] -> [a]
:) ((Int, [Int]) -> (Int, [Int])) -> (Int, [Int]) -> (Int, [Int])
forall a b. (a -> b) -> a -> b
$ Int -> Int -> [a] -> (Int, [Int])
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1) (Int
cur Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1) [a]
xs
else Int -> Int -> [a] -> (Int, [Int])
go Int
n (Int
cur Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1) [a]
xs
{-# INLINE findIndices #-}
zip :: Slist a -> Slist b -> Slist (a, b)
zip :: Slist a -> Slist b -> Slist (a, b)
zip (Slist l1 :: [a]
l1 s1 :: Size
s1) (Slist l2 :: [b]
l2 s2 :: Size
s2) = Slist :: forall a. [a] -> Size -> Slist a
Slist
{ sList :: [(a, b)]
sList = [a] -> [b] -> [(a, b)]
forall a b. [a] -> [b] -> [(a, b)]
L.zip [a]
l1 [b]
l2
, sSize :: Size
sSize = Size -> Size -> Size
forall a. Ord a => a -> a -> a
min Size
s1 Size
s2
}
{-# INLINE zip #-}
zip3 :: Slist a -> Slist b -> Slist c -> Slist (a, b, c)
zip3 :: Slist a -> Slist b -> Slist c -> Slist (a, b, c)
zip3 (Slist l1 :: [a]
l1 s1 :: Size
s1) (Slist l2 :: [b]
l2 s2 :: Size
s2) (Slist l3 :: [c]
l3 s3 :: Size
s3) = Slist :: forall a. [a] -> Size -> Slist a
Slist
{ sList :: [(a, b, c)]
sList = [a] -> [b] -> [c] -> [(a, b, c)]
forall a b c. [a] -> [b] -> [c] -> [(a, b, c)]
L.zip3 [a]
l1 [b]
l2 [c]
l3
, sSize :: Size
sSize = [Size] -> Size
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum [Size
s1, Size
s2, Size
s3]
}
{-# INLINE zip3 #-}
zipWith :: (a -> b -> c) -> Slist a -> Slist b -> Slist c
zipWith :: (a -> b -> c) -> Slist a -> Slist b -> Slist c
zipWith f :: a -> b -> c
f (Slist l1 :: [a]
l1 s1 :: Size
s1) (Slist l2 :: [b]
l2 s2 :: Size
s2) = Slist :: forall a. [a] -> Size -> Slist a
Slist
{ sList :: [c]
sList = (a -> b -> c) -> [a] -> [b] -> [c]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
L.zipWith a -> b -> c
f [a]
l1 [b]
l2
, sSize :: Size
sSize = Size -> Size -> Size
forall a. Ord a => a -> a -> a
min Size
s1 Size
s2
}
{-# INLINE zipWith #-}
zipWith3 :: (a -> b -> c -> d) -> Slist a -> Slist b -> Slist c -> Slist d
zipWith3 :: (a -> b -> c -> d) -> Slist a -> Slist b -> Slist c -> Slist d
zipWith3 f :: a -> b -> c -> d
f (Slist l1 :: [a]
l1 s1 :: Size
s1) (Slist l2 :: [b]
l2 s2 :: Size
s2) (Slist l3 :: [c]
l3 s3 :: Size
s3) = Slist :: forall a. [a] -> Size -> Slist a
Slist
{ sList :: [d]
sList = (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
forall a b c d. (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
L.zipWith3 a -> b -> c -> d
f [a]
l1 [b]
l2 [c]
l3
, sSize :: Size
sSize = [Size] -> Size
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum [Size
s1, Size
s2, Size
s3]
}
{-# INLINE zipWith3 #-}
unzip :: Slist (a, b) -> (Slist a, Slist b)
unzip :: Slist (a, b) -> (Slist a, Slist b)
unzip Slist{..} = let (as :: [a]
as, bs :: [b]
bs) = [(a, b)] -> ([a], [b])
forall a b. [(a, b)] -> ([a], [b])
L.unzip [(a, b)]
sList in ([a] -> Slist a
forall a. [a] -> Slist a
l [a]
as, [b] -> Slist b
forall a. [a] -> Slist a
l [b]
bs)
where
l :: [x] -> Slist x
l :: [x] -> Slist x
l x :: [x]
x = [x] -> Size -> Slist x
forall a. [a] -> Size -> Slist a
Slist [x]
x Size
sSize
{-# INLINE unzip #-}
unzip3 :: Slist (a, b, c) -> (Slist a, Slist b, Slist c)
unzip3 :: Slist (a, b, c) -> (Slist a, Slist b, Slist c)
unzip3 Slist{..} = let (as :: [a]
as, bs :: [b]
bs, cs :: [c]
cs) = [(a, b, c)] -> ([a], [b], [c])
forall a b c. [(a, b, c)] -> ([a], [b], [c])
L.unzip3 [(a, b, c)]
sList in ([a] -> Slist a
forall a. [a] -> Slist a
l [a]
as, [b] -> Slist b
forall a. [a] -> Slist a
l [b]
bs, [c] -> Slist c
forall a. [a] -> Slist a
l [c]
cs)
where
l :: [x] -> Slist x
l :: [x] -> Slist x
l x :: [x]
x = [x] -> Size -> Slist x
forall a. [a] -> Size -> Slist a
Slist [x]
x Size
sSize
{-# INLINE unzip3 #-}
nub :: Eq a => Slist a -> Slist a
nub :: Slist a -> Slist a
nub = (a -> a -> Bool) -> Slist a -> Slist a
forall a. (a -> a -> Bool) -> Slist a -> Slist a
nubBy a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)
{-# INLINE nub #-}
nubBy :: forall a . (a -> a -> Bool) -> Slist a -> Slist a
nubBy :: (a -> a -> Bool) -> Slist a -> Slist a
nubBy f :: a -> a -> Bool
f Slist{..} = let (s :: Int
s, l :: [a]
l) = Int -> [a] -> [a] -> (Int, [a])
go 0 [] [a]
sList in case Size
sSize of
Infinity -> [a] -> Slist a
forall a. [a] -> Slist a
infiniteSlist [a]
l
_ -> [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
l (Size -> Slist a) -> Size -> Slist a
forall a b. (a -> b) -> a -> b
$ Int -> Size
Size Int
s
where
go :: Int -> [a] -> [a] -> (Int, [a])
go :: Int -> [a] -> [a] -> (Int, [a])
go !Int
n res :: [a]
res [] = (Int
n, [a]
res)
go n :: Int
n res :: [a]
res (x :: a
x:xs :: [a]
xs) =
if (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (a -> a -> Bool
f a
x) [a]
res
then Int -> [a] -> [a] -> (Int, [a])
go Int
n [a]
res [a]
xs
else Int -> [a] -> [a] -> (Int, [a])
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1) ([a]
res [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x]) [a]
xs
{-# INLINE nubBy #-}
delete :: Eq a => a -> Slist a -> Slist a
delete :: a -> Slist a -> Slist a
delete = (a -> a -> Bool) -> a -> Slist a -> Slist a
forall a. (a -> a -> Bool) -> a -> Slist a -> Slist a
deleteBy a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)
{-# INLINE delete #-}
deleteBy :: forall a . (a -> a -> Bool) -> a -> Slist a -> Slist a
deleteBy :: (a -> a -> Bool) -> a -> Slist a -> Slist a
deleteBy f :: a -> a -> Bool
f a :: a
a (Slist l :: [a]
l Infinity) = [a] -> Slist a
forall a. [a] -> Slist a
infiniteSlist ([a] -> Slist a) -> [a] -> Slist a
forall a b. (a -> b) -> a -> b
$ (a -> a -> Bool) -> a -> [a] -> [a]
forall a. (a -> a -> Bool) -> a -> [a] -> [a]
L.deleteBy a -> a -> Bool
f a
a [a]
l
deleteBy f :: a -> a -> Bool
f a :: a
a Slist{..} = let (del :: Size
del, res :: [a]
res) = [a] -> (Size, [a])
go [a]
sList in
[a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
res (Size -> Slist a) -> Size -> Slist a
forall a b. (a -> b) -> a -> b
$ Size
sSize Size -> Size -> Size
forall a. Num a => a -> a -> a
- Size
del
where
go :: [a] -> (Size, [a])
go :: [a] -> (Size, [a])
go [] = (Int -> Size
Size 0, [])
go (x :: a
x:xs :: [a]
xs) = if a -> a -> Bool
f a
a a
x
then (Int -> Size
Size 1, [a]
xs)
else ([a] -> [a]) -> (Size, [a]) -> (Size, [a])
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]
:) ((Size, [a]) -> (Size, [a])) -> (Size, [a]) -> (Size, [a])
forall a b. (a -> b) -> a -> b
$ [a] -> (Size, [a])
go [a]
xs
{-# INLINE deleteBy #-}
deleteFirstsBy :: (a -> a -> Bool) -> Slist a -> Slist a -> Slist a
deleteFirstsBy :: (a -> a -> Bool) -> Slist a -> Slist a -> Slist a
deleteFirstsBy f :: a -> a -> Bool
f = (a -> Slist a -> Slist a) -> Slist a -> Slist a -> Slist a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ((a -> a -> Bool) -> a -> Slist a -> Slist a
forall a. (a -> a -> Bool) -> a -> Slist a -> Slist a
deleteBy a -> a -> Bool
f)
{-# INLINE deleteFirstsBy #-}
diff :: Eq a => Slist a -> Slist a -> Slist a
diff :: Slist a -> Slist a -> Slist a
diff = (a -> Slist a -> Slist a) -> Slist a -> Slist a -> Slist a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> Slist a -> Slist a
forall a. Eq a => a -> Slist a -> Slist a
delete
{-# INLINE diff #-}
union :: Eq a => Slist a -> Slist a -> Slist a
union :: Slist a -> Slist a -> Slist a
union = (a -> a -> Bool) -> Slist a -> Slist a -> Slist a
forall a. (a -> a -> Bool) -> Slist a -> Slist a -> Slist a
unionBy a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)
{-# INLINE union #-}
unionBy :: (a -> a -> Bool) -> Slist a -> Slist a -> Slist a
unionBy :: (a -> a -> Bool) -> Slist a -> Slist a -> Slist a
unionBy f :: a -> a -> Bool
f xs :: Slist a
xs ys :: Slist a
ys = Slist a
xs Slist a -> Slist a -> Slist a
forall a. Semigroup a => a -> a -> a
<> (a -> a -> Bool) -> Slist a -> Slist a -> Slist a
forall a. (a -> a -> Bool) -> Slist a -> Slist a -> Slist a
deleteFirstsBy a -> a -> Bool
f ((a -> a -> Bool) -> Slist a -> Slist a
forall a. (a -> a -> Bool) -> Slist a -> Slist a
nubBy a -> a -> Bool
f Slist a
ys) Slist a
xs
{-# INLINE unionBy #-}
intersect :: Eq a => Slist a -> Slist a -> Slist a
intersect :: Slist a -> Slist a -> Slist a
intersect = (a -> a -> Bool) -> Slist a -> Slist a -> Slist a
forall a. (a -> a -> Bool) -> Slist a -> Slist a -> Slist a
intersectBy a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)
{-# INLINE intersect #-}
intersectBy :: forall a . (a -> a -> Bool) -> Slist a -> Slist a -> Slist a
intersectBy :: (a -> a -> Bool) -> Slist a -> Slist a -> Slist a
intersectBy _ (Slist _ (Size 0)) _ = Slist a
forall a. Monoid a => a
mempty
intersectBy _ _ (Slist _ (Size 0)) = Slist a
forall a. Monoid a => a
mempty
intersectBy f :: a -> a -> Bool
f (Slist l1 :: [a]
l1 Infinity) (Slist l2 :: [a]
l2 _) = [a] -> Slist a
forall a. [a] -> Slist a
infiniteSlist ([a] -> Slist a) -> [a] -> Slist a
forall a b. (a -> b) -> a -> b
$ (a -> a -> Bool) -> [a] -> [a] -> [a]
forall a. (a -> a -> Bool) -> [a] -> [a] -> [a]
L.intersectBy a -> a -> Bool
f [a]
l1 [a]
l2
intersectBy f :: a -> a -> Bool
f (Slist l1 :: [a]
l1 _) (Slist l2 :: [a]
l2 _) =
let (s :: Int
s, l :: [a]
l) = Int -> [a] -> (Int, [a])
go 0 [a]
l1 in [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
l (Size -> Slist a) -> Size -> Slist a
forall a b. (a -> b) -> a -> b
$ Int -> Size
Size Int
s
where
go :: Int -> [a] -> (Int, [a])
go :: Int -> [a] -> (Int, [a])
go n :: Int
n [] = (Int
n, [])
go n :: Int
n (x :: a
x:xs :: [a]
xs) =
if (a -> Bool) -> [a] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (a -> a -> Bool
f a
x) [a]
l2
then ([a] -> [a]) -> (Int, [a]) -> (Int, [a])
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]
:) ((Int, [a]) -> (Int, [a])) -> (Int, [a]) -> (Int, [a])
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> (Int, [a])
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1) [a]
xs
else Int -> [a] -> (Int, [a])
go Int
n [a]
xs
{-# INLINE intersectBy #-}
sort :: Ord a => Slist a -> Slist a
sort :: Slist a -> Slist a
sort = (a -> a -> Ordering) -> Slist a -> Slist a
forall a. (a -> a -> Ordering) -> Slist a -> Slist a
sortBy a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
{-# INLINE sort #-}
sortBy :: (a -> a -> Ordering) -> Slist a -> Slist a
sortBy :: (a -> a -> Ordering) -> Slist a -> Slist a
sortBy f :: a -> a -> Ordering
f Slist{..} = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist ((a -> a -> Ordering) -> [a] -> [a]
forall a. (a -> a -> Ordering) -> [a] -> [a]
L.sortBy a -> a -> Ordering
f [a]
sList) Size
sSize
{-# INLINE sortBy #-}
sortOn :: Ord b => (a -> b) -> Slist a -> Slist a
sortOn :: (a -> b) -> Slist a -> Slist a
sortOn f :: a -> b
f Slist{..} = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist ((a -> b) -> [a] -> [a]
forall b a. Ord b => (a -> b) -> [a] -> [a]
L.sortOn a -> b
f [a]
sList) Size
sSize
{-# INLINE sortOn #-}
insert :: Ord a => a -> Slist a -> Slist a
insert :: a -> Slist a -> Slist a
insert = (a -> a -> Ordering) -> a -> Slist a -> Slist a
forall a. (a -> a -> Ordering) -> a -> Slist a -> Slist a
insertBy a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
{-# INLINE insert #-}
insertBy :: (a -> a -> Ordering) -> a -> Slist a -> Slist a
insertBy :: (a -> a -> Ordering) -> a -> Slist a -> Slist a
insertBy f :: a -> a -> Ordering
f a :: a
a Slist{..} = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist ((a -> a -> Ordering) -> a -> [a] -> [a]
forall a. (a -> a -> Ordering) -> a -> [a] -> [a]
L.insertBy a -> a -> Ordering
f a
a [a]
sList) (Size
sSize Size -> Size -> Size
forall a. Num a => a -> a -> a
+ 1)
{-# INLINE insertBy #-}
genericLength :: Num i => Slist a -> i
genericLength :: Slist a -> i
genericLength = Int -> i
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> i) -> (Slist a -> Int) -> Slist a -> i
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Slist a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length
{-# INLINE genericLength #-}
genericTake :: Integral i => i -> Slist a -> Slist a
genericTake :: i -> Slist a -> Slist a
genericTake (i -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral -> Int
i) sl :: Slist a
sl@Slist{..}
| Int -> Size
Size Int
i Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
>= Size
sSize = Slist a
sl
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= 0 = Slist a
forall a. Monoid a => a
mempty
| Bool
otherwise = Slist :: forall a. [a] -> Size -> Slist a
Slist
{ sList :: [a]
sList = Int -> [a] -> [a]
forall i a. Integral i => i -> [a] -> [a]
L.genericTake Int
i [a]
sList
, sSize :: Size
sSize = Size -> Size -> Size
forall a. Ord a => a -> a -> a
min Size
sSize (Int -> Size
Size Int
i)
}
{-# INLINE genericTake #-}
genericDrop :: Integral i => i -> Slist a -> Slist a
genericDrop :: i -> Slist a -> Slist a
genericDrop (i -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral -> Int
i) sl :: Slist a
sl@Slist{..}
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= 0 = Slist a
sl
| Int -> Size
Size Int
i Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
>= Size
sSize = Slist a
forall a. Monoid a => a
mempty
| Bool
otherwise = Slist :: forall a. [a] -> Size -> Slist a
Slist
{ sList :: [a]
sList = Int -> [a] -> [a]
forall i a. Integral i => i -> [a] -> [a]
L.genericDrop Int
i [a]
sList
, sSize :: Size
sSize = Size
sSize Size -> Size -> Size
forall a. Num a => a -> a -> a
- Int -> Size
Size Int
i
}
{-# INLINE genericDrop #-}
genericSplitAt :: Integral i => i -> Slist a -> (Slist a, Slist a)
genericSplitAt :: i -> Slist a -> (Slist a, Slist a)
genericSplitAt (i -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral -> Int
i) sl :: Slist a
sl@Slist{..}
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= 0 = (Slist a
forall a. Monoid a => a
mempty, Slist a
sl)
| Int -> Size
Size Int
i Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
>= Size
sSize = (Slist a
sl, Slist a
forall a. Monoid a => a
mempty)
| Bool
otherwise =
let (l1 :: [a]
l1, l2 :: [a]
l2) = Int -> [a] -> ([a], [a])
forall i a. Integral i => i -> [a] -> ([a], [a])
L.genericSplitAt Int
i [a]
sList
s2 :: Size
s2 = Size
sSize Size -> Size -> Size
forall a. Num a => a -> a -> a
- Int -> Size
Size Int
i
in ([a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
l1 (Size -> Slist a) -> Size -> Slist a
forall a b. (a -> b) -> a -> b
$ Int -> Size
Size Int
i, [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist [a]
l2 Size
s2)
{-# INLINE genericSplitAt #-}
genericAt :: Integral i => i -> Slist a -> Maybe a
genericAt :: i -> Slist a -> Maybe a
genericAt = Int -> Slist a -> Maybe a
forall a. Int -> Slist a -> Maybe a
at (Int -> Slist a -> Maybe a)
-> (i -> Int) -> i -> Slist a -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. i -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral
{-# INLINE genericAt #-}
genericUnsafeAt :: Integral i => i -> Slist a -> a
genericUnsafeAt :: i -> Slist a -> a
genericUnsafeAt i :: i
i _ | i
i i -> i -> Bool
forall a. Ord a => a -> a -> Bool
< 0 = String -> a
forall a. String -> a
errorWithoutStackTrace "Slist.genericUnsafeAt: negative argument"
genericUnsafeAt i :: i
i (Slist l :: [a]
l Infinity) = [a] -> i -> a
forall i a. Integral i => [a] -> i -> a
L.genericIndex [a]
l i
i
genericUnsafeAt i :: i
i (Slist l :: [a]
l (Size n :: Int
n))
| i
i i -> i -> Bool
forall a. Ord a => a -> a -> Bool
>= Int -> i
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n = String -> a
forall a. String -> a
errorWithoutStackTrace "Slist.genericUnsafeAt: index too large"
| Bool
otherwise = [a] -> i -> a
forall i a. Integral i => [a] -> i -> a
L.genericIndex [a]
l i
i
{-# INLINE genericUnsafeAt #-}
genericReplicate :: Integral i => i -> a -> Slist a
genericReplicate :: i -> a -> Slist a
genericReplicate n :: i
n x :: a
x
| i
n i -> i -> Bool
forall a. Ord a => a -> a -> Bool
<= 0 = Slist a
forall a. Monoid a => a
mempty
| Bool
otherwise = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist (i -> a -> [a]
forall i a. Integral i => i -> a -> [a]
L.genericReplicate i
n a
x) (Size -> Slist a) -> Size -> Slist a
forall a b. (a -> b) -> a -> b
$ Int -> Size
Size (i -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral i
n)
{-# INLINE genericReplicate #-}