{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE CPP          #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE ViewPatterns #-}

{- HLINT ignore "Use mconcat" -}

{- |
Copyright:  (c) 2019-2020 Veronika Romashkina
License:    MPL-2.0
Maintainer: Veronika Romashkina <vrom911@gmail.com>

This module introduces sized list data type — 'Slist'. The data type
has the following shape:

@
__data__ 'Slist' a = Slist
    { sList :: [a]
    , sSize :: 'Size'
    }
@

As you can see along with the familiar list, it contains 'Size' field that
represents the size of the structure. Slists can be finite or infinite, and this
is expressed with 'Size'.

@
__data__ 'Size'
    = Size 'Int'
    | Infinity
@

This representation of the list gives some additional advantages. Getting the
length of the list is the "free" operation (runs in \( O(1) \)). This property
helps to improve the performance for a bunch of functions like 'take', 'drop',
'at', etc. But also it doesn't actually add any overhead on the existing
functions.

Also, this allows to write a number of safe functions like 'safeReverse',
'safeHead', 'safeLast', 'safeIsSuffixOf', etc.

== Comparison

Check out the comparison table between lists and slists performance.

+-------------------+--------------------+--------------------+-----------------------+-----------------------+
| Function          | list (finite)      | list (infinite)    | Slist (finite)        | Slist (infinite)      |
+===================+====================+====================+=======================+=======================+
| 'length'          | \( O(n) \)         | \</hangs/\>        |  \( O(1) \)           |   \( O(1) \)          |
+-------------------+--------------------+--------------------+-----------------------+-----------------------+
| 'safeLast'        | \( O(n) \)         | \</hangs/\>        |  \( O(n) \)           |   \( O(1) \)          |
+-------------------+--------------------+--------------------+-----------------------+-----------------------+
| 'init'            | \( O(n) \)         | \</hangs/\>        |  \( O(n) \)           |   \( O(1) \)          |
+-------------------+--------------------+--------------------+-----------------------+-----------------------+
| 'take'            | \( O(min\ i\ n) \) | \( O(i) \)         | @0 < i < n@: \(O(i)\) |              \(O(i)\) |
|                   |                    |                    | otherwise:   \(O(1)\) |                       |
+-------------------+--------------------+--------------------+-----------------------+-----------------------+
| 'at'              | \( O(min\ i\ n) \) | \( O(i) \)         | @0 < i < n@: \(O(i)\) |   \( O(i) \)          |
|                   | run-time exception | run-time exception | otherwise:   \(O(1)\) |                       |
+-------------------+--------------------+--------------------+-----------------------+-----------------------+
| 'safeStripPrefix' | \( O(m) \)         |  \( O(m) \)        |  \( O(m) \)           |   \( O(m) \)          |
|                   |                    | can hang           |                       |                       |
+-------------------+--------------------+--------------------+-----------------------+-----------------------+

== Potential usage cases

* When you ask the length of the list too frequently.
* When you need to convert to data structures that require to know the list
  size in advance for allocating an array of the elements. /Example:/ [Vector data
  structure](https://hackage.haskell.org/package/vector).
* When you need to serialised lists.
* When you need to control the behaviour depending on the finiteness of the list.
* When you need a more efficient or safe implementation of some functions.

-}

module Slist
       ( -- * Types
         Slist
       , Size
         -- ** Smart constructors
       , slist
       , infiniteSlist
       , one
       , iterate
#if ( __GLASGOW_HASKELL__ > 802 )
       , iterate'
#endif
       , repeat
       , replicate
       , cycle
       , fromRange
         -- * Basic functions
       , len
       , size
       , isEmpty
       , head
       , safeHead
       , last
       , safeLast
       , init
       , tail
       , uncons

         -- * Transformations
       , map
       , reverse
       , safeReverse
       , intersperse
       , intercalate
       , transpose
       , subsequences
       , permutations

         -- *  Reducing slists (folds)
       , concat
       , concatMap

         -- * Building slists
         -- ** Scans
       , scanl
       , scanl'
       , scanl1
       , scanr
       , scanr1

         -- ** Unfolding
       , unfoldr

         -- * Subslists
         -- ** Extracting
       , take
       , drop
       , splitAt
       , takeWhile
       , dropWhile
       , span
       , break
       , stripPrefix
       , safeStripPrefix
       , group
       , groupBy
       , inits
       , tails
         -- ** Predicates
       , isPrefixOf
       , safeIsPrefixOf
       , isSuffixOf
       , safeIsSuffixOf
       , isInfixOf
       , safeIsInfixOf
       , isSubsequenceOf
       , safeIsSubsequenceOf

         -- * Searching
         -- ** Searching by equality
       , lookup
         -- ** Searching with a predicate
       , filter
       , partition

         -- * Indexing
       , at
       , unsafeAt
       , elemIndex
       , elemIndices
       , findIndex
       , findIndices

         -- * Zipping and unzipping
       , zip
       , zip3
       , zipWith
       , zipWith3
       , unzip
       , unzip3

         -- * Sets
         -- $sets
       , nub
       , nubBy
       , delete
       , deleteBy
       , deleteFirstsBy
       , diff
       , union
       , unionBy
       , intersect
       , intersectBy

         -- * Ordered slists
       , sort
       , sortBy
       , sortOn
       , insert
       , insertBy

        -- * Generic functions
       , 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 type that represents sized list.
Size can be both finite or infinite, it is established using
'Size' data type.
-}
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)

{- | Equality of sized lists is checked more efficiently
due to the fact that the check on the list sizes can be
done first for the constant time.
-}
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 (==) #-}

-- | Lexicographical comparison of the lists.
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 #-}

{- | List appending. Use '<>' for 'Slist' concatenation instead of
'L.++' operator that is common in ordinary list concatenations.
-}
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
        -- foldr :: (a -> ([a], Size) -> ([a], Size)) -> ([a], Size) -> [Slist a] -> ([a], Size)
        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 (>>=) #-}

{- | Efficient implementation of 'sum' and 'product' functions.
'length' returns 'Int's 'maxBound' on infinite lists.
-}
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 #-}

    -- | Is the element in the structure?
    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 #-}

{- | @O(n)@. Constructs 'Slist' from the given list.

>>> slist [1..5]
Slist {sList = [1,2,3,4,5], sSize = Size 5}

/Note:/ works with finite lists. Use 'infiniteSlist'
to construct infinite lists.
-}
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 #-}

{- | @O(1)@. Constructs 'Slist' from the given list.

@
>> infiniteSlist [1..]
Slist {sList = [1..], sSize = Infinity}
@

/Note:/ works with infinite lists. Use 'slist'
to construct finite lists.
-}
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 #-}

{- | @O(1)@. Creates 'Slist' with a single element.
The size of such 'Slist' is always equals to @Size 1@.

>>> one "and only"
Slist {sList = ["and only"], sSize = Size 1}

-}
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 #-}

{- | Returns an infinite slist of repeated applications
of the given function to the start element:

> iterate f x == [x, f x, f (f x), ...]

@
>> __iterate (+1) 0__
Slist {sList = [0..], sSize = 'Infinity'}
@

>>> take 5 $ iterate ('a':) "a"
Slist {sList = ["a","aa","aaa","aaaa","aaaaa"], sSize = Size 5}

/Note:/ 'L.iterate' is lazy, potentially leading to thunk build-up if
the consumer doesn't force each iterate.
See 'iterate'' for a strict variant of this function.
-}
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 )
{- | Returns an infinite slist of repeated applications
of the given function to the start element:

> iterate' f x == [x, f x, f (f x), ...]

@
>> __iterate' (+1) 0__
Slist {sList = [0..], sSize = 'Infinity'}
@

>>> take 5 $ iterate' ('a':) "a"
Slist {sList = ["a","aa","aaa","aaaa","aaaaa"], sSize = Size 5}

'iterate'' is the strict version of 'iterate'.

It ensures that the result of each application of force to weak head normal
form before proceeding.
-}
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

