!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~GHC, Hugs (MPTC and FD)stablerobdockins AT fastmail DOT fm Safe-Inferred>This class represents a quantity that can be measured. It is @ calculated by an associative function with a unit (hence the  Monoid; superclass, and by a function which gives the measurement E for an individual item. Some datastructures are able to speed up B the calculation of a measure by caching intermediate values of  the computation. 9This class represents hashable objects where the hash is  reversible.  #forall x :: a. unhash (hash x) == x Note that:  hash (unhash i) == i"does not necessarily hold because  is not necessarily  defined for all i, only for all i in the range of hash. ?This class represents hashable objects where the hash function  is unique1 (injective). There are no new methods, just a  stronger invariant: 0forall x,y :: a. (x == y) iff (hash x == hash y)6This class represents hashable objects. If obeys the  following invariant: 4forall x,y :: a. (x == y) implies (hash x == hash y)GHC, Hugs (MPTC and FD)stablerobdockins AT fastmail DOT fm Safe-InferredLThe 0 class defines an interface for datatypes which < implement sequences. A description for each function is  given below. 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) xsThis function is always  unambiguous. Default running time: O( 1 ) 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 ) Convert a list into a sequence  ( fromList [x0,...,xn-1] = <x0,...,xn-1> Axioms:  "fromList xs = foldr lcons empty xsThis function is always  unambiguous. Default running time: O( n ) Create a sequence containing n copies of the given element.  Return Q 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 = emptyThis function is always  unambiguous. Default running time: O( n ) >Separate a sequence into its first (leftmost) element and the  remaining sequence. Calls  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 ) (Return the first element of a sequence. . Signals an error if the sequence is empty. Axioms:  lhead empty = undefined lhead (lcons x xs) = xThis function is always  unambiguous. Default running time: O( 1 ) *Returns the first element of a sequence.  Calls  if the sequence is empty. Axioms:  lheadM empty = fail lheadM (lcons x xs) = return xThis function is always  unambiguous. Default running time: O( 1 ) *Delete the first element of the sequence. ' Signals error if sequence is empty. Axioms:  ltail empty = undefined ltail (lcons x xs) = xsThis function is always  unambiguous. Default running time: O( 1 ) *Delete the first element of the sequence.  Calls  if the sequence is empty. Axioms:  ltailM empty = fail ltailM (lcons x xs) = return xsThis function is always  unambiguous. Default running time: O( 1 ) >Separate a sequence into its last (rightmost) element and the  remaining sequence. Calls  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 ) 5Return the last (rightmost) element of the sequence. ' Signals error if sequence is empty. Axioms:  rhead empty = undefined rhead (rcons x xs) = xThis function is always  unambiguous. Default running time: O( n ) *Returns the last element of the sequence.  Calls  if the sequence is empty. Axioms:  rheadM empty = fail rheadM (rcons x xs) = return xThis function is always  unambiguous. Default running time: O( n ) 5Delete the last (rightmost) element of the sequence. . Signals an error if the sequence is empty. Axioms:  rtail empty = undefined rtail (rcons x xs) = xsThis function is always  unambiguous. Default running time: O( n ) 5Delete the last (rightmost) element of the sequence.  Calls  of the sequence is empty Axioms:  rtailM empty = fail rtailM (rcons x xs) = return xsThis function is always  unambiguous. Default running time: O( n ) Returns  if the sequence is empty and  otherwise.   null <x0,...,xn-1> = (n==0) Axioms:  null xs = (size xs == 0)This function is always  unambiguous. Default running time: O( 1 ) "Returns the length of a sequence.   size <x0,...,xn-1> = n Axioms:  size empty = 0 size (lcons x xs) = 1 + size xsThis function is always  unambiguous. Default running time: O( n ) Convert a sequence to a list.  & toList <x0,...,xn-1> = [x0,...,xn-1] Axioms:  toList empty = [] #toList (lcons x xs) = x : toList xsThis function is always  unambiguous. Default running time: O( n ) 8Flatten a sequence of sequences into a simple sequence.  % concat xss = foldr append empty xss Axioms:  #concat xss = foldr append empty xssThis 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.  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 ) 7Reverse a sequence onto the front of another sequence.  E reverseOnto <x0,...,xn-1> <y0,...,ym-1> = <xn-1,...,x0,y0,...,ym-1> Axioms:  *reverseOnto xs ys = append (reverse xs) ysThis function is always  unambiguous. Default running time: O( n1 ) <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 4f is fold-commutative ==> fold f = foldr f = foldl ffold f is  unambiguous iff f is fold-commutative. Default running type:  O( t * n )  where t is the running tome of f. A strict variant of . fold' is one of the few ambiguous  sequence functions. Axioms:  .forall a. f a _|_ = _|_ ==> fold f x xs = fold' f x xsfold f is  unambiguous iff f is fold-commutative. Default running type:  O( t * n )  where t is the running tome of f. 8Combine 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:  7f is fold-commutative ==> fold1 f = foldr1 f = foldl1 ffold1 f is  unambiguous iff f is fold-commutative. Default running type:  O( t * n )  where t is the running tome of f. A strict variant of . Axioms:  !forall a. f a _|_ = _|_ ==> fold1' f xs = fold1 f xsfold1' f is  unambiguous iff f is fold-commutative. Default running time:  O( t * n )  where t is the running time of f <Combine all the elements of a sequence into a single value, B 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 !Strict variant of  . Axioms:  0forall a. f a _|_ = _|_ ==> foldr f x xs = foldr' f x xsThis function is always  unambiguous. Default running time:  O( t * n )  where t is the running time of f "<Combine all the elements of a sequence into a single value, B 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) xsThis function is always  unambiguous. Default running time:  O( t * n )  where t is the running time of f #Strict variant of ". Axioms: 1 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 $8Combine 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> 6 | 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 xsThis function is always  unambiguous. Default running time:  O( t * n )  where t is the running time of f %Strict variant of $. Axioms: 1 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 &6Combine all the elements of a non-empty sequence into = a single value, given a combining function. The function 9 is applied with left nesting. Signals an error if the  sequence is empty.   foldl1 (+) <x0,...,xn-1> 5 | 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 xsThis function is always  unambiguous. Default running time:  O( t * n )  where t is the running time of f 'Strict variant of &. Axioms: 1 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 (See , 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 )Strict variant of (. See , for additional notes. Axioms:  forall a. f a _|_ = _|_ && forall a. f _|_ a = _|_ ==> " reducer f x xs = reducer' f x xsreducer' f is unambiguous iff f is an associative function. Default running time:  O( t * n )  where t is the running time of f *See , 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 +Strict variant of *. See , for additional notes. Axioms:  forall a. f a _|_ = _|_ && forall a. f _|_ a = _|_ ==> " reducel f x xs = reducel' f x xsreducel' f is unambiguous iff f is an associative function. Default running time:  O( t * n )  where t is the running time of f ,LA reduce is similar to a fold, but combines elements in a balanced fashion. K The combining function should usually be associative. If the combining H 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 )1. 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 reduce5* are some of the only sequence operations for which M different implementations are permitted to yield different answers. Also L note that a single implementation may choose different parenthisizations I for different sequences, even if they are the same length. This will E typically happen when the sequences were constructed differently. GThe canonical applications of the reduce functions are algorithms like  merge sort where:  7 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 -Strict variant of ,. Axioms:  forall a. f a _|_ = _|_ && forall a. f _|_ a = _|_ ==>  reduce1 f xs = reduce1' f xsreduce1' f is unambiguous iff f is an associative function. Default running time:  O( t * n )  where t is the running time of f .Extract a prefix of length i from the sequence. Return  Q 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) = xsThis function is always  unambiguous. Default running time: O( i ) /Delete a prefix of length i from a sequence. Return  the entire sequence if i is negative, or Q 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) = ysThis function is always  unambiguous. Default running time: O( i ) 0)Split a sequence into a prefix of length i 1 and the remaining sequence. Behaves the same ! as the corresponding calls to . and /  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 ) 14Extract 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 . and / if the 4 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 ) 24Extract the elements of a sequence that satisfy the 7 given predicate, retaining the relative ordering of ( elements from the original sequence.  $ filter p xs = foldr pcons empty xs 7 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 xsThis function is always  unambiguous. Default running time:  O( t * n )  where t is the running time of p 34Separate the elements of a sequence into those that 6 satisfy the given predicate and those that do not, 8 retaining the relative ordering of elements from the  original sequence.  5 partition p xs = (filter p xs, filter (not . p) xs) Axioms:  3partition 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 46Extract 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 emptyThis function is always  unambiguous. Default running time:  O( t * n )  where t is the running time of p 55Delete 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 xsThis function is always  unambiguous. Default running time:  O( t * n )  where t is the running time of p 65Split 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>) 6 where i = min j such that p xj (or n if no such j) Axioms:  1splitWhile 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 7CTest 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 ) 8AReturn 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:  0not (inBounds i xs) ==> lookup i xs = undefined 6size xs == i ==> lookup i (append xs (lcons x ys)) = xThis function is always  unambiguous. Default running time: O( i ) 9AReturn the element at the given index. All indexes are 0 based.  Calls  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 xThis function is always  unambiguous. Default running time: O( i ) :.Return the element at the given index, or the D 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:  4not (inBounds i xs) ==> lookupWithDefault d i xs = d Csize xs == i ==> lookupWithDefault d i (append xs (lcons x ys)) = xThis function is always  unambiguous. Default running time: O( i ) ;2Replace the element at the given index, or return 8 the original sequence if the index is out of bounds.  All indexes are 0 based.   update i y xs@<x0,...,xn-1> 2 | inBounds i xs = <x0,...xi-1,y,xi+1,...,xn-1>  | otherwise = xs Axioms:  *not (inBounds i xs) ==> update i y xs = xs 7size 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 ) <7Apply 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> 5 | inBounds i xs = <x0,...xi-1,f xi,xi+1,...,xn-1>  | otherwise = xs Axioms:  *not (inBounds i xs) ==> adjust f i xs = xs 7size 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 =Like N+, 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 GmapWithIndex 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 >Like  +, 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) xsThis function is always  unambiguous. Default running time:  O( t * n )  where t is the running time of f ?Strict variant of >. Axioms:  9forall i a. f i a _|_ = _|_ ==> foldrWithIndex f x xs =  foldrWithIndex' f x xsThis function is always  unambiguous. Default running time:  O( t * n )  where t is the running time of f @Like "+, 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) xThis function is always  unambiguous. Default running time:  O( t * n )  where t is the running time of f AStrict variant of @. Axioms:  9forall i a. f _|_ i a = _|_ ==> foldlWithIndex f x xs =  foldlWithIndex' f x xsThis function is always  unambiguous. Default running time:  O( t * n )  where t is the running time of f B8Combine 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 ysThis function is always  unambiguous. Default running time: O( min( n1, n2 ) ) CLike B-, but combines three sequences into triples.  3 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 zsThis function is always  unambiguous. Default running time: O( min( n1, n2, n3 ) ) D8Combine 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 = emptyThis function is always  unambiguous. Default running time: O( t * min( n1, n2 ) )  where t is the running time of f ELike D* but for a three-place function and three  sequences.  7 zipWith3 f xs ys zs = map (uncurry f) (zip3 xs ys zs) Axioms:  2zipWith3 (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 F8Transpose a sequence of pairs into a pair of sequences.  % unzip xs = (map fst xs, map snd xs) Axioms:  !unzip xys = unzipWith fst snd xysThis function is always  unambiguous. Default running time: O( n ) G;Transpose a sequence of triples into a triple of sequences  5 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 xyzsThis function is always  unambiguous. Default running time: O( n ) H6Map 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 I8Map three functions across every element of a sequence, # yielding a triple of sequences.  6 unzipWith3 f g h xs = (map f xs, map g xs, map h xs) Axioms:  2unzipWith3 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 JBSemanticly, this function is a partial identity function. If the O datastructure is infinite in size or contains exceptions or non-termination ! in the structure itself, then strict( will result in bottom. Operationally, S 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 ) K Similar to J:, this function walks the datastructure forcing closures.  However,  strictWith3 will additionally apply the given function to the - sequence elements, force the result using seq, and then ignore it. I This function can be used to perform various levels of forcing on the & sequence elements. In particular:   strictWith id xs Kwill 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. UDefault running time: unbounded (forcing element closures can take arbitrairly long) L.A method to facilitate unit testing. Returns  if the structural E invariants of the implementation hold for the given sequence. If  this function returns -, it represents a bug in the implementation. M'The name of the module implementing s. N,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 O+Create a singleton sequence. Identical to return  from Monad.   singleton x = <x> Axioms:  +singleton x = lcons x empty = rcons x emptyThis function is always  unambiguous. Default running time: O( 1 ) P5Apply a sequence-producing function to every element ) of a sequence and flatten the result. P  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 Q"The empty sequence. Identical to mzero  from  MonadPlus.   empty = <> This function is always  unambiguous. Default running time: O( 1 ) R9Append two sequence, with the first argument on the left 7 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 xsThis function is always  unambiguous. Default running time: O( n1 ) L  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRL  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRLNOPQR  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMF  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRGHC, Hugs (MPTC and FD)stablerobdockins AT fastmail DOT fm Safe-InferredMSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~LSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~LSUVWXYZ\[^]_a`cbdefghijklmnopqsrtuvwxyz{|}~TMSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~GHC, Hugs (MPTC and FD)stablerobdockins AT fastmail DOT fm Safe-InferredMJCollections with observable elements where the set property is maintained J and where additionally, there is an ordering relation on the elements. H This class introduces no new methods, and is simply an abbreviation  for the context: (OrdColl c a,Set c a)KCollections with observable elements where the set property is maintained; H that is, a set contains at most one element of the equivalence class  formed by the  instance on the elements. <WARNING: Each of the following \"With\" functions is unsafe. N The passed in combining functions are used to choose which element is kept L in the case of duplicates. They are required to satisfy the precondition L that, given two equal elements, they return a third element equal to the I other two. Usually, the combining function just returns its first or E second argument, but it can combine elements in non-trivial ways. JThe combining function should usually be associative. Where the function G involves a sequence of elements, the elements will be combined from 9 left-to-right, but with an unspecified associativity. For example, if  x == y == z,  then fromSeqWith (+) [x,y,z] equals either  single (x + (y + z))  or  single ((x + y) + z) Same as 8 but with a combining function to resolve duplicates. This function is  unambiguous under the "with" precondition > if the combining function is associative. Otherwise it is  ambiguous. Same as 6 but with a combining function to resolve duplicates. This function is  unambiguous under the "with" precondition. Same as 6 but with a combining function to resolve duplicates. This function is  unambiguous under the "with" precondition > if the combining function is associative. Otherwise it is  ambiguous. Left biased union. Axioms:  unionl = unionWith (\ x y -> x)This function is always  unambiguous. Right biased union. Axioms:  unionr = unionWith (\ x y -> y)This function is always  unambiguous. Same as ;, but with a combining function to resolve duplicates. This function is  unambiguous under the "with" precondition. Same as 7, but with a combining function to resolve duplicates. This function is  unambiguous under the "with" precondition > if the combining function is associative. Otherwise it is  ambiguous. Same as 7, but with a combining function to resolve duplicates. This function is  unambiguous under the "with" precondition. ECollections with observable elements where the elements additionally I have an ordering relation. See the module documentation for comments  on observability. <Return the minimum element in the collection, together with ? the collection without that element. If there are multiple E copies of the minimum element, it is unspecified which is chosen.  Note that , , and  may make different  choices. Calls  if the collection is empty. This function is  ambiguous( at bag types, if more than one minimum 0 element exists in the bag. Otherwise, it is  unambiguous. EReturn the minimum element in the collection. If there are multiple E copies of the minimum element, it is unspecified which is chosen.  Note that , , and  may make different : choices. Signals an error if the collection is empty. This function is  ambiguous( at bag types, if more than one minimum 0 element exists in the bag. Otherwise, it is  unambiguous. =Return the maximum element in the collection, together with ? the collection without that element. If there are multiple E copies of the maximum element, it is unspecified which is chosen.  Note that ,  and  may make different  choices. Calls  if the collection is empty. This function is  ambiguous( at bag types, if more than one maximum 0 element exists in the bag. Otherwise, it is  unambiguous. EReturn the maximum element in the collection. If there are multiple E copies of the maximum element, it is unspecified which is chosen.  Note that ,  and  may make different : choices. Signals an error if the collection is empty. This function is  ambiguous( at bag types, if more than one maximum 0 element exists in the bag. Otherwise, it is  unambiguous. <Fold across the elements in non-decreasing order with right C associativity. (For sets, this will always be increasing order) This function is  unambiguous if the combining function is 8 fold-commutative, at all set types, and at bag types A where no two equivalent elements exist in the bag. Otherwise  it is  ambiguous. A strict variant of . This function is  unambiguous if the combining function is 8 fold-commutative, at all set types, and at bag types A where no two equivalent elements exist in the bag. Otherwise  it is  ambiguous. ;Fold across the elements in non-decreasing order with left C associativity. (For sets, this will always be increasing order) This function is  unambiguous if the combining function is 8 fold-commutative, at all set types, and at bag types A where no two equivalent elements exist in the bag. Otherwise  it is  ambiguous. A strict variant of . This function is  unambiguous if the combining function is 8 fold-commutative, at all set types, and at bag types A where no two equivalent elements exist in the bag. Otherwise  it is  ambiguous. <Fold across the elements in non-decreasing order with right A associativity, or signal an error if the collection is empty. 4 (For sets, this will always be increasing order) This function is  unambiguous if the combining function is 8 fold-commutative, at all set types, and at bag types A where no two equivalent elements exist in the bag. Otherwise  it is  ambiguous. A strict variant of . This function is  unambiguous if the combining function is 8 fold-commutative, at all set types, and at bag types A where no two equivalent elements exist in the bag. Otherwise  it is  ambiguous. ;Fold across the elements in non-decreasing order with left A associativity, or signal an error if the collection is empty. 4 (For sets, this will always be increasing order) This function is  unambiguous if the combining function is 8 fold-commutative, at all set types, and at bag types A where no two equivalent elements exist in the bag. Otherwise  it is  ambiguous. A strict variant of . This function is  unambiguous if the combining function is 8 fold-commutative, at all set types, and at bag types A where no two equivalent elements exist in the bag. Otherwise  it is  ambiguous. GList the elements in non-decreasing order. (For sets, this will always  be increasing order) At set types, this function is  unambiguous. At bag types, it  is  unambiguous1 if no two equivalent elements exist in the bag;  otherwise it is  ambiguous. DMap a monotonic function across all elements of a collection. The ? function is required to satisfy the following precondition:  ! forall x y. x < y ==> f x < f y This function is  unambiguous, under the precondition. HCollections with observable elements. See the module documentation for  comments on observability. =List the elements of the collection in an unspecified order. This function is  ambiguous" iff the collection contains more  than one element. ?Lookup one element equal to the given element. If no elements C exist in the collection equal to the given element, an error is C signaled. If multiple copies of the given element exist in the 4 collection, it is unspecified which is returned. This function is  ambiguous" at bag types, when more than one B element equivalent to the given item is in the bag. Otherwise  it is  unambiguous. ?Lookup one element equal to the given element. If no elements 7 exist in the collection equal to the given element,  is called. G If multiple copies of the given element exist in the collection, it % is unspecified which is returned. This function is  ambiguous" at bag types, when more than one B element equivalent to the given item is in the bag. Otherwise  it is  unambiguous. EReturn a sequence containing all elements in the collection equal to . the given element in an unspecified order. This function is  ambiguous" at bag types, when more than one B element equivalent to the given item is in the bag. Otherwise  it is  unambiguous. JLookup one element equal to the (second) given element in the collection. K If no elements exist in the collection equal to the given element, then $ the default element is returned. This function is  ambiguous" at bag types, when more than one B element equivalent to the given item is in the bag. Otherwise  it is  unambiguous. DFold over all the elements in a collection in an unspecified order. fold f is  unambiguous iff f is fold-commutative. A strict variant of . fold' f is  unambiguous iff f is fold-commutative. DFold over all the elements in a collection in an unspecified order. 4 An error is signaled if the collection is empty. fold1 f is  unambiguous iff f is fold-commutative. A strict variant of . fold1' f is  unambiguous iff f is fold-commutative. 2Remove all elements not satisfying the predicate. This function is always  unambiguous. ?Returns two collections, the first containing all the elements ? satisfying the predicate, and the second containing all the * elements not satisfying the predicate. This function is always  unambiguous.  Similar to :, this function walks the datastructure forcing closures.  However,  strictWith3 will additionally apply the given function to the / collection elements, force the result using seq, and then ignore it. I This function can be used to perform various levels of forcing on the & sequence elements. In particular:   strictWith id xs Kwill force the spine of the datastructure and reduce each element to WHNF. This function is always  unambiguous. 8Sets where the elements also have an ordering relation. B This class contains no methods; it is only an abbreviation for  the context (OrdCollX c a,SetX c a). BA collection where the set property is maintained; that is, a set G contains at most one element of the equivalence class formed by the   instance on the elements. AComputes the intersection of two sets. It is unspecified which ; element is kept when equal elements appear in each set. This function is  ambiguous%, except when the sets are disjoint. >Computes the difference of two sets; that is, all elements in 2 the first set which are not in the second set. This function is always  unambiguous. EComputes the symmetric difference of two sets; that is, all elements 1 which appear in exactily one of the two sets. This function is always  unambiguous. ATest whether the first set is a proper subset of the second set; F that is, if every element in the first set is also a member of the D second set AND there exists some element in the second set which  is not present in the first. This function is always  unambiguous. FTest whether the first set is a subset of the second set; that is, if F every element in the first set is also a member of the second set. This function is always  unambiguous. >Collections for which the elements have an ordering relation. BDelete the minimum element from the collection. If there is more L than one minimum, it is unspecified which is deleted. If the collection , is empty, it will be returned unchanged. This function is  ambiguous' at bag types if more than one minimum / element exists in the bag. Otherwise it is  unambiguous. BDelete the maximum element from the collection. If there is more L than one maximum, it is unspecified which is deleted. If the collection , is empty, it will be returned unchanged. This function is  ambiguous' at bag types if more than one maximum / element exists in the bag. Otherwise it is  unambiguous. >Insert an element into a collection which is guaranteed to be  <=9 any existing elements in the collection. For sets, the # precondition is strengthened to <. This function is  unambiguous!, under the above preconditions. >Insert an element into a collection which is guaranteed to be  >=: any existing elements in the collection. For sets, the # precondition is strengthened to >. This function is  unambiguous!, under the above preconditions. >Convert a sequence in non-decreasing order into a collection. 7 For sets, the sequence must be in increasing order. This function is  unambiguous!, under the above preconditions. 7Union two collections where every element in the first  collection is <=) every element in the second collection. 2 For sets, this precondition is strengthened to <. This function is  unambiguous!, under the above preconditions. 'Extract the sub-collection of elements < the given element. Axioms:  filterLT x xs = filter (< x) xsThis function is always  unambiguous. 'Extract the sub-collection of elements <= the given element. Axioms:  filterLE x xs = filter (<= x) xsThis function is always  unambiguous. 'Extract the sub-collection of elements > the given element. Axioms:  filterGT x xs = filter (> x) xsThis function is always  unambiguous. 'Extract the sub-collection of elements >= the given element. Axioms:   filterGE x xs = filter (>= x) xsThis function is always  unambiguous. 'Split a collection into those elements < a given element and  those >=. Axioms:  partitionLT_GE xs = partition (<) xsThis function is always  unambiguous. 'Split a collection into those elements <= a given element and  those >. Axioms:  partitionLE_GT xs = partition (<=) xsThis function is always  unambiguous. 'Split a collection into those elements < a given element and  those >:. All elements equal to the given element are discarded. Axioms:  3partitionLT_GT x xs = (filterLT x xs,filterGT x xs)This function is always  unambiguous. AThis is the root class of the collection hierarchy. However, it F is perfectly adequate for many applications that use sets or bags. create a singleton collection This function is always  unambiguous. AConvert a sequence to a collection. For sets, it is unspecified 0 which element is kept in case of duplicates. This function is  ambiguous at set types if more than one 8 equivalent item is in the sequence. Otherwise it is  unambiguous. DMerge a sequence of collections. For sets, it is unspecified which . element is kept in the case of duplicates. This function is  ambiguous* at set types if the sets in the sequence . are not mutually disjoint. Otherwise it is  unambiguous. DInsert an element into a collection. For sets, if an equal element F is already in the set, the newly inserted element is kept, and the  old element is discarded. This function is always  unambiguous. <Insert a sequence of elements into a collection. For sets, G the behavior with regard to multiple equal elements is unspecified. This function is  ambiguous' at set types if the sequence contains I more than one equivalent item or an item which is already in the set.  Otherwise it is  unambiguous. CDelete a single occurrence of the given element from a collection. > For bags, it is unspecified which element will be deleted. This function is  ambiguous+ at bag types if more than one item exists = in the bag equivalent to the given item. Otherwise it is  unambiguous. BDelete all occurrences of an element from a collection. For sets " this operation is identical to . This function is always  unambiguous. >Delete a single occurrence of each of the given elements from C a collection. For bags, there may be multiple occurrences of a D given element in the collection, in which case it is unspecified  which is deleted. This function is  ambiguous$ at bag types if more than one item G exists in the bag equivalent to any item in the list and the number G of equivalent occurrences of that item in the sequence is less than : the number of occurrences in the bag. Otherwise it is  unambiguous. &Test whether the collection is empty. Axioms:  null xs = (size xs == 0)This function is always  unambiguous. 1Return the number of elements in the collection. This function is always  unambiguous. 5Test whether the given element is in the collection. Axioms:  member x xs = (count x xs > 0)This function is always  unambiguous. BCount how many copies of the given element are in the collection. - For sets, this will always return 0 or 1. This function is always  unambiguous. BSemanticly, this function is a partial identity function. If the O datastructure is infinite in size or contains exceptions or non-termination ! in the structure itself, then strict( will result in bottom. Operationally, H this function walks the datastructure forcing any closures. In many  collections, the collction "shape"& depends on the value of the elemnts; J in such cases, the values of the elements will be forced to the extent G necessary to force the structure of the collection, but no further. This function is always  unambiguous. .A method to facilitate unit testing. Returns  if the structural G invariants of the implementation hold for the given collection. If  this function returns ), it represents a bug; generally, either H the implementation itself is flawed, or an unsafe operation has been + used while violating the preconditions. $The name of the module implementing c %The empty collection. Equivalant to mempty from  the Monoid instance. This function is always  unambiguous. EMerge two collections. For sets, it is unspecified which element is 2 kept in the case of duplicates. Equivalant to mappend from the  Monoid instance. This function is  ambiguous, at set types if the sets are not disjoint.  Otherwise it is  unambiguous. Xdefault element element to lookup  collection XX  GHC, Hugs (MPTC and FD)stablerobdockins AT fastmail DOT fm Safe-InferredGApply a function across all the elements in a collection and transform  the collection type. IMap a partial function across all elements of a collection and transform  the collection type. EMap a monotonic function across all the elements of a collection and H transform the collection type. The function is required to satisfy  the following precondition: ! forall x y. x < y ==> f x < f y HMap a collection-producing function across all elements of a collection * and collect the results together using . GHC, Hugs (MPTC and FD)stablerobdockins AT fastmail DOT fm Safe-Inferredo=Finite maps with observable keys where the keys additionally E have an ordering relation. This class introduces no new methods. "Finite maps with observable keys. Same as E7, but with a combining function to resolve duplicates. I The combining function additionally takes the key. Which key is kept : and passed into the combining function is unspecified. This function is  unambiguous provided that the Eq instance on keys ( corresponds to indistinguishability. Same as F7, but with a combining function to resolve duplicates. D The combining function additionally takes the key. Which key is ? kept and passed into the combining function is unspecified. This function is  unambiguous provided that the Eq instance on keys ( corresponds to indistinguishability. Same as %, except that the combining function D additionally takes the key value for each binding. Which key is ? kept and passed into the combining function is unspecified. This function is  unambiguous provided the Eq instance on keys ( corresponds to indistinguishability. KAn associative collection with observable keys where the keys additionally  have an ordering relation. <Delete the binding with the minimum key from an associative @ collection and return the key, the element and the remaining " associative collection. Calls  if the associative collection I is empty. Which binding is chosen if there are multiple minimum keys  is unspecified. This function is  ambiguous+ at finite relation types if more than one ; minimum key exists in the relation. Furthermore, it is  ambiguous 6 with respect to the actual key observed unless the Eq instance on , keys corresponds to indistinguisability. GFind the binding with the minimum key in an associative collection and H return the key and the element. Signals an error if the associative G collection is empty. Which binding is chosen if there are multiple  minimum keys is unspecified. This function is  ambiguous+ at finite relation types if more than one ; minimum key exists in the relation. Furthermore, it is  ambiguous 6 with respect to the actual key observed unless the Eq instance on , keys corresponds to indistinguisability. <Delete the binding with the maximum key from an associative @ collection and return the key, the element and the remaining " associative collection. Calls  if the associative collection I is empty. Which binding is chosen if there are multiple maximum keys  is unspecified. This function is  ambiguous+ at finite relation types if more than one ; maximum key exists in the relation. Furthermore, it is  ambiguous 6 with respect to the actual key observed unless the Eq instance on , keys corresponds to indistinguisability. GFind the binding with the maximum key in an associative collection and H return the key and the element. Signals an error if the associative G collection is empty. Which binding is chosen if there are multiple  maximum keys is unspecified. This function is  ambiguous+ at finite relation types if more than one ; maximum key exists in the relation. Furthermore, it is  ambiguous 6 with respect to the actual key observed unless the Eq instance on , keys corresponds to indistinguisability. FFold over all bindings in an associative collection in non-decreasing E order by key with right associativity, given a combining function D and an initial value. For finite maps, the order is increasing. foldrWithKey f is  ambiguous at finite relation types if : the relation contains more than one equivalent key and  f# is not fold-commutative OR if the Eq instance on keys 0 does not correspond to indistingusihability. A strict variant of .  foldrWithKey' f is  ambiguous at finite relation types if : the relation contains more than one equivalent key and  f# is not fold-commutative OR if the Eq instance on keys > does not correspond to indistingusihability. Otherwise it  is  unambiguous. FFold over all bindings in an associative collection in non-decreasing D order by key with left associativity, given a combining function D and an initial value. For finite maps, the order is increasing. foldlWithKey f is  ambiguous at finite relation types if : the relation contains more than one equivalent key and  f# is not fold-commutative OR if the Eq instance on keys = does not correspond to indistingusihability. Otherwise it  is  unambiguous. A strict variant of .  foldlWithKey' f is  ambiguous at finite relation types if : the relation contains more than one equivalent key and  f# is not fold-commutative OR if the Eq instance on keys > does not correspond to indistinguishability. Otherwise it  is  unambiguous.  IExtract the bindings of an associative collection into a sequence, where K the bindings are in non-decreasing order by key. For finite maps, this  is increasing order. This function is  ambiguous* at finite relation types if the relation 4 contains more than one equivalent key, or if the Eq instance on 5 keys does not correspond to indistinguishability.  7Associative collections where the keys are observable.  9Extract the bindings of an associative collection into a ? sequence. The bindings are emitted in an unspecified order. This function is  ambiguous$ with respect to the sequence order B iff the associative collection contains more than one binding.  Furthermore, it is  ambiguous with respect to the actual key  returned, unless the Eq! instance on keys corresponds to  indistinguisability.  ?Extract the keys of an associative collection into a sequence. H The keys are emitted in an unspecified order. For finite relations, H keys which appear multiple times in the relation will appear as many $ times in the extracted sequence. This function is  ambiguous$ with respect to the sequence order B iff the associative collection contains more than one binding.  Furthermore, it is  ambiguous with respect to the actual key  returned, unless the Eq! instance on keys corresponds to  indistinguisability.  EApply a function to every element in an associative collection. The < mapped function additionally takes the value of the key. This function is  ambiguous! with respect to the actual keys  observed, unless the Eq! instance on keys corresponds to  indistinguisability. JCombine all the elements in the associative collection, given a combining D function and an initial value. The elements are processed in an E unspecified order. The combining function additionally takes the  value of the key.  foldWithKey f is  unambiguous iff f is fold-commutative and  the Eq6 instance on keys corresponds to indistinguisability. A strict variant of .  foldWithKey' f is  unambiguous iff f is fold-commutative and  the Eq6 instance on keys corresponds to indistinguisability. FExtract all bindings from an associative collection which satisfy the  given predicate. This function is  ambiguous! with respect to the actual keys  observed, unless the Eq! instance on keys corresponds to  indistinguisability. JSplit an associative collection into two sub-collections containing those F bindings which satisfy the given predicate and those which do not. This function is  ambiguous! with respect to the actual keys  observed, unless the Eq! instance on keys corresponds to  indistinguisability. CFinite maps where the keys additionally have an ordering relation. ) This class introduces no new methods. GAn associative collection where the keys form a set; that is, each key 7 appears in the associative collection at most once. Same as B7, but with a combining function to resolve duplicates. This function is always  unambiguous. Same as B7, but with a combining function to resolve duplicates; I the combining function takes the key in addition to the two elements. This function is always  unambiguous. Same as C7, but with a combining function to resolve duplicates. This function is  unambiguous. Same as C7, but with a combining function to resolve duplicates; I the combining function takes the key in addition to the two elements. F The key passed to the combining function is always the same as the  given key. This function is  unambiguous. Same as D7, but with a combining function to resolve duplicates. This function is  unambiguous. Same as D7, but with a combining function to resolve duplicates; I the combining function takes the key in addition to the two elements. This function is  unambiguous. Left biased union. Axioms:  unionl = unionwith (\ x y -> x)This function is  unambiguous. Right biased union. Axioms:  unionr = unionWith (\ x y -> y)This function is  unambiguous. Same as E7, but with a combining function to resolve duplicates. This function is  unambiguous. Same as F7, but with a combining function to resolve duplicates. This function is  unambiguous. GCompute the intersection of two finite maps. The resulting finite map H will contain bindings where the keys are the set intersection of the F keys in the argument finite maps. The combining function computes G the value of the element given the bound elements from the argument  finite maps. This function is  unambiguous. BComputes the difference of two finite maps; that is, all bindings C in the first finite map whose keys to not appear in the second. This function is always  unambiguous.  HTest whether the set of keys in the first finite map is a proper subset C of the set of keys of the second; that is, every key present in F the first finite map is also a member of the second finite map AND G there exists some key in the second finite map which is not present  in the first. This function is always  unambiguous. !DTest whether the set of keys in the first finite map is a subset of M the set of keys of the second; that is, if every key present in the first - finite map is also present in the second. This function is always  unambiguous. "LTest whether the first map is a submap of the second map given a comparison P function on elements; that is, if every key present in the first map is also S present in the second map and the comparison function returns true when applied  two the bound elements. This function is always  unambiguous. #STest whether the first map is a proper submap of the second map given a comparison P function on elements; that is, if every key present in the first map is also S present in the second map and the comparison function returns true when applied R two the bound elements AND there exiss some key in the second finite map which  is not present in the first. This function is always  unambiguous. $"Test whether the first map is the "same"* map as the second map given a comparison Y function on elements; that is, if the first and second maps have the same set of keys T and the comparison function returns true when applied to corresponding elements. This function is always  unambiguous. %GAn associative collection where the keys additionally have an ordering  relation. &IRemove the binding with the minimum key, and return its element together 5 with the remaining associative collection. Calls  if the G associative collection is empty. Which binding is removed if there , is more than one minimum is unspecified. This function is  ambiguous1 at finite relation types if the finite relation 8 contains more than one minimum key. Otherwise it is  unambiguous. 'FFind the binding with the minimum key and return its element. Signals M an error if the associative collection is empty. Which element is chosen 5 if there is more than one minimum is unspecified. This function is  ambiguous1 at finite relation types if the finite relation 8 contains more than one minimum key. Otherwise it is  unambiguous. (ARemove the binding with the minimum key and return the remaining C associative collection, or return empty if it is already empty. This function is  ambiguous1 at finite relation types if the finite relation 8 contains more than one minimum key. Otherwise it is  unambiguous. )FInsert a binding into an associative collection with the precondition  that the given key is <=. any existing keys already in the collection. 9 For finite maps, this precondition is strengthened to <. This function is  unambiguous under the preconditions. *IRemove the binding with the maximum key, and return its element together 5 with the remaining associative collection. Calls  if the G associative collection is empty. Which binding is removed if there , is more than one maximum is unspecified. This function is  ambiguous1 at finite relation types if the finite relation 8 contains more than one minimum key. Otherwise it is  unambiguous. +GFind the binding with the maximum key and return its element. Signals M an error if the associative collection is empty. Which element is chosen 5 if there is more than one maximum is unspecified. This function is  ambiguous1 at finite relation types if the finite relation 8 contains more than one minimum key. Otherwise it is  unambiguous. ,ARemove the binding with the maximum key and return the remaining C associative collection, or return empty if it is already empty. This function is  ambiguous1 at finite relation types if the finite relation 8 contains more than one minimum key. Otherwise it is  unambiguous. -FInsert a binding into an associative collection with the precondition  that the given key is >=. any existing keys already in the collection. 9 For finite maps, this precondition is strengthened to >. This function is  unambiguous under the precondition. .HFold across the elements of an associative collection in non-decreasing F order by key with right associativity. For finite maps, the order  is increasing. foldr f is  unambiguous if f is fold-commutative, at finite F map types, or at finite relation types if the relation contains no $ duplicate keys. Otherwise it is  ambiguous. /A strict variant of .. foldr' f is  unambiguous if f is fold-commutative, at finite F map types, or at finite relation types if the relation contains no $ duplicate keys. Otherwise it is  ambiguous. 0HFold across the elements of an associative collection in non-decreasing E order by key with left associativity. For finite maps, the order  is increasing. foldl f is  unambiguous if f is fold-commutative, at finite F map types, or at finite relation types if the relation contains no $ duplicate keys. Otherwise it is  ambiguous. 1A strict variant of 0. foldl' f is  unambiguous if f is fold-commutative, at finite F map types, or at finite relation types if the relation contains no $ duplicate keys. Otherwise it is  ambiguous. 2HFold across the elements of an associative collection in non-decreasing C order by key with right associativity. Signals an error if the C associative collection is empty. For finite maps, the order is  increasing. foldr1 f is  unambiguous if f is fold-commutative, at finite F map types, or at finite relation types if the relation contains no $ duplicate keys. Otherwise it is  ambiguous. 3A strict variant of 2. foldr1' f is  unambiguous if f is fold-commutative, at finite F map types, or at finite relation types if the relation contains no $ duplicate keys. Otherwise it is  ambiguous. 4HFold across the elements of an associative collection in non-decreasing B order by key with left associativity. Signals an error if the C associative collection is empty. For finite maps, the order is  increasing. foldl1 f is  unambiguous if f is fold-commutative, at finite F map types, or at finite relation types if the relation contains no $ duplicate keys. Otherwise it is  ambiguous. 5A strict variant of 4. foldl1' f is  unambiguous if f is fold-commutative, at finite F map types, or at finite relation types if the relation contains no $ duplicate keys. Otherwise it is  ambiguous. 6GConvert a sequence of bindings into an associative collection with the I precondition that the sequence is sorted into non-decreasing order by J key. For finite maps, this precondition is strengthened to increasing  order. This function is  unambiguous under the precondition. 7GMerge two associative collections with the precondition that every key * in the first associative collection is <= every key in the second B associative collection. For finite maps, this precondition is  strengthened to <. This function is  unambiguous under the precondition. 8$Extract all bindings whose keys are < the given key. This function is always  unambiguous. 9$Extract all bindings whose keys are <= the given key. This function is always  unambiguous. :$Extract all bindings whose keys are > the given key. This function is always  unambiguous. ;$Extract all bindings whose keys are >= the given key. This function is always  unambiguous. <ESplit an associative collection into two sub-collections, containing ! those bindings whose keys are <# the given key and those which are >=. This function is always  unambiguous. =ESplit an associative collection into two sub-collections, containing ! those bindings whose keys are <=# the given key and those which are >. This function is always  unambiguous. >ESplit an associative collection into two sub-collections, containing ! those bindings whose keys are <# the given key and those which are >. @ All bindings with keys equal to the given key are discarded. This function is always  unambiguous. ?8The root class of the associative collection hierarchy. @"The empty associative collection. This function is always  unambiguous. A8Create an associative collection with a single binding. This function is always  unambiguous. BICreate an associative collection from a list of bindings. Which element B and key are kept in the case of duplicate keys is unspecified. This function is  ambiguous% at finite map types if the sequence ; contains more than one equivalent key. Otherwise it is  unambiguous. C>Add a binding to an associative collection. For finite maps, C 8 keeps the new element in the case of duplicate keys. This function is  unambiguous. DHAdd a sequence of bindings to a collection. For finite maps, which key H and which element are kept in the case of duplicates is unspecified. J However, if a key appears in the sequence and in the map, (one of) the 2 elements in the list will be given preference. This function is  ambiguous. at finite map types if the sequence contains 2 more than one equivalent key. Otherwise it is  unambiguous. ECMerge two associative collections. For finite maps, which element 9 to keep in the case of duplicate keys is unspecified. This function is  ambiguous- at finite map types if the map keys are not  disjoint. Otherwise it is  unambiguous. F<Merge a sequence of associative collections. Which element 9 to keep in the case of duplicate keys is unspecified. This function is  ambiguous- at finite map types if the map keys are not ' mutually disjoint. Otherwise it is  unambiguous. GKDelete one binding with the given key, or leave the associative collection G unchanged if it does not contain the key. For bag-like associative A collections, it is unspecified which binding will be removed. This function is  ambiguous2 at finite relation types if the key appears more / than once in the relation. Otherwise it is  unambiguous. HLDelete all bindings with the given key, or leave the associative collection - unchanged if it does not contain the key. This function is always  unambiguous. IIDelete a single occurrence of each of the given keys from an associative P collection. For bag-like associative collections containing duplicate keys, 5 it is unspecified which bindings will be removed. This function is  ambiguous2 at finite relation types if any key appears both O in the sequence and in the finite relation AND the number of occurrences in O the sequence is less than the number of occurrences in the finite relation.  Otherwise it is  unambiguous. J2Test whether the associative collection is empty. Axioms:  null m = (size m == 0)This function is always  unambiguous. K=Return the number of bindings in the associative collection. This function is always  unambiguous. LCTest whether the given key is bound in the associative collection. This function is always  unambiguous. MDReturns the number of bindings with the given key. For finite maps # this will always return 0 or 1. This function is always  unambiguous. NEFind the element associated with the given key. Signals an error if I the given key is not bound. If more than one element is bound by the 3 given key, it is unspecified which is returned. This function is  ambiguous- at finite relation types if the key appears < more than once in the finite relation. Otherwise, it is  unambiguous. O7Find the element associated with the given key. Calls  if the K given key is not bound. If more than one element is bound by the given - key, it is unspecified which is returned. This function is  ambiguous- at finite relation types if the key appears < more than once in the finite relation. Otherwise, it is  unambiguous. PDReturn all elements bound by the given key in an unspecified order. This function is  ambiguous- at finite relation types if the key appears < more than once in the finite relation. Otherwise, it is  unambiguous. QCFind the element associated with the given key; return the element F and the collection with that element deleted. Signals an error if I the given key is not bound. If more than one element is bound by the ? given key, it is unspecified which is deleted and returned. This function is  ambiguous- at finite relation types if the key appears < more than once in the finite relation. Otherwise, it is  unambiguous. RCFind the element associated with the given key; return the element 8 and the collection with that element deleted. Calls fail if I the given key is not bound. If more than one element is bound by the ? given key, it is unspecified which is deleted and returned. This function is  ambiguous- at finite relation types if the key appears < more than once in the finite relation. Otherwise, it is  unambiguous. SGFind all elements bound by the given key; return a sequence containing F all such bound elements in an unspecified order and the collection # with all such elements deleted. This function is  ambiguous- at finite relation types if the key appears < more than once in the finite relation. Otherwise, it is  unambiguous. TFReturn the element associated with the given key. If no such element ! is found, return the default. This function is  ambiguous- at finite relation types if the key appears < more than once in the finite relation. Otherwise, it is  unambiguous. UHChange a single binding for the given key by applying a function to its M element. If the key binds more than one element, it is unspecified which P will be modified. If the key is not found in the collection, it is returned  unchanged. This function is  ambiguous- at finite relation types if the key appears < more than once in the finite relation. Otherwise, it is  unambiguous. VDChange all bindings for the given key by applying a function to its H elements. If the key is not found in the collection, it is returned  unchanged. This function is always  unambiguous. WESearches for a matching key in the collection. If the key is found, H the given function is called to adjust the value. If the key is not I found, a new binding is inserted with the given element. If the given D key is bound more than once in the collection, it is unspecified  which element is adjusted. This function is  ambiguous- at finite relation types if the key appears < more than once in the finite relation. Otherwise, it is  unambiguous. XHSearches for all matching keys in the collection. If the key is found, M the given function is applied to all its elements to adjust their values. N If the key is not found, a new binding is inserted with the given element. This function is always  unambiguous. YKChange or delete a single binding for the given key by applying a function , to its element. If the function returns Nothing, then the binding U will be deleted. If the key binds more than one element, it is unspecified which P will be modified. If the key is not found in the collection, it is returned  unchanged. This function is  ambiguous- at finite relation types if the key appears < more than once in the finite relation. Otherwise, it is  unambiguous. ZJChange or delete all bindings for the given key by applying a function to = its elements. For any element where the function returns Nothing, the Q corresponding binding is deleted. If the key is not found in the collection,  it is returned unchanged. This function is always  unambiguous. [JCombine all the elements in the associative collection, given a combining D function and an initial value. The elements are processed in an  unspecified order. Note that [ ignores the keys. fold f is  unambiguous iff f is fold-commutative. \A strict variant of [. fold' f is  unambiguous iff f is fold-commutative. ]ICombine all the elements in a non-empty associative collection using the M given combining function. Signals an error if the associative collection F is empty. The elements are processed in an unspecified order. An F implementation may choose to process the elements linearly or in a  balanced fashion (like reduce1 on sequences). Note that ]  ignores the keys. fold1 f is  unambiguous iff f is fold-commutative. ^A strict variant of ]. fold1' f is  unambiguous iff f is fold-commutative. _AExtract all bindings whose elements satisfy the given predicate. This function is always  unambiguous. `FSplit an associative collection into those bindings which satisfy the , given predicate, and those which do not. This function is always  unambiguous. aIReturns all the elements in an associative collection, in an unspecified  order. This function is  ambiguous) iff the associative collection contains  more than one element. bBSemanticly, this function is a partial identity function. If the O datastructure is infinite in size or contains exceptions or non-termination ! in the structure itself, then strict( will result in bottom. Operationally, S this function walks the datastructure forcing any closures. Elements contained  in the map are not forced. This function is always  unambiguous. c Similar to b:, this function walks the datastructure forcing closures.  However,  strictWith3 will additionally apply the given function to the ( map elements, force the result using seq, and then ignore it. I This function can be used to perform various levels of forcing on the & sequence elements. In particular:   strictWith id xs Kwill force the spine of the datastructure and reduce each element to WHNF. This function is always  unambiguous. d.A method to facilitate unit testing. Returns  if the structural C invariants of the implementation hold for the given associative ) collection. If this function returns , it represents a bug; G generally, either the implementation itself is flawed, or an unsafe > operation has been used while violating the preconditions. eIReturns the name of the module implementing this associative collection. fEApply a function to the elements of every binding in the associative  collection. Identical to fmap from Functor. This function is always  unambiguous. gSpecialization of "" where the comparison function is  given by (==). hSpecialization of # where the comparison function  is given by (==). iSpecialization of $" where the comparison function is  given by (==).       !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTdefault element the key to look up the associative collection UVWXYZ[\]^_`abcdefghijklmnopqrstuvwxy      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyf?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcde%&'()*+,-./0123456789:;<=> !"#$     ghijklmnopqrstuvwxy       !"#$%&'()*+,-./0123456789:;<=>?&@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyGHC, Hugs (MPTC and FD)stablerobdockins AT fastmail DOT fm Safe-InferredzGLeft (front) cons on a sequence. The new element appears on the left.  Identical to . {HRight (rear) cons on a sequence. The new element appears on the right.  Identical to   with reversed arguments. |$Append two sequences. Identical to R. Subsumes the Prelude  definition. }/Lookup an element in a sequence. Identical to 8 with  reversed arguments. ~%Subset test operation. Identical to . Set difference. Identical to .  Set intersection. Identical to . Set union. Identical to . z{|}~z{|}~z{|}~z{|}~GHC, Hugs (MPTC and FD)stablerobdockins AT fastmail DOT fm Safe-Inferred %??%       !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]ZX[ "#$!WY%&'()+*,-./0123456@ABCDEFGHIJ789:ST;<=>?KLMNOPQRU^_`abcdefghijkl)*+,-./0mnopABqC%&'(;<Trstuvwxyz{|}~X SUVZ!Wnmp`abcdefguwxijz|kl{})*+,-./0~ZX ABqCE%&'(;<STUVW!EdisonAPI-1.2.2Data.Edison.PreludeData.Edison.SeqData.Edison.Seq.ListSeqData.Edison.CollData.Edison.Coll.UtilsData.Edison.AssocData.Edison.Sym Data.EdisonMeasuredmeasureReversibleHashunhash UniqueHashHashhashSequencelconsrconsfromListcopylviewlheadlheadMltailltailMrviewrheadrheadMrtailrtailMnullsizetoListconcatreverse reverseOntofoldfold'fold1fold1'foldrfoldr'foldlfoldl'foldr1foldr1'foldl1foldl1'reducerreducer'reducelreducel'reduce1reduce1'takedropsplitAtsubseqfilter partition takeWhile dropWhile splitWhileinBoundslookuplookupMlookupWithDefaultupdateadjust mapWithIndexfoldrWithIndexfoldrWithIndex'foldlWithIndexfoldlWithIndex'zipzip3zipWithzipWith3unzipunzip3 unzipWith unzipWith3strict strictWithstructuralInvariant instanceNamemap singleton concatMapemptyappendSeq moduleNameOrdSetSet fromSeqWith insertWith insertSeqWithunionlunionr unionWith unionSeqWithintersectionWithOrdCollminViewminElemmaxViewmaxElemtoOrdSequnsafeMapMonotonicColltoSeq lookupAllOrdSetXSetX intersection differencesymmetricDifference properSubsetsubsetOrdCollX deleteMin deleteMaxunsafeInsertMinunsafeInsertMaxunsafeFromOrdSeq unsafeAppendfilterLTfilterLEfilterGTfilterGEpartitionLT_GEpartitionLE_GTpartitionLT_GTCollXfromSequnionSeqinsert insertSeqdelete deleteAll deleteSeqmembercountunion insertList unionList deleteListunsafeFromOrdList lookupList toOrdList fromListWithinsertListWith unionListWith mapPartialunionMap OrdFiniteMap FiniteMap unionWithKeyunionSeqWithKeyintersectionWithKeyOrdAssocminViewWithKeyminElemWithKeymaxViewWithKeymaxElemWithKey foldrWithKey foldrWithKey' foldlWithKey foldlWithKey'Assockeys mapWithKey foldWithKey foldWithKey' filterWithKeypartitionWithKey OrdFiniteMapX FiniteMapXfromSeqWithKey insertWithKeyinsertSeqWithKeysubmapByproperSubmapBy sameMapBy OrdAssocXAssocXlookupAndDeletelookupAndDeleteMlookupAndDeleteAll adjustAlladjustOrInsertadjustAllOrInsertadjustOrDeleteadjustOrDeleteAllelementssubmap properSubmapsameMap elementsListfromListWithKeyinsertListWithKeykeysListunionListWithKey<||>++!|=\\/\\/baseGHC.Basefailghc-prim GHC.TypesTrueFalse $fSequence[] GHC.ClassesEq