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

{- HLINT ignore "Use mconcat" -}

{- |
Copyright:  (c) 2019-2020 Veronika Romashkina
            (c) 2020-2021 Kowainik
SPDX-License-Identifier: MPL-2.0
Maintainer: Kowainik <xrom.xkov@gmail.com>
Stability:   Stable
Portability: Portable

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
    , append'
    , cons
    , cons'
    , uncons

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

      -- *  Reducing slists (folds)
    , concat
    , concat'
    , concatMap
    , 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
    , chunksOf
    , listChunksOf
      -- ** Predicates
    , isPrefixOf
    , safeIsPrefixOf
    , isSuffixOf
    , safeIsSuffixOf
    , isInfixOf
    , safeIsInfixOf
    , isSubsequenceOf
    , safeIsSubsequenceOf

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

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

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

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

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

     -- * Generic functions
    , genericLength
    , genericTake
    , genericDrop
    , genericSplitAt
    , genericAt
    , genericUnsafeAt
    , genericReplicate

         -- * Maybe
    , maybeToSlist
    , slistToMaybe
    , catMaybes
    , mapMaybe
    , slistWith

      -- * Containers
      -- ** Map
    , mapToVals
    , mapToKeys
    , mapToPairs

      -- ** Set
    , setToSlist

    ) where