{- | @O(1)@. Creates an infinite slist with the given element
at each position.

@
>> __repeat 42__
Slist {sList = [42, 42 ..], sSize = 'Infinity'}
@

>>> take 6 $ repeat 'm'
Slist {sList = "mmmmmm", sSize = Size 6}

-}
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 #-}

{- | @O(n)@. Creates a finite slist with the given value at each position.

>>> replicate 3 'o'
Slist {sList = "ooo", sSize = Size 3}
>>> replicate (-11) "hmm"
Slist {sList = [], sSize = Size 0}
-}
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 #-}

{- | Ties a finite list into a circular one, or equivalently,
the infinite repetition of the original list.
It is the identity on infinite lists.

>>> take 23 $ cycle (slist "pam ")
Slist {sList = "pam pam pam pam pam pam", sSize = Size 23}

@
>> __cycle $ 'infiniteSlist' [1..]__
Slist {sList = [1..], sSize = 'Infinity'}
@
-}
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 #-}

{- | @O(1)@. An slist equivalent of 'P.enumFromTo' function or @[from..to]@ notation:
creates an 'Slist' of sequentially ordered values starting at @from@ and ending at @to@ inclusively.

>>> fromRange 0 5
Slist {sList = [0,1,2,3,4,5], sSize = Size 6}
>>> fromRange 5 0
Slist {sList = [], sSize = Size 0}
>>> fromRange 0 0
Slist {sList = [0], sSize = Size 1}
>>> fromRange 'a' 'd'
Slist {sList = "abcd", sSize = Size 4}
-}
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 #-}

----------------------------------------------------------------------------
-- Basic functions
----------------------------------------------------------------------------

{- | @O(1)@. Returns the length of a structure as an 'Int'.
On infinite lists returns the 'Int's 'maxBound'.

>>> len $ one 42
1
>>> len $ slist [1..3]
3
>>> len $ infiniteSlist [1..]
9223372036854775807
-}
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 #-}

