-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Sized list
--
-- This package implements Slist data structure that stores the
-- size of the list along with the list itself.
@package slist
@version 0.0.0
-- | Lists size representation
module Slist.Size
-- | Data type that represents lists size/lengths.
--
-- TODO: table
--
-- Note, that size is not suppose to have negative value, so use the
-- Size constructor carefully.
data Size
-- | Finite size
Size :: !Int -> Size
-- | Infinite size.
Infinity :: Size
-- | Returns the list of sizes from zero to the given one (including).
--
--
-- >>> sizes $ Size 3
-- [Size 0,Size 1,Size 2,Size 3]
--
--
--
-- >> sizes Infinity
-- [Size 0, Size 1, ..., Size maxBound, Infinity]
--
sizes :: Size -> [Size]
instance GHC.Classes.Ord Slist.Size.Size
instance GHC.Classes.Eq Slist.Size.Size
instance GHC.Read.Read Slist.Size.Size
instance GHC.Show.Show Slist.Size.Size
instance GHC.Num.Num Slist.Size.Size
instance GHC.Enum.Bounded Slist.Size.Size
-- | 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
-- <math>). 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.
--
-- TODO: table
--
-- 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.
-- - 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
-- | Data type that represents sized list. Size can be both finite or
-- infinite, it is established using Size data type.
data Slist a
-- | Data type that represents lists size/lengths.
--
-- TODO: table
--
-- Note, that size is not suppose to have negative value, so use the
-- Size constructor carefully.
data Size
-- | O(n). Constructs Slist from the given list.
--
--
-- >>> slist [1..5]
-- Slist {sList = [1,2,3,4,5], sSize = Size 5}
--
--
-- Note: works with finite lists. Use infiniteSlist to
-- construct infinite lists.
slist :: [a] -> Slist a
-- | O(1). Constructs Slist from the given list.
--
--
-- >> infiniteSlist [1..]
-- Slist {sList = [1..], sSize = Infinity}
--
--
-- Note: works with infinite lists. Use slist to construct
-- finite lists.
infiniteSlist :: [a] -> Slist a
-- | O(1). Creates Slist with a single element. The size of
-- such Slist is always equals to Size 1.
--
--
-- >>> one "and only"
-- Slist {sList = ["and only"], sSize = Size 1}
--
one :: a -> Slist a
-- | 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: 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
-- | 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
-- | 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
-- | 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
-- | 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
-- | O(1). Returns the length of a structure as an Int. On
-- infinite lists returns the Ints maxBound.
--
--
-- >>> len $ one 42
-- 1
--
-- >>> len $ slist [1..3]
-- 3
--
-- >>> len $ infiniteSlist [1..]
-- 9223372036854775807
--
len :: Slist a -> Int
-- | O(1). Returns the Size of the slist.
--
--
-- >>> size $ slist "Hello World!"
-- Size 12
--
-- >>> size $ infiniteSlist [1..]
-- Infinity
--
size :: Slist a -> Size
-- | O(1). Checks if Slist is empty
--
--
-- >>> isEmpty mempty
-- True
--
-- >>> isEmpty $ slist []
-- True
--
-- >>> isEmpty $ slist "Not Empty"
-- False
--
isEmpty :: Slist a -> Bool
-- | O(1). Extracts the first element of a slist. Uses not total
-- 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
-- | 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
-- | O(n). Extracts the last element of a list. Uses not total
-- 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
-- | 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
-- | 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
-- | 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
-- | 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)
-- | O(n). Applies the given function to each element of the
-- slist.
--
--
-- map f (slist [x1, x2, ..., xn]) == slist [f x1, f x2, ..., f xn]
-- map f (infiniteSlist [x1, x2, ...]) == infiniteSlist [f x1, f x2, ...]
--
map :: (a -> b) -> Slist a -> Slist b
-- | 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
-- | 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
-- | 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
-- | 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
-- | 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)
-- | 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)
-- | 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)
-- | <math> 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
-- | 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
-- | 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
-- | O(n). A strictly accumulating version of scanl
scanl' :: (b -> a -> b) -> b -> Slist a -> Slist b
-- | 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
-- | 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
-- | A variant of scanr that has no starting value argument.
scanr1 :: (a -> a -> a) -> Slist a -> Slist a
-- | 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
-- | 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
-- | 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
-- | 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)
-- | 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
-- | 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 :: forall a. (a -> Bool) -> Slist a -> Slist a
-- | 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)
-- | 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)
-- | 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)
-- | 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)
-- | 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)
-- | 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)
-- | 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)
-- | 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)
-- | 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
-- | 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
-- | 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
-- | 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
-- | 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
-- | 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
-- | 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
-- | 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
-- | 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
-- | 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
-- | 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)
-- | 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
-- | 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
-- | 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
-- | 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
-- | 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
-- | 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
-- | 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)
-- | 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)
-- | 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
-- | 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
-- | 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)
-- | 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)
-- | 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
-- | 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
-- | 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
-- | 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
-- | 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
-- | 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
-- | 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
-- | O(n*m). Non-overloaded version of union.
unionBy :: (a -> a -> Bool) -> Slist a -> Slist a -> Slist a
-- | 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
-- | O(n*m). Non-overloaded version of intersect.
intersectBy :: forall a. (a -> a -> Bool) -> Slist a -> Slist a -> Slist a
-- | 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
-- | 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
-- | 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
-- | 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
-- | O(n). The non-overloaded version of insert.
insertBy :: (a -> a -> Ordering) -> a -> Slist a -> Slist a
instance GHC.Read.Read a => GHC.Read.Read (Slist.Slist a)
instance GHC.Show.Show a => GHC.Show.Show (Slist.Slist a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Slist.Slist a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Slist.Slist a)
instance GHC.Base.Semigroup (Slist.Slist a)
instance GHC.Base.Monoid (Slist.Slist a)
instance GHC.Base.Functor Slist.Slist
instance GHC.Base.Applicative Slist.Slist
instance GHC.Base.Alternative Slist.Slist
instance GHC.Base.Monad Slist.Slist
instance Data.Foldable.Foldable Slist.Slist
instance Data.Traversable.Traversable Slist.Slist
instance GHC.Exts.IsList (Slist.Slist a)