import Data.Bifunctor (bimap, first, second)
import Data.Either (partitionEithers)
import Data.Foldable (foldl')
#if ( __GLASGOW_HASKELL__ == 802 )
import Data.Semigroup (Semigroup (..))
#endif
import GHC.Exts (fromListN)
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.Containers (mapToKeys, mapToPairs, mapToVals, setToSlist)
import Slist.Maybe (catMaybes, mapMaybe, maybeToSlist, slistToMaybe, slistWith)
import Slist.Size (Size (..), sizes)
import Slist.Type (Slist (..), cons, infiniteSlist, isEmpty, len, map, one, size, slist)

import qualified Data.List as L
import qualified Data.Set as Set
import qualified GHC.Exts as Exts
import qualified Prelude as P


{- | 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 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' 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 Int
n a
x
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
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 [a]
_ Size
Infinity) = Slist a
sl
cycle Slist{[a]
Size
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
sSize :: Size
sList :: [a]
..}             = [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 a
from 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 Int
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
+ Int
1)
{-# INLINE fromRange #-}

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


{- | @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{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = case Size
sSize of
    Size Int
0 -> Maybe a
forall a. Maybe a
Nothing
    Size
_      -> 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{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = case Size
sSize of
    Size
Infinity -> Maybe a
forall a. Maybe a
Nothing
    Size Int
0   -> Maybe a
forall a. Maybe a
Nothing
    Size
_        -> 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{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = case Size
sSize of
    Size Int
0 -> Slist a
forall a. Monoid a => a
mempty
    Size
_      -> [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist (Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
P.drop Int
1 [a]
sList) (Size
sSize Size -> Size -> Size
forall a. Num a => a -> a -> a
- Size
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{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = case Size
sSize of
    Size
Infinity -> Slist a
sl
    Size Int
0   -> Slist a
forall a. Monoid a => a
mempty
    Size
_        -> [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
- Size
1)
{-# INLINE init #-}

{- | Strict version of the 'Slist' appending operator '<>'.

@since 0.2.0.0
-}
append' :: Slist a -> Slist a -> Slist a
append' :: Slist a -> Slist a -> Slist a
append' Slist a
sl1 Slist a
sl2
    | Slist a -> Size
forall a. Slist a -> Size
sSize Slist a
sl1 Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Size
0 = Slist a
sl2
    | Slist a -> Size
forall a. Slist a -> Size
sSize Slist a
sl2 Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Size
0 = Slist a
sl1
    | Bool
otherwise = let !newSize :: Size
newSize = Slist a -> Size
forall a. Slist a -> Size
sSize Slist a
sl1 Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Slist a -> Size
forall a. Slist a -> Size
sSize Slist a
sl2 in Slist :: forall a. [a] -> Size -> Slist a
Slist
        { sList :: [a]
sList = Slist a -> [a]
forall a. Slist a -> [a]
sList Slist a
sl1 [a] -> [a] -> [a]
forall a. Semigroup a => a -> a -> a
<> Slist a -> [a]
forall a. Slist a -> [a]
sList Slist a
sl2
        , sSize :: Size
sSize = Size
newSize
        }

{- | @O(1)@. Strict version of the 'cons' function
(in terms of the size evaluation).

The following property is preserved:

@
  'size' ('cons'' x xs) == 'size' xs + 1
@

Examples:

>>> cons' 'a' $ one 'b'
Slist {sList = "ab", sSize = Size 2}

@
>> __cons' 0 $ 'infiniteSlist' [1..]__
Slist {sList = [0..], sSize = 'Infinity'}
@

@since 0.2.0.0
-}
cons' :: a -> Slist a -> Slist a
cons' :: a -> Slist a -> Slist a
cons' a
x (Slist [a]
xs !Size
s) = let !newSize :: Size
newSize = Size
s Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
1 in [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs) Size
newSize
{-# INLINE cons' #-}

{- | @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 [] Size
_)     = Maybe (a, Slist a)
forall a. Maybe a
Nothing
uncons (Slist (a
x:[a]
xs) 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
- Size
1)
{-# INLINE uncons #-}

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


{- | @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
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = [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 [a]
_ Size
Infinity) = Slist a
sl
safeReverse 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 a
_ sl :: Slist a
sl@(Slist [a]
_ (Size Int
0)) = Slist a
sl
intersperse a
a Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..}             = [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) (Size
2 Size -> Size -> Size
forall a. Num a => a -> a -> a
* Size
sSize Size -> Size -> Size
forall a. Num a => a -> a -> a
- Size
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 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 [Slist a]
l Size
_) = 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{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = 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 Size
Infinity = Size
Infinity
    newSize (Size Int
n) = Int -> Size
Size (Int -> Size) -> Int -> Size
forall a b. (a -> b) -> a -> b
$ Int
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 [a]
l 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 Size
Infinity = Size
Infinity
    fact (Size Int
n) = Int -> Size
Size (Int -> Size) -> Int -> Size
forall a b. (a -> b) -> a -> b
$ Int -> Int -> Int
go Int
1 Int
n

    go :: Int -> Int -> Int
    go :: Int -> Int -> Int
go !Int
acc Int
0 = Int
acc
    go !Int
acc 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
- Int
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 #-}

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

The strict version of 'concat'.

>>> 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'}
@

@since 0.2.0.0
-}
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 :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' Slist a -> Slist a -> Slist a
forall a. Slist a -> Slist a -> Slist a
append' 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 #-}

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

Strict version of 'concatMap'.

>>> concatMap' one "abc"
Slist {sList = "abc", sSize = Size 3}

@since 0.2.0.0
-}
concatMap' :: Foldable t => (a -> Slist b) -> t a -> Slist b
concatMap' :: (a -> Slist b) -> t a -> Slist b
concatMap' a -> Slist b
f = (Slist b -> a -> Slist b) -> Slist b -> t a -> Slist b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\Slist b
acc a
x -> Slist b
acc Slist b -> Slist b -> Slist b
forall a. Slist a -> Slist a -> Slist a
`append'` a -> Slist b
f a
x) Slist b
forall a. Monoid a => a
mempty
{-# 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 b -> a -> b
f b
b Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = [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
+ Size
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' b -> a -> b
f b
b Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = [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
+ Size
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 a -> a -> a
f Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = [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 a -> b -> b
f b
b Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = [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
+ Size
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 a -> a -> a
f Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = [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 b -> Maybe (a, b)
f b
def = let (Int
s, [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 = case b -> Maybe (a, b)
f b
b of
        Just (a
a, 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
+ Int
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
        Maybe (a, b)
Nothing        -> (Int
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 Int
i sl :: Slist a
sl@Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..}
    | 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
<= Int
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 Int
i sl :: Slist a
sl@Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..}
    | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
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 Int
i sl :: Slist a
sl@Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..}
    | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
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 ([a]
l1, [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 a -> Bool
p Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = let (Int
s, [a]
l) = Int -> [a] -> (Int, [a])
go Int
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 (a
x:[a]
xs) =
        if a -> Bool
p a
x
        then let (Int
i, [a]
l) = Int -> [a] -> (Int, [a])
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
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 a -> Bool
p (Slist [a]
l Size
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 a -> Bool
p Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = let (Int
s, [a]
l) = Int -> [a] -> (Int, [a])
go Int
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 (a
x:[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
+ Int
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 a -> Bool
p Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = let (Int
s, [a]
l, [a]
r) = Int -> [a] -> (Int, [a], [a])
go Int
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 (a
x:[a]
xs) =
        if a -> Bool
p a
x
        then let (Int
s, [a]
l, [a]
r) = Int -> [a] -> (Int, [a], [a])
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
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 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(n)@. Splits a 'Slist' into components of the given length. The last
element may be shorter than the other chunks, depending on the length of the
input.

>>> chunksOf 3 $ slist [0..7]
Slist {sList = [Slist {sList = [0,1,2], sSize = Size 3},Slist {sList = [3,4,5], sSize = Size 3},Slist {sList = [6,7], sSize = Size 2}], sSize = Size 3}
>>> chunksOf 0 $ slist [0..10]
Slist {sList = [], sSize = Size 0}
>>> chunksOf (-13) $ slist [0..10]
Slist {sList = [], sSize = Size 0}
>>> chunksOf 100 $ slist [1,2,3]
Slist {sList = [Slist {sList = [1,2,3], sSize = Size 3}], sSize = Size 1}

>>> take 2 $ chunksOf 3 $ infiniteSlist [1..]
Slist {sList = [Slist {sList = [1,2,3], sSize = Size 3},Slist {sList = [4,5,6], sSize = Size 3}], sSize = Size 2}

@since 0.2.0.0
-}
chunksOf :: Int -> Slist a -> Slist (Slist a)
chunksOf :: Int -> Slist a -> Slist (Slist a)
chunksOf Int
i sl :: Slist a
sl@Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..}
    | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = Slist (Slist a)
forall a. Monoid a => a
mempty
    | Size
sSize Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Size
Infinity = [Slist a] -> Size -> Slist (Slist a)
forall a. [a] -> Size -> Slist a
Slist (([a] -> Slist a) -> [[a]] -> [Slist a]
forall a b. (a -> b) -> [a] -> [b]
P.map (Int -> [Item (Slist a)] -> Slist a
forall l. IsList l => Int -> [Item l] -> l
fromListN Int
i) ([[a]] -> [Slist a]) -> [[a]] -> [Slist a]
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> [[a]]
forall a. Int -> [a] -> [[a]]
listChunksOf Int
i [a]
sList) Size
Infinity
    | Bool
otherwise = Slist a -> Slist (Slist a)
forall a. Slist a -> Slist (Slist a)
go Slist a
sl
  where
    go :: Slist a -> Slist (Slist a)
    go :: Slist a -> Slist (Slist a)
go x :: Slist a
x@(Slist [a]
_ Size
s)
        | Int -> Size
Size Int
i Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
>= Size
s = Slist a -> Slist (Slist a)
forall a. a -> Slist a
one Slist a
x
        | Bool
otherwise =
            let (Slist a
chunk, Slist a
rest) = Int -> Slist a -> (Slist a, Slist a)
forall a. Int -> Slist a -> (Slist a, Slist a)
splitAt Int
i Slist a
x
            in Slist a -> Slist (Slist a) -> Slist (Slist a)
forall a. a -> Slist a -> Slist a
cons Slist a
chunk (Slist (Slist a) -> Slist (Slist a))
-> Slist (Slist a) -> Slist (Slist a)
forall a b. (a -> b) -> a -> b
$ Slist a -> Slist (Slist a)
forall a. Slist a -> Slist (Slist a)
go Slist a
rest
{-# INLINE chunksOf #-}

{- | @O(n)@. Splits a list into components of the given length. The last
element may be shorter than the other chunks, depending on the length of the
input.

>>> listChunksOf 3 [0..7]
[[0,1,2],[3,4,5],[6,7]]
>>> listChunksOf 0 [0..10]
[]
>>> listChunksOf (-13) [0..10]
[]
>>> listChunksOf 100 [1,2,3]
[[1,2,3]]

>>> P.take 2 $ listChunksOf 3 [1..]
[[1,2,3],[4,5,6]]

@since 0.2.0.0
-}
listChunksOf :: Int -> [a] -> [[a]]
listChunksOf :: Int -> [a] -> [[a]]
listChunksOf Int
i [a]
l
    | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0 = [[a]]
forall a. Monoid a => a
mempty
    | Bool
otherwise = [a] -> [[a]]
forall a. [a] -> [[a]]
go [a]
l
  where
    go :: [a] -> [[a]]
    go :: [a] -> [[a]]
go [] = []
    go [a]
x =
        let ([a]
chunk, [a]
rest) = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
P.splitAt Int
i [a]
x
        in [a]
chunk [a] -> [[a]] -> [[a]]
forall a. a -> [a] -> [a]
: [a] -> [[a]]
forall a. [a] -> [[a]]
go [a]
rest
{-# INLINE listChunksOf #-}

{- | @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 [a]
l1 Size
s1) f :: Slist a
f@(Slist [a]
l2 Size
s2)
    | Size
s1 Size -> Size -> Bool
forall a. Eq a => a -> a -> Bool
== Int -> Size
Size Int
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 = (\[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 [a]
_ Size
Infinity) (Slist [a]
_ Size
Infinity) = Maybe (Slist a)
forall a. Maybe a
Nothing
safeStripPrefix Slist a
sl1 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 a -> a -> Bool
p (Slist [a]
l Size
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 a -> a -> Bool
p Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..}          = [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 [a]
l 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
+ Size
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 [a]
l Size
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 [a]
l s :: Size
s@(Size 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 (\[a]
li 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
- Int
1 .. Int
0]
    , sSize :: Size
sSize = Size
s Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
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 [a]
l1 Size
s1) (Slist [a]
l2 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 [a]
_ Size
s1) sl2 :: Slist a
sl2@(Slist [a]
_ 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 [a]
l1 Size
s1) (Slist [a]
l2 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 Slist a
sl1 sl2 :: Slist a
sl2@(Slist [a]
_ 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 [a]
l1 Size
s1) (Slist [a]
l2 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 [a]
_ Size
s1) sl2 :: Slist a
sl2@(Slist [a]
_ 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 [a]
l1 Size
s1) (Slist [a]
l2 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 [a]
_ Size
s1) sl2 :: Slist a
sl2@(Slist [a]
_ 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, 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 a -> Bool
p (Slist [a]
l Size
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 a -> Bool
p Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = let (Int
newS, [a]
newL) = Int -> [a] -> (Int, [a])
go Int
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 Int
n (a
x:[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
+ Int
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 a -> Bool
p (Slist [a]
l Size
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 a -> Bool
p Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = let (Int
s1, [a]
l1, [a]
l2) = Int -> [a] -> (Int, [a], [a])
go Int
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 Int
n (a
x:[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
+ Int
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 #-}

{- | @O(n)@.
Returns the pair of slists of elements resulting to 'Left' and resulting to
'Right' by applying the given function.

>>> onEven x = if even x then Right x else Left ("Oops: " ++ show x)
>>> partitionWith onEven $ slist [1..5]
(Slist {sList = ["Oops: 1","Oops: 3","Oops: 5"], sSize = Size 3},Slist {sList = [2,4], sSize = Size 2})

@since 0.2.0.0
-}
partitionWith :: forall a b c . (a -> Either b c) -> Slist a -> (Slist b, Slist c)
partitionWith :: (a -> Either b c) -> Slist a -> (Slist b, Slist c)
partitionWith a -> Either b c
f (Slist [a]
l Size
Infinity) = ([b] -> Slist b)
-> ([c] -> Slist c) -> ([b], [c]) -> (Slist b, Slist c)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [b] -> Slist b
forall a. [a] -> Slist a
infiniteSlist [c] -> Slist c
forall a. [a] -> Slist a
infiniteSlist (([b], [c]) -> (Slist b, Slist c))
-> ([b], [c]) -> (Slist b, Slist c)
forall a b. (a -> b) -> a -> b
$ (a -> Either b c) -> [a] -> ([b], [c])
forall a b c. (a -> Either b c) -> [a] -> ([b], [c])
listPartitionWith a -> Either b c
f [a]
l
partitionWith a -> Either b c
f Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = let (Int
s1, [b]
l1, [c]
l2) = Int -> [a] -> (Int, [b], [c])
go Int
0 [a]
sList in
    ([b] -> Size -> Slist b
forall a. [a] -> Size -> Slist a
Slist [b]
l1 (Size -> Slist b) -> Size -> Slist b
forall a b. (a -> b) -> a -> b
$ Int -> Size
Size Int
s1, [c] -> Size -> Slist c
forall a. [a] -> Size -> Slist a
Slist [c]
l2 (Size -> Slist c) -> Size -> Slist c
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, [b], [c])
    go :: Int -> [a] -> (Int, [b], [c])
go !Int
n [] = (Int
n, [], [])
    go Int
n (a
x:[a]
xs) = case a -> Either b c
f a
x of
        Left  b
b -> ([b] -> [b]) -> (Int, [b], [c]) -> (Int, [b], [c])
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first  (b
bb -> [b] -> [b]
forall a. a -> [a] -> [a]
:) ((Int, [b], [c]) -> (Int, [b], [c]))
-> (Int, [b], [c]) -> (Int, [b], [c])
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> (Int, [b], [c])
go (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) [a]
xs
        Right c
c -> ([c] -> [c]) -> (Int, [b], [c]) -> (Int, [b], [c])
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second (c
cc -> [c] -> [c]
forall a. a -> [a] -> [a]
:) ((Int, [b], [c]) -> (Int, [b], [c]))
-> (Int, [b], [c]) -> (Int, [b], [c])
forall a b. (a -> b) -> a -> b
$ Int -> [a] -> (Int, [b], [c])
go Int
n [a]
xs
{-# INLINE partitionWith #-}

{- | @O(n)@.
Returns the pair of lists of elements resulting to 'Left' and resulting to
'Right' by applying the given function.


>>> onEven x = if even x then Right x else Left ("Oops: " ++ show x)
>>> listPartitionWith onEven [1..5]
(["Oops: 1","Oops: 3","Oops: 5"],[2,4])

@since 0.2.0.0
-}
listPartitionWith :: forall a b c . (a -> Either b c) -> [a] -> ([b], [c])
listPartitionWith :: (a -> Either b c) -> [a] -> ([b], [c])
listPartitionWith a -> Either b c
f = [Either b c] -> ([b], [c])
forall a b. [Either a b] -> ([a], [b])
partitionEithers ([Either b c] -> ([b], [c]))
-> ([a] -> [Either b c]) -> [a] -> ([b], [c])
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Either b c) -> [a] -> [Either b c]
forall a b. (a -> b) -> [a] -> [b]
L.map a -> Either b c
f
{-# INLINE listPartitionWith #-}

----------------------------------------------------------------------------
-- 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 Int
n Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..}
    | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
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 Int
n Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = [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] -> 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 -> 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 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 a -> Bool
p (Slist [a]
l Size
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 a -> Bool
p Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = let (Int
newS, [Int]
newL) = Int -> Int -> [a] -> (Int, [Int])
go Int
0 Int
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
_ [] = (Int
n, [])
    go Int
n !Int
cur (a
x:[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
+ Int
1) (Int
cur Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) [a]
xs
        else Int -> Int -> [a] -> (Int, [Int])
go Int
n (Int
cur Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
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 [a]
l1 Size
s1) (Slist [b]
l2 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 [a]
l1 Size
s1) (Slist [b]
l2 Size
s2) (Slist [c]
l3 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 a -> b -> c
f (Slist [a]
l1 Size
s1) (Slist [b]
l2 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 a -> b -> c -> d
f (Slist [a]
l1 Size
s1) (Slist [b]
l2 Size
s2) (Slist [c]
l3 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{[(a, b)]
Size
sSize :: Size
sList :: [(a, b)]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = let ([a]
as, [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] -> 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{[(a, b, c)]
Size
sSize :: Size
sList :: [(a, b, c)]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = let ([a]
as, [b]
bs, [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] -> 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 a -> a -> Bool
f Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = let (Int
s, [a]
l) = Int -> [a] -> [a] -> (Int, [a])
go Int
0 [] [a]
sList in case Size
sSize of
    Size
Infinity -> [a] -> Slist a
forall a. [a] -> Slist a
infiniteSlist [a]
l
    Size
_        -> [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 [a]
res [] = (Int
n, [a]
res)
    go Int
n [a]
res (a
x:[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
+ Int
1) ([a]
res [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x]) [a]
xs
{-# INLINE nubBy #-}

{- | Removes duplicate elements from a slist, keeping only the first occurance of
the element.

Like 'nub' but runs in \( O(n \log n) \)  time and requires 'Ord'.

>>> ordNub $ slist [3, 3, 3, 2, 2, -1, 1]
Slist {sList = [3,2,-1,1], sSize = Size 4}

-}
ordNub :: forall a . (Ord a) => Slist a -> Slist a
ordNub :: Slist a -> Slist a
ordNub Slist a
sl = let (Int
s, [a]
l) = Int -> Set a -> [a] -> (Int, [a])
go Int
0 Set a
forall a. Set a
Set.empty (Slist a -> [a]
forall a. Slist a -> [a]
sList Slist a
sl) in Slist :: forall a. [a] -> Size -> Slist a
Slist
    { sList :: [a]
sList = [a]
l
    , sSize :: Size
sSize = Int -> Size
Size Int
s
    }
  where
    go :: Int -> Set.Set a -> [a] -> (Int, [a])
    go :: Int -> Set a -> [a] -> (Int, [a])
go !Int
i Set a
_ []     = (Int
i, [])
    go Int
i Set a
s (a
x:[a]
xs) =
      if a
x a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`Set.member` Set a
s
      then Int -> Set a -> [a] -> (Int, [a])
go Int
i Set a
s [a]
xs
      else  ([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 -> Set a -> [a] -> (Int, [a])
go (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
Set.insert a
x Set a
s) [a]
xs
{-# INLINEABLE ordNub #-}

{- | @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 a -> a -> Bool
f a
a (Slist [a]
l Size
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 a -> a -> Bool
f a
a Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = let (Size
del, [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 Int
0, [])
    go (a
x:[a]
xs) = if a -> a -> Bool
f a
a a
x
        then (Int -> Size
Size Int
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 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 a -> a -> Bool
f Slist a
xs 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 a -> a -> Bool
_ (Slist [a]
_ (Size Int
0)) Slist a
_ = Slist a
forall a. Monoid a => a
mempty
intersectBy a -> a -> Bool
_ Slist a
_ (Slist [a]
_ (Size Int
0)) = Slist a
forall a. Monoid a => a
mempty
intersectBy a -> a -> Bool
f (Slist [a]
l1 Size
Infinity) (Slist [a]
l2 Size
_) = [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 a -> a -> Bool
f (Slist [a]
l1 Size
_) (Slist [a]
l2 Size
_) =
    let (Int
s, [a]
l) = Int -> [a] -> (Int, [a])
go Int
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 Int
n [] = (Int
n, [])
    go Int
n (a
x:[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
+ Int
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 a -> a -> Ordering
f Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = [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 a -> b
f Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = [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 log n)@.
Sorts a list by comparing the results of a key function applied to each
element.

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

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

@since 0.2.0.0
-}
sortWith :: Ord b => (a -> b) -> Slist a -> Slist a
sortWith :: (a -> b) -> Slist a -> Slist a
sortWith a -> b
f Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = [a] -> Size -> Slist a
forall a. [a] -> Size -> Slist a
Slist ((a -> b) -> [a] -> [a]
forall b a. Ord b => (a -> b) -> [a] -> [a]
Exts.sortWith a -> b
f [a]
sList) Size
sSize
{-# INLINE sortWith #-}

{- | @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 a -> a -> Ordering
f a
a Slist{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..} = [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
+ Size
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{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..}
    | 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
<= Int
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{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..}
    | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
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{[a]
Size
sSize :: Size
sList :: [a]
sSize :: forall a. Slist a -> Size
sList :: forall a. Slist a -> [a]
..}
    | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
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 ([a]
l1, [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 Slist a
_ | i
i i -> i -> Bool
forall a. Ord a => a -> a -> Bool
< i
0 = [Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace [Char]
"Slist.genericUnsafeAt: negative argument"
genericUnsafeAt i
i (Slist [a]
l Size
Infinity) = [a] -> i -> a
forall i a. Integral i => [a] -> i -> a
L.genericIndex [a]
l i
i
genericUnsafeAt i
i (Slist [a]
l (Size 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 = [Char] -> a
forall a. [Char] -> a
errorWithoutStackTrace [Char]
"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 i
n a
x
    | i
n i -> i -> Bool
forall a. Ord a => a -> a -> Bool
<= i
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 #-}