{- | @O(1)@. Returns the 'Size' of the slist.

>>> size $ slist "Hello World!"
Size 12
>>> size $ infiniteSlist [1..]
Infinity
-}
size :: Slist a -> Size
size :: Slist a -> Size
size = Slist a -> Size
forall a. Slist a -> Size
sSize
{-# INLINE size #-}

{- | @O(1)@. Checks if 'Slist' is empty

>>> isEmpty mempty
True
>>> isEmpty $ slist []
True
>>> isEmpty $ slist "Not Empty"
False
-}
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 #-}

{- | @O(1)@. Extracts the first element of a slist.
Uses not total 'L.head' function, so use wisely.

It is recommended to use 'safeHead' instead.

>>> head $ slist "qwerty"
'q'
>>> head $ infiniteSlist [1..]
1
>>> head mempty
*** Exception: Prelude.head: empty list

-}
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 #-}

{- | @O(1)@. Extracts the first element of a slist if possible.

>>> safeHead $ slist "qwerty"
Just 'q'
>>> safeHead $ infiniteSlist [1..]
Just 1
>>> safeHead mempty
Nothing
-}
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 #-}

{- | @O(n)@. Extracts the last element of a list.
Uses not total 'L.last' function, so use wisely.

It is recommended to use 'safeLast' instead

>>> last $ slist "qwerty"
'y'
>>> last mempty
*** Exception: Prelude.last: empty list

@
>> last $ infiniteSlist [1..]
\</hangs/\>
@
-}
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 #-}

{- | @O(n)@. Extracts the last element of a list if possible.

>>> safeLast $ slist "qwerty"
Just 'y'
>>> safeLast mempty
Nothing
>>> safeLast $ infiniteSlist [1..]
Nothing
-}
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 #-}

{- | @O(1)@. Returns a slist with all the elements after
the head of a given slist.

>>> tail mempty
Slist {sList = [], sSize = Size 0}
>>> tail $ slist "Hello"
Slist {sList = "ello", sSize = Size 4}

@
>> __tail $ 'infiniteSlist' [0..]__
Slist {sList = [1..], sSize = 'Infinity'}
@
-}
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 #-}

{- | @O(n)@. Return all the elements of a list except the last one.

>>> init mempty
Slist {sList = [], sSize = Size 0}
>>> init $ slist "Hello"
Slist {sList = "Hell", sSize = Size 4}

@
>> __init $ 'infiniteSlist' [0..]__
Slist {sList = [0..], sSize = 'Infinity'}
@
-}
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 #-}

{- | @O(1)@. Decomposes a slist into its head and tail.
If the slist is empty, returns 'Nothing'.

>>> uncons mempty
Nothing
>>> uncons $ one 'a'
Just ('a',Slist {sList = "", sSize = Size 0})

@
>> __uncons $ 'infiniteSlist' [0..]__
Just (0, Slist {sList = [1..], sSize = 'Infinity'})
@
-}
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 #-}

----------------------------------------------------------------------------
-- Transformations
----------------------------------------------------------------------------

{- | @O(n)@. Applies the given function to each element of the slist.

> map f (slist [x1, x2, ..., xn])     == slist [f x1, f x2, ..., f xn]
> map f (infiniteSlist [x1, x2, ...]) == infiniteSlist [f x1, f x2, ...]

-}
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 #-}

{- | @O(n)@. Returns the elements of the slist in reverse order.

>>> reverse $ slist "Hello"
Slist {sList = "olleH", sSize = Size 5}
>>> reverse $ slist "wow"
Slist {sList = "wow", sSize = Size 3}

/Note:/ 'reverse' slist can not be calculated on infinite slists.

@
>> __reverse $ 'infiniteSlist' [1..]__
\</hangs/\>
@

Use 'safeReverse' to not hang on infinite slists.
-}
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 #-}

{- | @O(n)@. Returns the elements of the slist in reverse order.
On infinite slists returns the initial slist.

>>> safeReverse $ slist "Hello"
Slist {sList = "olleH", sSize = Size 5}

@
>> __reverse $ 'infiniteSlist' [1..]__
Slist {sList = [1..], sSize = 'Infinity'}
@
-}
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 #-}

{- | @O(n)@. Takes an element and a list and intersperses
that element between the elements of the list.

>>> intersperse ',' $ slist "abcd"
Slist {sList = "a,b,c,d", sSize = Size 7}
>>> intersperse '!' mempty
Slist {sList = "", sSize = Size 0}

@
>> __intersperse 0 $ 'infiniteSlist' [1,1..]__
Slist {sList = [1,0,1,0..], sSize = 'Infinity'}
@
-}
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 #-}

{- | @O(n)@. Inserts the given slist in between the slists and concatenates the result.

> intercalate x xs = concat (intersperse x xs)

>>> intercalate (slist ", ") $ slist [slist "Lorem", slist "ipsum", slist "dolor"]
Slist {sList = "Lorem, ipsum, dolor", sSize = Size 19}

-}
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 #-}

{- | @O(n * m)@. Transposes the rows and columns of the slist.

>>> transpose $ slist [slist [1,2]]
Slist {sList = [Slist {sList = [1], sSize = Size 1},Slist {sList = [2], sSize = Size 1}], sSize = Size 2}

@
>> __transpose $ slist [slist [1,2,3], slist [4,5,6]]__
Slist { sList =
          [ Slist {sList = [1,4], sSize = Size 2}
          , Slist {sList = [2,5], sSize = Size 2}
          , Slist {sList = [3,6], sSize = Size 2}
          ]
      , sSize = Size 3
      }
@

If some of the rows are shorter than the following rows, their elements are skipped:

>>> transpose $ slist [slist [10,11], slist [20], mempty]
Slist {sList = [Slist {sList = [10,20], sSize = Size 2},Slist {sList = [11], sSize = Size 1}], sSize = Size 2}

If some of the rows is an infinite slist, then the resulting slist is going to be infinite.
-}
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 #-}

{- | @O(2 ^ n)@. Returns the list of all subsequences of the argument.

>>> subsequences mempty
Slist {sList = [Slist {sList = [], sSize = Size 0}], sSize = Size 1}
>>> subsequences $ slist "ab"
Slist {sList = [Slist {sList = "", sSize = Size 0},Slist {sList = "a", sSize = Size 1},Slist {sList = "b", sSize = Size 1},Slist {sList = "ab", sSize = Size 2}], sSize = Size 4}
>>> take 4 $ subsequences $ infiniteSlist [1..]
Slist {sList = [Slist {sList = [], sSize = Size 0},Slist {sList = [1], sSize = Size 1},Slist {sList = [2], sSize = Size 1},Slist {sList = [1,2], sSize = Size 2}], sSize = Size 4}

-}
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 #-}

{- | @O(n!)@. Returns the list of all permutations of the argument.

>>> permutations mempty
Slist {sList = [Slist {sList = [], sSize = Size 0}], sSize = Size 1}
>>> permutations $ slist "abc"
Slist {sList = [Slist {sList = "abc", sSize = Size 3},Slist {sList = "bac", sSize = Size 3},Slist {sList = "cba", sSize = Size 3},Slist {sList = "bca", sSize = Size 3},Slist {sList = "cab", sSize = Size 3},Slist {sList = "acb", sSize = Size 3}], sSize = Size 6}

-}
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 #-}

----------------------------------------------------------------------------
-- Reducing slists (folds)
----------------------------------------------------------------------------

{- | \( O(\sum n_i) \) The concatenation of all the elements of a container of slists.

>>> concat [slist [1,2], slist [3..5], slist [6..10]]
Slist {sList = [1,2,3,4,5,6,7,8,9,10], sSize = Size 10}

@
>> __ concat $ slist [slist [1,2], 'infiniteSlist' [3..]]__
Slist {sList = [1..], sSize = 'Infinity'}
@
-}
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 #-}

{- | Maps a function over all the elements of a container
and concatenates the resulting slists.

>>> concatMap one "abc"
Slist {sList = "abc", sSize = Size 3}
-}
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 #-}

----------------------------------------------------------------------------
-- Building lists
----------------------------------------------------------------------------

{- | @O(n)@. Similar to 'foldl', but returns a slist of successive
reduced values from the left:

> scanl f z $ slist [x1, x2, ...] == slist [z, z `f` x1, (z `f` x1) `f` x2, ...]

Note that

> last (scanl f z xs) == foldl f z xs.

This peculiar arrangement is necessary to prevent scanl being rewritten in
its own right-hand side.

>>> scanl (+) 0 $ slist [1..10]
Slist {sList = [0,1,3,6,10,15,21,28,36,45,55], sSize = Size 11}

-}
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 #-}

-- | @O(n)@. A strictly accumulating version of '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' #-}

{- | @O(n)@. 'scanl1' is a variant of 'scanl' that has no starting value argument:

> scanl1 f $ slist [x1, x2, ...] == slist [x1, x1 `f` x2, ...]
-}
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 #-}

{- | @O(n)@. The right-to-left dual of 'scanl'.

Note that

> head (scanr f z xs) == foldr f z xs.

>>> scanr (+) 0 $ slist [1..10]
Slist {sList = [55,54,52,49,45,40,34,27,19,10,0], sSize = Size 11}

-}
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 #-}

-- | A variant of 'scanr' that has no starting value argument.
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 #-}

{- | @O(n)@. A \`dual\' to 'foldr': while 'foldr'
reduces a list to a summary value, 'unfoldr' builds a list from
a seed value.  The function takes the element and returns 'Nothing'
if it is done producing the list or returns 'Just' @(a,b)@, in which
case, @a@ is a prepended to the list and @b@ is used as the next
element in a recursive call.

In some cases, 'unfoldr' can undo a 'foldr' operation:

> unfoldr f' (foldr f z xs) == xs

if the following holds:

> f' (f x y) = Just (x,y)
> f' z       = Nothing

A simple use of unfoldr:

>>> unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
Slist {sList = [10,9,8,7,6,5,4,3,2,1], sSize = Size 10}
-}
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 #-}

----------------------------------------------------------------------------
-- Sublists
----------------------------------------------------------------------------

{- | @O(i) | i < n@ and @O(1) | otherwise@.

Returns the prefix of the slist of the given length.
If the given @i@ is non-positive then the empty structure is returned.
If @i@ is exceeds the length of the structure the initial slist is returned.

>>> take 5 $ slist "Hello world!"
Slist {sList = "Hello", sSize = Size 5}
>>> take 20 $ slist "small"
Slist {sList = "small", sSize = Size 5}
>>> take 0 $ slist "none"
Slist {sList = "", sSize = Size 0}
>>> take (-11) $ slist "hmm"
Slist {sList = "", sSize = Size 0}
>>> take 4 $ infiniteSlist [1..]
Slist {sList = [1,2,3,4], sSize = Size 4}
-}
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 #-}

{- | @O(i) | i < n@ and @O(1) | otherwise@.

Returns the suffix of the slist after the first @i@ elements.
If @i@ exceeds the length of the slist then the empty structure is returned.
If @i@ is non-positive the initial structure is returned.

>>> drop 6 $ slist "Hello World"
Slist {sList = "World", sSize = Size 5}
>>> drop 42 $ slist "oops!"
Slist {sList = "", sSize = Size 0}
>>> drop 0 $ slist "Hello World!"
Slist {sList = "Hello World!", sSize = Size 12}
>>> drop (-4) $ one 42
Slist {sList = [42], sSize = Size 1}

@
>> __drop 5 $ 'infiniteSlist' [1..]__
Slist {sList = [6..], sSize = 'Infinity'}
@

-}
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 #-}

{- | @O(i) | i < n@ and @O(1) | otherwise@.

Returns a tuple where the first element is the prefix
of the given length and the second element is the remainder
of the slist.

>>> splitAt 5 $ slist "Hello World!"
(Slist {sList = "Hello", sSize = Size 5},Slist {sList = " World!", sSize = Size 7})
>>> splitAt 0 $ slist "abc"
(Slist {sList = "", sSize = Size 0},Slist {sList = "abc", sSize = Size 3})
>>> splitAt 4 $ slist "abc"
(Slist {sList = "abc", sSize = Size 3},Slist {sList = "", sSize = Size 0})
>>>splitAt (-42) $ slist "??"
(Slist {sList = "", sSize = Size 0},Slist {sList = "??", sSize = Size 2})

@
>> __splitAt 2 $ 'infiniteSlist' [1..]__
(Slist {sList = [1,2], sSize = 'Size' 2}, Slist {sList = [3..], sSize = 'Infinity'})
@
-}
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 #-}

{- | @O(n)@. Returns the longest prefix (possibly empty)
of elements that satisfy the given predicate.

>>> takeWhile (<3) $ slist [1..10]
Slist {sList = [1,2], sSize = Size 2}
>>> takeWhile (<3) $ infiniteSlist [1..]
Slist {sList = [1,2], sSize = Size 2}
>>> takeWhile (<=10) $ slist [1..10]
Slist {sList = [1,2,3,4,5,6,7,8,9,10], sSize = Size 10}
>>> takeWhile (<0) $ slist [1..10]
Slist {sList = [], sSize = Size 0}

-}
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 #-}

{- | @O(n)@. Returns the suffix (possibly empty) of the remaining
elements after dropping elements that satisfy the given predicate.

>>> dropWhile (<3) $ slist [1..10]
Slist {sList = [3,4,5,6,7,8,9,10], sSize = Size 8}
>>> dropWhile (<=10) $ slist [1..10]
Slist {sList = [], sSize = Size 0}
>>> dropWhile (<0) $ slist [1..10]
Slist {sList = [1,2,3,4,5,6,7,8,9,10], sSize = Size 10}
>>> take 5 $ dropWhile (<3) $ infiniteSlist [1..]
Slist {sList = [3,4,5,6,7], sSize = Size 5}

@
>> __dropWhile (< 5) $ 'infiniteSlist' [1..]__
Slist {sList = [5,6..], sSize = 'Infinity'}
@
-}
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 #-}

{- | @O(n)@. Returns a tuple where first element is longest prefix (possibly empty)
of the slist of elements that satisfy the given predicate
and second element is the remainder of the list.

>>> span (<3) $ slist [1,2,3,4,1,2,3,4]
(Slist {sList = [1,2], sSize = Size 2},Slist {sList = [3,4,1,2,3,4], sSize = Size 6})
>>> span (<=10) $ slist [1..3]
(Slist {sList = [1,2,3], sSize = Size 3},Slist {sList = [], sSize = Size 0})
>>> span (<0) $ slist [1..3]
(Slist {sList = [], sSize = Size 0},Slist {sList = [1,2,3], sSize = Size 3})

@
>> __span (<3) $ 'infiniteSlist' [1..]__
(Slist {sList = [1,2], sSize = Size 2}, Slist {sList = [3..], sSize = 'Infinity'})
@
-}
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 #-}

{- | @O(n)@.  Returns a tuple where first element is longest prefix (possibly empty)
of the slist of elements that /do not/ satisfy the given predicate
and second element is the remainder of the list.

@
> break p = 'span' ('not' . p)
@
-}
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 #-}

{- | @O(m)@. Drops the given prefix from a list.
It returns 'Nothing' if the slist did not start with the given prefix,
or 'Just' the slist after the prefix, if it does.

>>> stripPrefix (slist "foo") (slist "foobar")
Just (Slist {sList = "bar", sSize = Size 3})
>>> stripPrefix (slist "foo") (slist "foo")
Just (Slist {sList = "", sSize = Size 0})
>>> stripPrefix (slist "foo") (slist "barfoo")
Nothing
>>> stripPrefix mempty  (slist "foo")
Just (Slist {sList = "foo", sSize = Size 3})
>>> stripPrefix (infiniteSlist [0..]) (infiniteSlist [1..])
Nothing

/Note:/ this function could hang on the infinite slists.

@
>> __stripPrefix (infiniteSlist [1..]) (infiniteSlist [1..])__
\</hangs/\>
@

Use 'safeStripPrefix' instead.
-}
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 #-}

{- | Similar to 'stripPrefix', but never hangs on infinite lists
and returns 'Nothing' in that case.

>>> safeStripPrefix (infiniteSlist [1..]) (infiniteSlist [1..])
Nothing
>>> safeStripPrefix (infiniteSlist [0..]) (infiniteSlist [1..])
Nothing

-}
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 #-}

{- | @O(n)@. Takes a slist and returns a slist of slists such
that the concatenation of the result is equal to the argument.
Moreover, each sublist in the result contains only equal elements.

It is a special case of 'groupBy', which allows
to supply their own equality test.

>>> group $ slist "Mississippi"
Slist {sList = [Slist {sList = "M", sSize = Size 1},Slist {sList = "i", sSize = Size 1},Slist {sList = "ss", sSize = Size 2},Slist {sList = "i", sSize = Size 1},Slist {sList = "ss", sSize = Size 2},Slist {sList = "i", sSize = Size 1},Slist {sList = "pp", sSize = Size 2},Slist {sList = "i", sSize = Size 1}], sSize = Size 8}
>>> group mempty
Slist {sList = [], sSize = Size 0}

-}
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 #-}

{- | @O(n)@. Non-overloaded version of the 'group' function.

>>> groupBy (>) $ slist "Mississippi"
Slist {sList = [Slist {sList = "M", sSize = Size 1},Slist {sList = "i", sSize = Size 1},Slist {sList = "s", sSize = Size 1},Slist {sList = "si", sSize = Size 2},Slist {sList = "s", sSize = Size 1},Slist {sList = "sippi", sSize = Size 5}], sSize = Size 6}

-}
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 #-}

{- | @O(n)@. Returns all initial segments of the argument, shortest first.

>>> inits $ slist "abc"
Slist {sList = [Slist {sList = "", sSize = Size 0},Slist {sList = "a", sSize = Size 1},Slist {sList = "ab", sSize = Size 2},Slist {sList = "abc", sSize = Size 3}], sSize = Size 4}
>>> inits mempty
Slist {sList = [Slist {sList = [], sSize = Size 0}], sSize = Size 1}

-}
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 #-}

{- | @O(n)@. Returns all final segments of the argument, shortest first.

>>> tails $ slist "abc"
Slist {sList = [Slist {sList = "abc", sSize = Size 3},Slist {sList = "bc", sSize = Size 2},Slist {sList = "c", sSize = Size 1},Slist {sList = "", sSize = Size 0}], sSize = Size 4}
>>> tails mempty
Slist {sList = [Slist {sList = [], sSize = Size 0}], sSize = Size 1}

-}
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 #-}

{- | @O(m)@.
Takes two slists and returns 'True' iff the first slist
is a prefix of the second.

>>> isPrefixOf (slist "Hello") (slist "Hello World!")
True
>>> isPrefixOf (slist "Hello World!") (slist "Hello")
False
>>> isPrefixOf mempty (slist "hey")
True

/Note:/ this function could hang on the infinite slists.

@
>> __isPrefixOf (infiniteSlist [1..]) (infiniteSlist [1..])__
\</hangs/\>
@

Use 'safeIsPrefixOf' instead.

-}
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 #-}

{- | Similar to 'isPrefixOf', but never hangs on infinite lists
and returns 'False' in that case.

>>> safeIsPrefixOf (infiniteSlist [1..]) (infiniteSlist [1..])
False
>>> safeIsPrefixOf (infiniteSlist [0..]) (infiniteSlist [1..])
False
-}
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 #-}

{- |
Takes two slists and returns 'True' iff the first slist
is a suffix of the second.

>>> isSuffixOf (slist "World!") (slist "Hello World!")
True
>>> isSuffixOf (slist "Hello World!") (slist "Hello")
False
>>> isSuffixOf mempty (slist "hey")
True

/Note:/ this function hangs if the second slist is infinite.

@
>> __isSuffixOf /anything/ (infiniteSlist [1..])__
\</hangs/\>
@

Use 'safeIsSuffixOf' instead.
-}
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 #-}

{- | Similar to 'isSuffixOf', but never hangs on infinite lists
and returns 'False' in that case.

>>> safeIsSuffixOf (slist [1,2]) (infiniteSlist [1..])
False
>>> safeIsSuffixOf (infiniteSlist [1..]) (infiniteSlist [1..])
False
-}
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 #-}

{- |
Takes two slists and returns 'True' iff the first slist
is contained, wholly and intact, anywhere within the second.

>>> isInfixOf (slist "ll") (slist "Hello World!")
True
>>> isInfixOf (slist " Hello") (slist "Hello")
False
>>> isInfixOf (slist "Hello World!") (slist "Hello")
False

/Note:/ this function could hang on the infinite slists.

@
>> __isPrefixOf (infiniteSlist [1..]) (infiniteSlist [1..])__
\</hangs/\>
@

Use 'safeIsInfixOf' instead.
-}
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 #-}

{- | Similar to 'isInfixOf', but never hangs on infinite lists
and returns 'False' in that case.

>>> safeIsInfixOf (infiniteSlist [1..]) (infiniteSlist [1..])
False
>>> safeIsInfixOf (infiniteSlist [0..]) (infiniteSlist [1..])
False
-}
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 #-}

{- |
Takes two slists and returns 'True' if all the elements
of the first slist occur, in order, in the second.
The elements do not have to occur consecutively.

@isSubsequenceOf x y@ is equivalent to @'elem' x ('subsequences' y)@.

>>> isSubsequenceOf (slist "Hll") (slist "Hello World!")
True
>>> isSubsequenceOf (slist "") (slist "Hello World!")
True
>>> isSubsequenceOf (slist "Hallo") (slist "Hello World!")
False

/Note:/ this function hangs if the second slist is infinite.

@
>> __isSuffixOf /anything/ (infiniteSlist [1..])__
\</hangs/\>
@

Use 'safeIsSuffixOf' instead.
-}
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 #-}

{- | Similar to 'isSubsequenceOf', but never hangs on infinite lists
and returns 'False' in that case.

>>> safeIsSubsequenceOf (infiniteSlist [1..]) (infiniteSlist [1..])
False
>>> safeIsSubsequenceOf (infiniteSlist [0..]) (infiniteSlist [1..])
False
-}
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 #-}

----------------------------------------------------------------------------
-- Searching
----------------------------------------------------------------------------

{- | @O(n)@.
Looks up by the given key in the slist of key-value pairs.

>>> lookup 42 $ slist $ [(1, "one"), (2, "two")]
Nothing
>>> lookup 42 $ slist $ [(1, "one"), (2, "two"), (42, "life, the universe and everything")]
Just "life, the universe and everything"
>>> lookup 1 $ zip (infiniteSlist  [1..]) (infiniteSlist [0..])
Just 0
-}
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 #-}

{- | @O(n)@.
Returns the slist of the elements that satisfy the given predicate.

>>> filter (<3) $ slist [1..5]
Slist {sList = [1,2], sSize = Size 2}
>>> take 5 $ filter odd $ infiniteSlist [1..]
Slist {sList = [1,3,5,7,9], sSize = Size 5}
-}
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 #-}

{- | @O(n)@.
Returns the pair of slists of elements which do and do not satisfy
the given predicate.

>>> partition (<3) $ slist [1..5]
(Slist {sList = [1,2], sSize = Size 2},Slist {sList = [3,4,5], sSize = Size 3})
-}
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 #-}

----------------------------------------------------------------------------
-- Indexing
----------------------------------------------------------------------------

{- | @O(i) | i < n@ and @O(1) | otherwise@.

Returns the element of the slist at the given position.
If the @i@ exceeds the length of the slist the function returns 'Nothing'.

>>> let sl = slist [1..10]
>>> at 0 sl
Just 1
>>> at (-1) sl
Nothing
>>> at 11 sl
Nothing
>>> at 9 sl
Just 10
-}
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 #-}

{- | @O(min i n)@.
Unsafe version of the 'at' function.
If the element on the given position does not exist
it throws the exception at run-time.

>>> let sl = slist [1..10]
>>> unsafeAt 0 sl
1
>>> unsafeAt (-1) sl
*** Exception: Prelude.!!: negative index
>>> unsafeAt 11 sl
*** Exception: Prelude.!!: index too large
>>> unsafeAt 9 sl
10
-}
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 #-}

{- | @O(n)@.
Returns the index of the first element in the given slist which is equal
(by '==') to the query element, or 'Nothing' if there is no such element.

>>> elemIndex 5 $ slist [1..10]
Just 4
>>> elemIndex 0 $ slist [1..10]
Nothing
-}
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 #-}

{- | @O(n)@.
Extends 'elemIndex', by returning the indices of all elements equal
to the query element, in ascending order.

>>> elemIndices 1 $ slist [1,1,1,2,2,4,5,1,9,1]
Slist {sList = [0,1,2,7,9], sSize = Size 5}
>>> take 5 $ elemIndices 1 $ repeat 1
Slist {sList = [0,1,2,3,4], sSize = Size 5}
-}
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 #-}

{- | @O(n)@.
Returns the index of the first element in the slist satisfying
the given predicate, or 'Nothing' if there is no such element.

>>> findIndex (>3) $ slist [1..5]
Just 3
>>> findIndex (<0) $ slist [1..5]
Nothing
-}
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 #-}

{- | @O(n)@.
Extends 'findIndex', by returning the indices of all elements
satisfying the given predicate, in ascending order.

>>> findIndices (<3) $ slist [1..5]
Slist {sList = [0,1], sSize = Size 2}
>>> findIndices (<0) $ slist [1..5]
Slist {sList = [], sSize = Size 0}
>>> take 5 $ findIndices (<=10) $ infiniteSlist [1..]
Slist {sList = [0,1,2,3,4], sSize = Size 5}
-}
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 #-}

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

{- | @O(min n m)@.
Takes two slists and returns a slist of corresponding pairs.

>>> zip (slist [1,2]) (slist ["one", "two"])
Slist {sList = [(1,"one"),(2,"two")], sSize = Size 2}
>>> zip (slist [1,2,3]) (slist ["one", "two"])
Slist {sList = [(1,"one"),(2,"two")], sSize = Size 2}
>>> zip (slist [1,2]) (slist ["one", "two", "three"])
Slist {sList = [(1,"one"),(2,"two")], sSize = Size 2}
>>> zip mempty (slist [1..5])
Slist {sList = [], sSize = Size 0}
>>> zip (infiniteSlist [1..]) (slist ["one", "two"])
Slist {sList = [(1,"one"),(2,"two")], sSize = Size 2}
-}
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 #-}

{- | @O(minimum [n1, n2, n3])@.
Takes three slists and returns a slist of triples, analogous to '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 #-}

{- | @O(min n m)@.
Generalises 'zip' by zipping with the given function, instead of a tupling function.

For example, @zipWith (+)@ is applied to two lists to produce the list of corresponding sums.
-}
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 #-}

{- | @O(minimum [n1, n2, n3])@.
Takes a function which combines three elements, as well as three slists
and returns a slist of their point-wise combination, analogous to '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 #-}

{- | @O(n)@.
Transforms a slist of pairs into a slist of first components
and a slist of second components.

>>> unzip $ slist [(1,"one"),(2,"two")]
(Slist {sList = [1,2], sSize = Size 2},Slist {sList = ["one","two"], sSize = Size 2})
-}
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 #-}

{- | @O(n)@.
Takes a slist of triples and returns three slists, analogous to '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 #-}

----------------------------------------------------------------------------
-- Sets
----------------------------------------------------------------------------

{- $sets

Set is a special case of slists so that it consist of the unique elements.

Example of set:

@
Slist {sList = "qwerty", sSize = Size 6}
Slist {sList = [1..], sSize = Infinity}
@
-}

{- | @O(n^2)@.
Removes duplicate elements from a slist. In particular,
it keeps only the first occurrence of each element.

It is a special case of 'nubBy', which allows to supply your own equality test.

>>> nub $ replicate 5 'a'
Slist {sList = "a", sSize = Size 1}
>>> nub mempty
Slist {sList = [], sSize = Size 0}
>>> nub $ slist [1,2,3,4,3,2,1,2,4,3,5]
Slist {sList = [1,2,3,4,5], sSize = Size 5}
-}
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 #-}

{- | @O(n^2)@.
Behaves just like 'nub', except it uses a user-supplied equality predicate
instead of the overloaded '==' function.

>>> nubBy (\x y -> mod x 3 == mod y 3) $ slist [1,2,4,5,6]
Slist {sList = [1,2,6], sSize = Size 3}
-}
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 #-}

{- | @O(n)@.
Removes the first occurrence of the given element from its slist argument.

>>> delete 'h' $ slist "hahaha"
Slist {sList = "ahaha", sSize = Size 5}
>>> delete 0 $ slist [1..3]
Slist {sList = [1,2,3], sSize = Size 3}
-}
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 #-}

{- | @O(n)@.
Behaves like 'delete', but takes a user-supplied equality predicate.

>>> deleteBy (>=) 4 $ slist [1..10]
Slist {sList = [2,3,4,5,6,7,8,9,10], sSize = Size 9}
-}
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 #-}

{- | @O(n*m)@.
Takes a predicate and two slists and returns the first slist
with the first occurrence of each element of the second slist removed.

>>> deleteFirstsBy (==) (slist [1..5]) (slist [2,8,4,10,1])
Slist {sList = [3,5], sSize = Size 2}
-}
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 #-}

{- | @O(n*m)@.
Returns the difference between two slists. The operation is non-associative.
In the result of @diff xs ys@, the first occurrence of each element of @ys@
in turn (if any) has been removed from @xs@. Thus

> diff (xs <> ys) ys == xs

>>> diff (slist [1..10]) (slist [1,3..10])
Slist {sList = [2,4,6,8,10], sSize = Size 5}
>>> diff (slist [1,3..10]) (slist [2,4..10])
Slist {sList = [1,3,5,7,9], sSize = Size 5}
-}
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 #-}

{- | @O(n*m)@.
Returns the list union of the two slists.

>>> union (slist "pen") (slist "apple")
Slist {sList = "penal", sSize = Size 5}

Duplicates, and elements of the first slist, are removed from the the second slist,
but if the first slist contains duplicates, so will the result.

>>> union (slist "apple") (slist "pen")
Slist {sList = "applen", sSize = Size 6}

It is a special case of 'unionBy'.
-}
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 #-}

{- | @O(n*m)@.
Non-overloaded version of '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 #-}

{- | @O(n*m)@.
Returns the slist intersection of two slists.

>>> intersect (slist [1,2,3,4]) (slist [2,4,6,8])
Slist {sList = [2,4], sSize = Size 2}

If the first list contains duplicates, so will the result.

>>> intersect (slist [1,2,2,3,4]) (slist [6,4,4,2])
Slist {sList = [2,2,4], sSize = Size 3}

If the first slist is infinite, so will be the result.

If the element is found in both the first and the second slist,
the element from the first slist will be used.

It is a special case of 'intersectBy'.
-}
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 #-}

{- | @O(n*m)@.
Non-overloaded version of '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 #-}

----------------------------------------------------------------------------
-- Ordered slists
----------------------------------------------------------------------------

{- | @O(n log n)@.
implements a stable sorting algorithm. It is a special case of 'sortBy'.

Elements are arranged from from lowest to highest, keeping duplicates
in the order they appeared in the input.

>>> sort $ slist [10, 9..1]
Slist {sList = [1,2,3,4,5,6,7,8,9,10], sSize = Size 10}

/Note:/ this function hangs on infinite slists.
-}
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 #-}

{- | @O(n log n)@.
Non-overloaded version of 'sort'.

>>> sortBy (\(a,_) (b,_) -> compare a b) $ slist [(2, "world"), (4, "!"), (1, "Hello")]
Slist {sList = [(1,"Hello"),(2,"world"),(4,"!")], sSize = Size 3}

/Note:/ this function hangs on infinite slists.
-}
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 #-}

{- | @O(n log n)@.
Sorts a list by comparing the results of a key function applied to each
element.  @sortOn f@ is equivalent to @'sortBy' (comparing f)@, but has the
performance advantage of only evaluating @f@ once for each element in the
input list.  This is called the decorate-sort-undecorate paradigm, or
Schwartzian transform.

Elements are arranged from lowest to highest, keeping duplicates in
the order they appeared in the input.

>>> sortOn fst $ slist [(2, "world"), (4, "!"), (1, "Hello")]
Slist {sList = [(1,"Hello"),(2,"world"),(4,"!")], sSize = Size 3}

/Note:/ this function hangs on infinite slists.
-}
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 #-}

{- | @O(n)@.
Takes an element and a slist and inserts the element into the slist
at the first position where it is less than or equal to the next element.
In particular, if the list is sorted before the call, the result will also
be sorted. It is a special case of 'insertBy'.

>>> insert 4 $ slist [1,2,3,5,6]
Slist {sList = [1,2,3,4,5,6], sSize = Size 6}
-}
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 #-}

-- | @O(n)@. The non-overloaded version of '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 #-}

----------------------------------------------------------------------------
-- Generic fuctions
----------------------------------------------------------------------------

{- | @O(1)@.
The 'genericLength' function is an overloaded version of 'length'.
In particular, instead of returning an 'Int', it returns any type which is an
instance of 'Num'.

>>> genericLength $ one 42
1
>>> genericLength $ slist [1..3]
3
>>> genericLength $ infiniteSlist [1..]
9223372036854775807
-}
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 #-}

{- | @O(i) | i < n@ and @O(1) | otherwise@.
The 'genericTake' function is an overloaded version of 'take', which
accepts any 'Integral' value as the number of elements to take.

>>> genericTake 5 $ slist "Hello world!"
Slist {sList = "Hello", sSize = Size 5}
>>> genericTake 20 $ slist "small"
Slist {sList = "small", sSize = Size 5}
>>> genericTake 0 $ slist "none"
Slist {sList = "", sSize = Size 0}
>>> genericTake (-11) $ slist "hmm"
Slist {sList = "", sSize = Size 0}
>>> genericTake 4 $ infiniteSlist [1..]
Slist {sList = [1,2,3,4], sSize = Size 4}
-}
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 #-}

{- | @O(i) | i < n@ and @O(1) | otherwise@.
The 'genericDrop' function is an overloaded version of 'drop', which accepts
any 'Integral' value as the number of elements to drop.

>>> genericDrop 6 $ slist "Hello World"
Slist {sList = "World", sSize = Size 5}
>>> genericDrop 42 $ slist "oops!"
Slist {sList = "", sSize = Size 0}
>>> genericDrop 0 $ slist "Hello World!"
Slist {sList = "Hello World!", sSize = Size 12}
>>> genericDrop (-4) $ one 42
Slist {sList = [42], sSize = Size 1}

@
>> __drop 5 $ 'infiniteSlist' [1..]__
Slist {sList = [6..], sSize = 'Infinity'}
@

-}
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 #-}

{- | @O(i) | i < n@ and @O(1) | otherwise@.
The 'genericSplitAt' function is an overloaded version of 'splitAt', which
accepts any 'Integral' value as the position at which to split.

>>> genericSplitAt 5 $ slist "Hello World!"
(Slist {sList = "Hello", sSize = Size 5},Slist {sList = " World!", sSize = Size 7})
>>> genericSplitAt 0 $ slist "abc"
(Slist {sList = "", sSize = Size 0},Slist {sList = "abc", sSize = Size 3})
>>> genericSplitAt 4 $ slist "abc"
(Slist {sList = "abc", sSize = Size 3},Slist {sList = "", sSize = Size 0})
>>> genericSplitAt (-42) $ slist "??"
(Slist {sList = "", sSize = Size 0},Slist {sList = "??", sSize = Size 2})

@
>> __genericSplitAt 2 $ 'infiniteSlist' [1..]__
(Slist {sList = [1,2], sSize = 'Size' 2}, Slist {sList = [3..], sSize = 'Infinity'})
@

-}
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 #-}

{- | @O(i) | i < n@ and @O(1) | otherwise@.
The 'genericAt' function is an overloaded version of 'at', which
accepts any 'Integral' value as the position. If the element on the given
position does not exist it will return 'Nothing'.

>>> let sl = slist [1..10]
>>> genericAt 0 sl
Just 1
>>> genericAt (-1) sl
Nothing
>>> genericAt 11 sl
Nothing
>>> genericAt 9 sl
Just 10
-}
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 #-}

{- | @O(min i n)@.
The 'genericUnsafeAt' function is an overloaded version of 'unsafeAt', which
accepts any 'Integral' value as the position. If the element on the given
position does not exist it throws the exception at run-time.

>>> let sl = slist [1..10]
>>> genericUnsafeAt 0 sl
1
>>> genericUnsafeAt (-1) sl
*** Exception: Slist.genericUnsafeAt: negative argument
>>> genericUnsafeAt 11 sl
*** Exception: Slist.genericUnsafeAt: index too large
>>> genericUnsafeAt 9 sl
10
-}
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 #-}

{- | @O(n)@.
The 'genericReplicate' function is an overloaded version of 'replicate',
which accepts any 'Integral' value as the number of repetitions to make.

>>> genericReplicate 3 'o'
Slist {sList = "ooo", sSize = Size 3}
>>> genericReplicate (-11) "hmm"
Slist {sList = [], sSize = Size 0}
-}
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 #-}