EdisonAPI-1.3.3.2: src/Data/Edison/Seq.hs
-- |
-- Module : Data.Edison.Seq
-- Copyright : Copyright (c) 1998-1999 Chris Okasaki
-- License : MIT; see COPYRIGHT file for terms and conditions
--
-- Maintainer : robdockins AT fastmail DOT fm
-- Stability : stable
-- Portability : GHC, Hugs (MPTC and FD)
--
-- The sequence abstraction is usually viewed as a hierarchy of ADTs
-- including lists, queues, deques, catenable lists, etc. However, such
-- a hierarchy is based on efficiency rather than functionality. For example,
-- a list supports all the operations that a deque supports, even though
-- some of the operations may be inefficient. Hence, in Edison, all sequence
-- data structures are defined as instances of the single Sequence class:
--
-- @ class (Functor s, MonadPlus s) => Sequence s@
--
-- All sequences are also instances of 'Functor', 'Monad', and 'MonadPlus'.
-- In addition, all sequences are expected to be instances of @Eq@, @Show@,
-- and @Read@, although this is not enforced.
--
-- We follow the naming convention that every module implementing sequences
-- defines a type constructor named @Seq@.
--
-- For each method the \"default\" complexity is listed. Individual
-- implementations may differ for some methods. The documentation for
-- each implementation will list those methods for which the running time
-- differs from these.
--
-- A description of each Sequence function appears below. In most cases
-- psudeocode is also provided. Obviously, the psudeocode is illustrative only.
--
-- Sequences are represented in psudecode between angle brackets:
--
-- > <x0,x1,x2...,xn-1>
--
-- Such that @x0@ is at the left (front) of the sequence and
-- @xn-1@ is at the right (rear) of the sequence.
module Data.Edison.Seq (
-- * Superclass aliases
-- ** Functor aliases
map
-- ** Monad aliases
, singleton
, concatMap
-- ** MonadPlus aliases
, empty
, append
-- * The Sequence class
, Sequence (..)
) where
import Prelude hiding (concat,reverse,map,concatMap,foldr,foldl,foldr1,foldl1,
filter,takeWhile,dropWhile,lookup,take,drop,splitAt,
zip,zip3,zipWith,zipWith3,unzip,unzip3,null)
import Control.Monad
import qualified Control.Monad.Fail as Fail
import Data.Monoid
import Data.Edison.Prelude
-- | Return the result of applying a function to
-- every element of a sequence. Identical
-- to @fmap@ from @Functor@.
--
-- > map f <x0,...,xn-1> = <f x0,...,f xn-1>
--
-- /Axioms:/
--
-- * @map f empty = empty@
--
-- * @map f (lcons x xs) = lcons (f x) (map f xs)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
map :: Sequence s => (a -> b) -> s a -> s b
map = fmap
-- | Create a singleton sequence. Identical to @return@
-- from @Monad@.
--
-- > singleton x = <x>
--
-- /Axioms:/
--
-- * @singleton x = lcons x empty = rcons x empty@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( 1 )@
singleton :: Sequence s => a -> s a
singleton = return
-- | Apply a sequence-producing function to every element
-- of a sequence and flatten the result. 'concatMap'
-- is the bind @(>>=)@ operation of from @Monad@ with the
-- arguments in the reverse order.
--
-- > concatMap f xs = concat (map f xs)
--
-- /Axioms:/
--
-- * @concatMap f xs = concat (map f xs)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n + m )@
-- where @n@ is the length of the input sequence, @m@ is the
-- length of the output sequence, and @t@ is the running time of @f@
concatMap :: Sequence s => (a -> s b) -> s a -> s b
concatMap = flip (>>=)
-- | The empty sequence. Identical to @mzero@
-- from @MonadPlus@.
--
-- > empty = <>
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( 1 )@
empty :: Sequence s => s a
empty = mzero
-- | Append two sequence, with the first argument on the left
-- and the second argument on the right. Identical to @mplus@
-- from @MonadPlus@.
--
-- > append <x0,...,xn-1> <y0,...,ym-1> = <x0,...,xn-1,y0,...,ym-1>
--
-- /Axioms:/
--
-- * @append xs ys = foldr lcons ys xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( n1 )@
append :: Sequence s => s a -> s a -> s a
append = mplus
-- | The 'Sequence' class defines an interface for datatypes which
-- implement sequences. A description for each function is
-- given below.
class (Functor s, MonadPlus s) => Sequence s where
-- | Add a new element to the front\/left of a sequence
--
-- > lcons x <x0,...,xn-1> = <x,x0,...,xn-1>
--
-- /Axioms:/
--
-- * @lcons x xs = append (singleton x) xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( 1 )@
lcons :: a -> s a -> s a
-- | Add a new element to the right\/rear of a sequence
--
-- > rcons x <x0,...,xn-1> = <x0,...,xn-1,x>
--
-- /Axioms:/
--
-- * @rcons x xs = append xs (singleton x)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( n )@
rcons :: a -> s a -> s a
-- | Convert a list into a sequence
--
-- > fromList [x0,...,xn-1] = <x0,...,xn-1>
--
-- /Axioms:/
--
-- * @fromList xs = foldr lcons empty xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( n )@
fromList :: [a] -> s a
-- | Create a sequence containing @n@ copies of the given element.
-- Return 'empty' if @n\<0@.
--
-- @copy n x = \<x,...,x>@
--
-- /Axioms:/
--
-- * @n > 0 ==> copy n x = cons x (copy (n-1) x)@
--
-- * @n \<= 0 ==> copy n x = empty@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( n )@
copy :: Int -> a -> s a
-- | Separate a sequence into its first (leftmost) element and the
-- remaining sequence. Calls 'fail' if the sequence is empty.
--
-- /Axioms:/
--
-- * @lview empty = fail@
--
-- * @lview (lcons x xs) = return (x,xs)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( 1 )@
lview :: (Fail.MonadFail m) => s a -> m (a, s a)
-- | Return the first element of a sequence.
-- Signals an error if the sequence is empty.
--
-- /Axioms:/
--
-- * @lhead empty = undefined@
--
-- * @lhead (lcons x xs) = x@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( 1 )@
lhead :: s a -> a
-- | Returns the first element of a sequence.
-- Calls 'fail' if the sequence is empty.
--
-- /Axioms:/
--
-- * @lheadM empty = fail@
--
-- * @lheadM (lcons x xs) = return x@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( 1 )@
lheadM :: (Fail.MonadFail m) => s a -> m a
-- | Delete the first element of the sequence.
-- Signals error if sequence is empty.
--
-- /Axioms:/
--
-- * @ltail empty = undefined@
--
-- * @ltail (lcons x xs) = xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( 1 )@
ltail :: s a -> s a
-- | Delete the first element of the sequence.
-- Calls 'fail' if the sequence is empty.
--
-- /Axioms:/
--
-- * @ltailM empty = fail@
--
-- * @ltailM (lcons x xs) = return xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( 1 )@
ltailM :: (Fail.MonadFail m) => s a -> m (s a)
-- | Separate a sequence into its last (rightmost) element and the
-- remaining sequence. Calls 'fail' if the sequence is empty.
--
-- /Axioms:/
--
-- * @rview empty = fail@
--
-- * @rview (rcons x xs) = return (x,xs)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( n )@
rview :: (Fail.MonadFail m) => s a -> m (a, s a)
-- | Return the last (rightmost) element of the sequence.
-- Signals error if sequence is empty.
--
-- /Axioms:/
--
-- * @rhead empty = undefined@
--
-- * @rhead (rcons x xs) = x@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( n )@
rhead :: s a -> a
-- | Returns the last element of the sequence.
-- Calls 'fail' if the sequence is empty.
--
-- /Axioms:/
--
-- * @rheadM empty = fail@
--
-- * @rheadM (rcons x xs) = return x@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( n )@
rheadM :: (Fail.MonadFail m) => s a -> m a
-- | Delete the last (rightmost) element of the sequence.
-- Signals an error if the sequence is empty.
--
-- /Axioms:/
--
-- * @rtail empty = undefined@
--
-- * @rtail (rcons x xs) = xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( n )@
rtail :: s a -> s a
-- | Delete the last (rightmost) element of the sequence.
-- Calls 'fail' of the sequence is empty
--
-- /Axioms:/
--
-- * @rtailM empty = fail@
--
-- * @rtailM (rcons x xs) = return xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( n )@
rtailM :: (Fail.MonadFail m) => s a -> m (s a)
-- | Returns 'True' if the sequence is empty and 'False' otherwise.
--
-- > null <x0,...,xn-1> = (n==0)
--
-- /Axioms:/
--
-- * @null xs = (size xs == 0)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( 1 )@
null :: s a -> Bool
-- | Returns the length of a sequence.
--
-- > size <x0,...,xn-1> = n
--
-- /Axioms:/
--
-- * @size empty = 0@
--
-- * @size (lcons x xs) = 1 + size xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( n )@
size :: s a -> Int
-- | Convert a sequence to a list.
--
-- > toList <x0,...,xn-1> = [x0,...,xn-1]
--
-- /Axioms:/
--
-- * @toList empty = []@
--
-- * @toList (lcons x xs) = x : toList xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( n )@
toList :: s a -> [a]
-- | Flatten a sequence of sequences into a simple sequence.
--
-- > concat xss = foldr append empty xss
--
-- /Axioms:/
--
-- * @concat xss = foldr append empty xss@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( n + m )@
-- where @n@ is the length of the input sequence and @m@ is
-- length of the output sequence.
concat :: s (s a) -> s a
-- | Reverse the order of a sequence
--
-- > reverse <x0,...,xn-1> = <xn-1,...,x0>
--
-- /Axioms:/
--
-- * @reverse empty = empty@
--
-- * @reverse (lcons x xs) = rcons x (reverse xs)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( n )@
reverse :: s a -> s a
-- | Reverse a sequence onto the front of another sequence.
--
-- > reverseOnto <x0,...,xn-1> <y0,...,ym-1> = <xn-1,...,x0,y0,...,ym-1>
--
-- /Axioms:/
--
-- * @reverseOnto xs ys = append (reverse xs) ys@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( n1 )@
reverseOnto :: s a -> s a -> s a
-- | Combine all the elements of a sequence into a single value,
-- given a combining function and an initial value. The order
-- in which the elements are applied to the combining function
-- is unspecified. @fold@ is one of the few ambiguous sequence
-- functions.
--
-- /Axioms:/
--
-- * @fold f c empty = c@
--
-- * @f is fold-commutative ==> fold f = foldr f = foldl f@
--
-- @fold f@ is /unambiguous/ iff @f@ is fold-commutative.
--
-- Default running type: @O( t * n )@
-- where @t@ is the running tome of @f@.
fold :: (a -> b -> b) -> b -> s a -> b
-- | A strict variant of 'fold'. @fold'@ is one of the few ambiguous
-- sequence functions.
--
-- /Axioms:/
--
-- * @forall a. f a _|_ = _|_ ==> fold f x xs = fold' f x xs@
--
-- @fold f@ is /unambiguous/ iff @f@ is fold-commutative.
--
-- Default running type: @O( t * n )@
-- where @t@ is the running tome of @f@.
fold' :: (a -> b -> b) -> b -> s a -> b
-- | Combine all the elements of a non-empty sequence into a
-- single value, given a combining function. Signals an error
-- if the sequence is empty.
--
-- /Axioms:/
--
-- * @f is fold-commutative ==> fold1 f = foldr1 f = foldl1 f@
--
-- @fold1 f@ is /unambiguous/ iff @f@ is fold-commutative.
--
-- Default running type: @O( t * n )@
-- where @t@ is the running tome of @f@.
fold1 :: (a -> a -> a) -> s a -> a
-- | A strict variant of 'fold1'.
--
-- /Axioms:/
--
-- * @forall a. f a _|_ = _|_ ==> fold1' f xs = fold1 f xs@
--
-- @fold1' f@ is /unambiguous/ iff @f@ is fold-commutative.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
fold1' :: (a -> a -> a) -> s a -> a
-- | Combine all the elements of a sequence into a single value,
-- given a combining function and an initial value. The function
-- is applied with right nesting.
--
-- > foldr (%) c <x0,...,xn-1> = x0 % (x1 % ( ... % (xn-1 % c)))
--
-- /Axioms:/
--
-- * @foldr f c empty = c@
--
-- * @foldr f c (lcons x xs) = f x (foldr f c xs)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
foldr :: (a -> b -> b) -> b -> s a -> b
-- | Strict variant of 'foldr'.
--
-- /Axioms:/
--
-- * @forall a. f a _|_ = _|_ ==> foldr f x xs = foldr' f x xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
foldr' :: (a -> b -> b) -> b -> s a -> b
-- | Combine all the elements of a sequence into a single value,
-- given a combining function and an initial value. The function
-- is applied with left nesting.
--
-- > foldl (%) c <x0,...,xn-1> = (((c % x0) % x1) % ... ) % xn-1
--
-- /Axioms:/
--
-- * @foldl f c empty = c@
--
-- * @foldl f c (lcons x xs) = foldl f (f c x) xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
foldl :: (b -> a -> b) -> b -> s a -> b
-- | Strict variant of 'foldl'.
--
-- /Axioms:/
--
-- * forall a. f _|_ a = _|_ ==> foldl f z xs = foldl' f z xs
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
foldl' :: (b -> a -> b) -> b -> s a -> b
-- | Combine all the elements of a non-empty sequence into a
-- single value, given a combining function. The function
-- is applied with right nesting. Signals an error if the
-- sequence is empty.
--
-- > foldr1 (+) <x0,...,xn-1>
-- > | n==0 = error "ModuleName.foldr1: empty sequence"
-- > | n>0 = x0 + (x1 + ... + xn-1)
--
-- /Axioms:/
--
-- * @foldr1 f empty = undefined@
--
-- * @foldr1 f (rcons x xs) = foldr f x xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
foldr1 :: (a -> a -> a) -> s a -> a
-- | Strict variant of 'foldr1'.
--
-- /Axioms:/
--
-- * forall a. f a _|_ = _|_ ==> foldr1 f xs = foldr1' f xs
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
foldr1' :: (a -> a -> a) -> s a -> a
-- | Combine all the elements of a non-empty sequence into
-- a single value, given a combining function. The function
-- is applied with left nesting. Signals an error if the
-- sequence is empty.
--
-- > foldl1 (+) <x0,...,xn-1>
-- > | n==0 = error "ModuleName.foldl1: empty sequence"
-- > | n>0 = (x0 + x1) + ... + xn-1
--
-- /Axioms:/
--
-- * @foldl1 f empty = undefined@
--
-- * @foldl1 f (lcons x xs) = foldl f x xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
foldl1 :: (a -> a -> a) -> s a -> a
-- | Strict variant of 'foldl1'.
--
-- /Axioms:/
--
-- * forall a. f _|_ a = _|_ ==> foldl1 f xs = foldl1' f xs
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
foldl1' :: (a -> a -> a) -> s a -> a
-- | See 'reduce1' for additional notes.
--
-- > reducer f x xs = reduce1 f (cons x xs)
--
-- /Axioms:/
--
-- * @reducer f c xs = foldr f c xs@ for associative @f@
--
-- @reducer f@ is unambiguous iff @f@ is an associative function.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
reducer :: (a -> a -> a) -> a -> s a -> a
-- | Strict variant of 'reducer'.
--
-- See 'reduce1' for additional notes.
--
-- /Axioms:/
--
-- * @forall a. f a _|_ = _|_ && forall a. f _|_ a = _|_ ==>
-- reducer f x xs = reducer' f x xs@
--
-- @reducer' f@ is unambiguous iff @f@ is an associative function.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
reducer' :: (a -> a -> a) -> a -> s a -> a
-- | See 'reduce1' for additional notes.
--
-- > reducel f x xs = reduce1 f (rcons x xs)
--
-- /Axioms:/
--
-- * @reducel f c xs = foldl f c xs@ for associative @f@
--
-- @reducel f@ is unambiguous iff @f@ is an associative function.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
reducel :: (a -> a -> a) -> a -> s a -> a
-- | Strict variant of 'reducel'.
--
-- See 'reduce1' for additional notes.
--
-- /Axioms:/
--
-- * @forall a. f a _|_ = _|_ && forall a. f _|_ a = _|_ ==>
-- reducel f x xs = reducel' f x xs@
--
-- @reducel' f@ is unambiguous iff @f@ is an associative function.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
reducel' :: (a -> a -> a) -> a -> s a -> a
-- | A reduce is similar to a fold, but combines elements in a balanced fashion.
-- The combining function should usually be associative. If the combining
-- function is associative, the various reduce functions yield the same
-- results as the corresponding folds.
--
-- What is meant by \"in a balanced fashion\"? We mean that
-- @reduce1 (%) \<x0,x1,...,xn-1>@ equals some complete parenthesization of
-- @x0 % x1 % ... % xn-1@ such that the nesting depth of parentheses
-- is @O( log n )@. The precise shape of this parenthesization is
-- unspecified.
--
-- > reduce1 f <x> = x
-- > reduce1 f <x0,...,xn-1> =
-- > f (reduce1 f <x0,...,xi>) (reduce1 f <xi+1,...,xn-1>)
--
-- for some @i@ such that @ 0 \<= i && i \< n-1 @
--
-- Although the exact value of i is unspecified it tends toward @n\/2@
-- so that the depth of calls to @f@ is at most logarithmic.
--
-- Note that @reduce@* are some of the only sequence operations for which
-- different implementations are permitted to yield different answers. Also
-- note that a single implementation may choose different parenthisizations
-- for different sequences, even if they are the same length. This will
-- typically happen when the sequences were constructed differently.
--
-- The canonical applications of the reduce functions are algorithms like
-- merge sort where:
--
-- > mergesort xs = reducer merge empty (map singleton xs)
--
--
-- /Axioms:/
--
-- * @reduce1 f empty = undefined@
--
-- * @reduce1 f xs = foldr1 f xs = foldl1 f xs@ for associative @f@
--
-- @reduce1 f@ is unambiguous iff @f@ is an associative function.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
reduce1 :: (a -> a -> a) -> s a -> a
-- | Strict variant of 'reduce1'.
--
-- /Axioms:/
--
-- * @forall a. f a _|_ = _|_ && forall a. f _|_ a = _|_ ==>
-- reduce1 f xs = reduce1' f xs@
--
-- @reduce1' f@ is unambiguous iff @f@ is an associative function.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
reduce1' :: (a -> a -> a) -> s a -> a
-- | Extract a prefix of length @i@ from the sequence. Return
-- 'empty' if @i@ is negative, or the entire sequence if @i@
-- is too large.
--
-- > take i xs = fst (splitAt i xs)
--
-- /Axioms:/
--
-- * @i \< 0 ==> take i xs = empty@
--
-- * @i > size xs ==> take i xs = xs@
--
-- * @size xs == i ==> take i (append xs ys) = xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( i )@
take :: Int -> s a -> s a
-- | Delete a prefix of length @i@ from a sequence. Return
-- the entire sequence if @i@ is negative, or 'empty' if
-- @i@ is too large.
--
-- > drop i xs = snd (splitAt i xs)
--
-- /Axioms:/
--
-- * @i \< 0 ==> drop i xs = xs@
--
-- * @i > size xs ==> drop i xs = empty@
--
-- * @size xs == i ==> drop i (append xs ys) = ys@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( i )@
drop :: Int -> s a -> s a
-- | Split a sequence into a prefix of length @i@
-- and the remaining sequence. Behaves the same
-- as the corresponding calls to 'take' and 'drop'
-- if @i@ is negative or too large.
--
-- > splitAt i xs
-- > | i < 0 = (<> , <x0,...,xn-1>)
-- > | i < n = (<x0,...,xi-1>, <xi,...,xn-1>)
-- > | i >= n = (<x0,...,xn-1>, <> )
--
-- /Axioms:/
--
-- * @splitAt i xs = (take i xs,drop i xs)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( i )@
splitAt :: Int -> s a -> (s a, s a)
-- | Extract a subsequence from a sequence. The integer
-- arguments are \"start index\" and \"length\" NOT
-- \"start index\" and \"end index\". Behaves the same
-- as the corresponding calls to 'take' and 'drop' if the
-- start index or length are negative or too large.
--
-- > subseq i len xs = take len (drop i xs)
--
-- /Axioms:/
--
-- * @subseq i len xs = take len (drop i xs)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( i + len )@
subseq :: Int -> Int -> s a -> s a
-- | Extract the elements of a sequence that satisfy the
-- given predicate, retaining the relative ordering of
-- elements from the original sequence.
--
-- > filter p xs = foldr pcons empty xs
-- > where pcons x xs = if p x then cons x xs else xs
--
-- /Axioms:/
--
-- * @filter p empty = empty@
--
-- * @filter p (lcons x xs) = if p x
-- then lcons x (filter p xs)
-- else filter p xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @p@
filter :: (a -> Bool) -> s a -> s a
-- | Separate the elements of a sequence into those that
-- satisfy the given predicate and those that do not,
-- retaining the relative ordering of elements from the
-- original sequence.
--
-- > partition p xs = (filter p xs, filter (not . p) xs)
--
-- /Axioms:/
--
-- * @partition p xs = (filter p xs, filter (not . p) xs)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @p@
partition :: (a -> Bool) -> s a -> (s a, s a)
-- | Extract the maximal prefix of elements satisfying the
-- given predicate.
--
-- > takeWhile p xs = fst (splitWhile p xs)
--
-- /Axioms:/
--
-- * @takeWhile p empty = empty@
--
-- * @takeWhile p (lcons x xs) = if p x
-- then lcons x (takeWhile p xs)
-- else empty@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @p@
takeWhile :: (a -> Bool) -> s a -> s a
-- | Delete the maximal prefix of elements satisfying the
-- given predicate.
--
-- > dropWhile p xs = snd (splitWhile p xs)
--
-- /Axioms:/
--
-- * @dropWhile p empty = empty@
--
-- * @dropWhile p (lcons x xs) = if p x
-- then dropWhile p xs
-- else lcons x xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @p@
dropWhile :: (a -> Bool) -> s a -> s a
-- | Split a sequence into the maximal prefix of elements
-- satisfying the given predicate, and the remaining sequence.
--
-- > splitWhile p <x0,...,xn-1> = (<x0,...,xi-1>, <xi,...,xn-1>)
-- > where i = min j such that p xj (or n if no such j)
--
-- /Axioms:/
--
-- * @splitWhile p xs = (takeWhile p xs,dropWhile p xs)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @p@
splitWhile :: (a -> Bool) -> s a -> (s a, s a)
-- | Test whether an index is valid for the given sequence. All indexes
-- are 0 based.
--
-- > inBounds i <x0,...,xn-1> = (0 <= i && i < n)
--
-- /Axioms:/
--
-- * @inBounds i xs = (0 \<= i && i \< size xs)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( i )@
inBounds :: Int -> s a -> Bool
-- | Return the element at the given index. All indexes are 0 based.
-- Signals error if the index out of bounds.
--
-- > lookup i xs@<x0,...,xn-1>
-- > | inBounds i xs = xi
-- > | otherwise = error "ModuleName.lookup: index out of bounds"
--
-- /Axioms:/
--
-- * @not (inBounds i xs) ==> lookup i xs = undefined@
--
-- * @size xs == i ==> lookup i (append xs (lcons x ys)) = x@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( i )@
lookup :: Int -> s a -> a
-- | Return the element at the given index. All indexes are 0 based.
-- Calls 'fail' if the index is out of bounds.
--
-- > lookupM i xs@<x0,...,xn-1>
-- > | inBounds i xs = Just xi
-- > | otherwise = Nothing
--
-- /Axioms:/
--
-- * @not (inBounds i xs) ==> lookupM i xs = fail@
--
-- * @size xs == i ==> lookupM i (append xs (lcons x ys)) = return x@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( i )@
lookupM :: (Fail.MonadFail m) => Int -> s a -> m a
-- | Return the element at the given index, or the
-- default argument if the index is out of bounds. All indexes are
-- 0 based.
--
-- > lookupWithDefault d i xs@<x0,...,xn-1>
-- > | inBounds i xs = xi
-- > | otherwise = d
--
-- /Axioms:/
--
-- * @not (inBounds i xs) ==> lookupWithDefault d i xs = d@
--
-- * @size xs == i ==> lookupWithDefault d i (append xs (lcons x ys)) = x@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( i )@
lookupWithDefault :: a -> Int -> s a -> a
-- | Replace the element at the given index, or return
-- the original sequence if the index is out of bounds.
-- All indexes are 0 based.
--
-- > update i y xs@<x0,...,xn-1>
-- > | inBounds i xs = <x0,...xi-1,y,xi+1,...,xn-1>
-- > | otherwise = xs
--
-- /Axioms:/
--
-- * @not (inBounds i xs) ==> update i y xs = xs@
--
-- * @size xs == i ==> update i y (append xs (lcons x ys)) =
-- append xs (lcons y ys)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( i )@
update :: Int -> a -> s a -> s a
-- | Apply a function to the element at the given index, or
-- return the original sequence if the index is out of bounds.
-- All indexes are 0 based.
--
-- > adjust f i xs@<x0,...,xn-1>
-- > | inBounds i xs = <x0,...xi-1,f xi,xi+1,...,xn-1>
-- > | otherwise = xs
--
-- /Axioms:/
--
-- * @not (inBounds i xs) ==> adjust f i xs = xs@
--
-- * @size xs == i ==> adjust f i (append xs (lcons x ys)) =
-- append xs (cons (f x) ys)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( i + t )@
-- where @t@ is the running time of @f@
adjust :: (a -> a) -> Int -> s a -> s a -- map a single element
-- | Like 'map', but include the index with each element.
-- All indexes are 0 based.
--
-- > mapWithIndex f <x0,...,xn-1> = <f 0 x0,...,f (n-1) xn-1>
--
-- /Axioms:/
--
-- * @mapWithIndex f empty = empty@
--
-- * @mapWithIndex f (rcons x xs) = rcons (f (size xs) x) (mapWithIndex f xs)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
mapWithIndex :: (Int -> a -> b) -> s a -> s b
-- | Like 'foldr', but include the index with each element.
-- All indexes are 0 based.
--
-- > foldrWithIndex f c <x0,...,xn-1> =
-- > f 0 x0 (f 1 x1 (... (f (n-1) xn-1 c)))
--
-- /Axioms:/
--
-- * @foldrWithIndex f c empty = c@
--
-- * @foldrWithIndex f c (rcons x xs) =
-- foldrWithIndex f (f (size xs) x c) xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
foldrWithIndex :: (Int -> a -> b -> b) -> b -> s a -> b
-- | Strict variant of 'foldrWithIndex'.
--
-- /Axioms:/
--
-- * @forall i a. f i a _|_ = _|_ ==> foldrWithIndex f x xs =
-- foldrWithIndex' f x xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
foldrWithIndex' :: (Int -> a -> b -> b) -> b -> s a -> b
-- | Like 'foldl', but include the index with each element.
-- All indexes are 0 based.
--
-- > foldlWithIndex f c <x0,...,xn-1> =
-- > f (...(f (f c 0 x0) 1 x1)...) (n-1) xn-1)
--
-- /Axioms:/
--
-- * @foldlWithIndex f c empty = c@
--
-- * @foldlWithIndex f c (rcons x xs) =
-- f (foldlWithIndex f c xs) (size xs) x@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
foldlWithIndex :: (b -> Int -> a -> b) -> b -> s a -> b
-- | Strict variant of 'foldlWithIndex'.
--
-- /Axioms:/
--
-- * @forall i a. f _|_ i a = _|_ ==> foldlWithIndex f x xs =
-- foldlWithIndex' f x xs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the running time of @f@
foldlWithIndex' :: (b -> Int -> a -> b) -> b -> s a -> b
-- | Combine two sequences into a sequence of pairs. If the
-- sequences are different lengths, the excess elements of the
-- longer sequence is discarded.
--
-- > zip <x0,...,xn-1> <y0,...,ym-1> = <(x0,y0),...,(xj-1,yj-1)>
-- > where j = min {n,m}
--
-- /Axioms:/
--
-- * @zip xs ys = zipWith (,) xs ys@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( min( n1, n2 ) )@
zip :: s a -> s b -> s (a,b)
-- | Like 'zip', but combines three sequences into triples.
--
-- > zip3 <x0,...,xn-1> <y0,...,ym-1> <z0,...,zk-1> =
-- > <(x0,y0,z0),...,(xj-1,yj-1,zj-1)>
-- > where j = min {n,m,k}
--
-- /Axioms:/
--
-- * @zip3 xs ys zs = zipWith3 (,,) xs ys zs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( min( n1, n2, n3 ) )@
zip3 :: s a -> s b -> s c -> s (a,b,c)
-- | Combine two sequences into a single sequence by mapping
-- a combining function across corresponding elements. If
-- the sequences are of different lengths, the excess elements
-- of the longer sequence are discarded.
--
-- > zipWith f xs ys = map (uncurry f) (zip xs ys)
--
-- /Axioms:/
--
-- * @zipWith f (lcons x xs) (lcons y ys) =
-- lcons (f x y) (zipWith f xs ys)@
--
-- * @(null xs || null ys) ==> zipWith xs ys = empty@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * min( n1, n2 ) )@
-- where @t@ is the running time of @f@
zipWith :: (a -> b -> c) -> s a -> s b -> s c
-- | Like 'zipWith' but for a three-place function and three
-- sequences.
--
-- > zipWith3 f xs ys zs = map (uncurry f) (zip3 xs ys zs)
--
-- /Axioms:/
--
-- * @zipWith3 (lcons x xs) (lcons y ys) (lcons z zs) =
-- lcons (f x y z) (zipWith3 f xs ys zs)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * min( n1, n2, n3 ) )@
-- where @t@ is the running time of @f@
zipWith3 :: (a -> b -> c -> d) -> s a -> s b -> s c -> s d
-- | Transpose a sequence of pairs into a pair of sequences.
--
-- > unzip xs = (map fst xs, map snd xs)
--
-- /Axioms:/
--
-- * @unzip xys = unzipWith fst snd xys@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( n )@
unzip :: s (a,b) -> (s a, s b)
-- | Transpose a sequence of triples into a triple of sequences
--
-- > unzip3 xs = (map fst3 xs, map snd3 xs, map thd3 xs)
-- > where fst3 (x,y,z) = x
-- > snd3 (x,y,z) = y
-- > thd3 (x,y,z) = z
--
-- /Axioms:/
--
-- * @unzip3 xyzs = unzipWith3 fst3 snd3 thd3 xyzs@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( n )@
unzip3 :: s (a,b,c) -> (s a, s b, s c)
-- | Map two functions across every element of a sequence,
-- yielding a pair of sequences
--
-- > unzipWith f g xs = (map f xs, map g xs)
--
-- /Axioms:/
--
-- * @unzipWith f g xs = (map f xs, map g xs)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the maximum running time
-- of @f@ and @g@
unzipWith :: (a -> b) -> (a -> c) -> s a -> (s b, s c)
-- | Map three functions across every element of a sequence,
-- yielding a triple of sequences.
--
-- > unzipWith3 f g h xs = (map f xs, map g xs, map h xs)
--
-- /Axioms:/
--
-- * @unzipWith3 f g h xs = (map f xs,map g xs,map h xs)@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( t * n )@
-- where @t@ is the maximum running time
-- of @f@, @g@, and @h@
unzipWith3 :: (a -> b) -> (a -> c) -> (a -> d) -> s a -> (s b, s c, s d)
-- | Semanticly, this function is a partial identity function. If the
-- datastructure is infinite in size or contains exceptions or non-termination
-- in the structure itself, then @strict@ will result in bottom. Operationally,
-- this function walks the datastructure forcing any closures. Elements contained
-- in the sequence are /not/ forced.
--
-- /Axioms:/
--
-- * @strict xs = xs@ OR @strict xs = _|_@
--
-- This function is always /unambiguous/.
--
-- Default running time: @O( n )@
strict :: s a -> s a
-- | Similar to 'strict', this function walks the datastructure forcing closures.
-- However, @strictWith@ will additionally apply the given function to the
-- sequence elements, force the result using @seq@, and then ignore it.
-- This function can be used to perform various levels of forcing on the
-- sequence elements. In particular:
--
-- > strictWith id xs
--
-- will force the spine of the datastructure and reduce each element to WHNF.
--
-- /Axioms:/
--
-- * forall @f :: a -> b@, @strictWith f xs = xs@ OR @strictWith f xs = _|_@
--
-- This function is always /unambiguous/.
--
-- Default running time: unbounded (forcing element closures can take arbitrarily long)
strictWith :: (a -> b) -> s a -> s a
-- | A method to facilitate unit testing. Returns 'True' if the structural
-- invariants of the implementation hold for the given sequence. If
-- this function returns 'False', it represents a bug in the implementation.
structuralInvariant :: s a -> Bool
-- | The name of the module implementing s.
instanceName :: s a -> String
----------------------------------------------------------------------
-- Other possible operations not currently included
{-
insertAt :: Int -> a -> s a -> s a
-- adds to front or rear if index out of bounds
--
-- insertAt i y xs@<x0,...,xn-1>
-- | i < 0 = cons y xs
-- | i >= n = snoc xs y
-- | otherwise = <x0,...,xi-1,y,xi,...,xn-1>
deleteAt :: Int -> s a -> s a
-- returns original sequence if index out of bounds
--
-- deleteAt i xs@<x0,...,xn-1>
-- | i < 0 = xs
-- | i >= n = xs
-- | otherwise = <x0,...,xi-1,xi+1,...,xn-1>
insertAt i x s = append before (cons x after)
where (before, after) = splitAt i s
deleteAt i s = if i < 0 then s else append before (ltail after)
where (before, after) = splitAt i s
-}