-- | -- 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 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 :: (Monad 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 :: (Monad 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 :: (Monad 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 :: (Monad 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 :: (Monad 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 :: (Monad 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 :: (Monad 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 arbitrairly 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 -}