!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ Copyright (c) 1998 Chris Okasaki1BSD3; see COPYRIGHT file for terms and conditionsrobdockins AT fastmail DOT fmstableGHC, Hugs (MPTC and FD)Safe79This 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 for an individual item. Some datastructures are able to speed up the calculation of a measure by caching intermediate values of the computation.GThis 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.EThis class represents hashable objects where the hash function is uniqueG (injective). There are no new methods, just a stronger invariant: 0forall x,y :: a. (x == y) iff (hash x == hash y)MThis class represents hashable objects. If obeys the following invariant: 4forall x,y :: a. (x == y) implies (hash x == hash y)%Copyright (c) 1998-1999 Chris Okasaki0MIT; see COPYRIGHT file for terms and conditionsrobdockins AT fastmail DOT fmstableGHC, Hugs (MPTC and FD)Safe79LThe } class defines an interface for datatypes which implement sequences. A description for each function is given below. 1Add 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 ) 1Add 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 ) UReturn 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 )3Returns 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 )PDelete 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 )3Delete 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 )[Return 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 )4Returns 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 )bDelete 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 )>Delete the last (rightmost) element of the sequence. Calls  of the sequence is emptyAxioms: 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> = nAxioms: 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 )7Flatten a sequence of sequences into a simple sequence. #concat xss = foldr append empty xssAxioms: #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 )6Reverse a sequence onto the front of another sequence. CreverseOnto <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. fold3 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'3 is one of the few ambiguous sequence functions.Axioms: 6forall 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.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: 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: 4forall 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, 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: 8forall 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, given a combining function and an initial value. The function is applied with left nesting. ;foldl (%) c <x0,...,xn-1> = (((c % x0) % x1) % ... ) % xn-1Axioms: 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:8forall a. f _|_ a = _|_ ==> foldl f z xs = foldl' f z 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 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. ofoldr1 (+) <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 xsThis function is always  unambiguous.Default running time:  O( t * n ) where t is the running time of f%Strict variant of $.Axioms:6forall a. f a _|_ = _|_ ==> foldr1 f xs = foldr1' f 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 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. mfoldl1 (+) <x0,...,xn-1> | n==0 = error "ModuleName.foldl1: empty sequence" | n>0 = (x0 + x1) + ... + xn-1Axioms: 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:6forall a. f _|_ a = _|_ ==> foldl1 f xs = foldl1' f xsThis 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: aforall 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*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: aforall 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,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-12 such that the nesting depth of parentheses is  O( log n )@. The precise shape of this parenthesization is unspecified. ereduce1 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: 5mergesort 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 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.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 i4 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 iS 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 )1Extract 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 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 )2Extract the elements of a sequence that satisfy the given predicate, retaining the relative ordering of elements from the original sequence. Xfilter p xs = foldr pcons empty xs where pcons x xs = if p x then cons x xs else xsAxioms: filter p empty = empty Yfilter 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 p3Separate 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. 3partition 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 p4IExtract the maximal prefix of elements satisfying the given predicate. &takeWhile p xs = fst (splitWhile p xs)Axioms: takeWhile p empty = empty XtakeWhile 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 p5HDelete the maximal prefix of elements satisfying the given predicate. &dropWhile p xs = snd (splitWhile p xs)Axioms: dropWhile p empty = empty QdropWhile 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 p6sSplit a sequence into the maximal prefix of elements satisfying the given predicate, and the remaining sequence. psplitWhile 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: 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 p7RTest 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 )8mReturn the element at the given index. All indexes are 0 based. Signals error if the index out of bounds. olookup 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 )9JReturn the element at the given index. All indexes are 0 based. Calls  if the index is out of bounds. NlookupM i xs@<x0,...,xn-1> | inBounds i xs = Just xi | otherwise = NothingAxioms: +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 default argument if the index is out of bounds. All indexes are 0 based. OlookupWithDefault d i xs@<x0,...,xn-1> | inBounds i xs = xi | otherwise = dAxioms: 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 );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 = xsAxioms: *not (inBounds i xs) ==> update i y xs = xs Ssize 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 )<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. badjust f i xs@<x0,...,xn-1> | inBounds i xs = <x0,...xi-1,f xi,xi+1,...,xn-1> | otherwise = xsAxioms: *not (inBounds i xs) ==> adjust f i xs = xs Vsize 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 NF, but include the index with each element. All indexes are 0 based. 8mapWithIndex 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  F, but include the index with each element. All indexes are 0 based. NfoldrWithIndex f c <x0,...,xn-1> = f 0 x0 (f 1 x1 (... (f (n-1) xn-1 c)))Axioms: foldrWithIndex f c empty = c MfoldrWithIndex 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: Vforall 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 "F, but include the index with each element. All indexes are 0 based. PfoldlWithIndex f c <x0,...,xn-1> = f (...(f (f c 0 x0) 1 x1)...) (n-1) xn-1)Axioms: foldlWithIndex f c empty = c MfoldlWithIndex 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 fAStrict variant of @.Axioms: Vforall 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 fBCombine two sequences into a sequence of pairs. If the sequences are different lengths, the excess elements of the longer sequence is discarded. Szip <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. qzip3 <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 ) )DCombine 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: JzipWith 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 fELike D7 but for a three-place function and three sequences. 5zipWith3 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 fF7Transpose 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 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) = zAxioms: ,unzip3 xyzs = unzipWith3 fst3 snd3 thd3 xyzsThis function is always  unambiguous.Default running time: O( n )HUMap 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 gIZMap three functions across every element of a sequence, yielding a triple of sequences. 4unzipWith3 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 hJSemanticly, 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 )K Similar to JF, 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 xsJwill 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.TDefault running time: unbounded (forcing element closures can take arbitrairly long)L.A method to facilitate unit testing. Returns q if the structural 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 fO+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 )P^Apply 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, m0 is the length of the output sequence, and t is the running time of fQ"The empty sequence. Identical to mzero from  MonadPlus.  empty = <>This function is always  unambiguous.Default running time: O( 1 )RpAppend 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 xsThis function is always  unambiguous.Default running time: O( n1 )L  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRL  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRLNOPQR  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMF  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQR Copyright (c) 1998 Chris Okasaki0MIT; see COPYRIGHT file for terms and conditionsrobdockins AT fastmail DOT fmstableGHC, Hugs (MPTC and FD)Safe79MSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~LSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~LSUVWXYZ\[^]_a`cbdefghijklmnopqsrtuvwxyz{|}~TMSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ Copyright (c) 1998 Chris Okasaki0MIT; see COPYRIGHT file for terms and conditionsrobdockins AT fastmail DOT fmstableGHC, Hugs (MPTC and FD)Safe79MCollections with observable elements where the set property is maintained and where additionally, there is an ordering relation on the elements. This class introduces no new methods, and is simply an abbreviation for the context: (OrdColl c a,Set c a)Collections with observable elements where the set property is maintained; 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.u The passed in combining functions are used to choose which element is kept in the case of duplicates. They are required to satisfy the precondition that, given two equal elements, they return a third element equal to the other two. Usually, the combining function just returns its first or second argument, but it can combine elements in non-trivial ways.The combining function should usually be associative. Where the function involves a sequence of elements, the elements will be combined from 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 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 5 but with a combining function to resolve duplicates.This function is  unambiguous under the "with" precondition.Same as 5 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 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.Same as 6, but with a combining function to resolve duplicates.This function is  unambiguous under the "with" precondition.Collections with observable elements where the elements additionally 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 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  ambiguousX at bag types, if more than one minimum element exists in the bag. Otherwise, it is  unambiguous.Return the minimum element in the collection. If there are multiple copies of the minimum element, it is unspecified which is chosen. Note that , , and M may make different choices. Signals an error if the collection is empty.This function is  ambiguousX at bag types, if more than one minimum 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 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  ambiguousX at bag types, if more than one maximum element exists in the bag. Otherwise, it is  unambiguous.Return the maximum element in the collection. If there are multiple copies of the maximum element, it is unspecified which is chosen. Note that ,  and M may make different choices. Signals an error if the collection is empty.This function is  ambiguousX at bag types, if more than one maximum element exists in the bag. Otherwise, it is  unambiguous.~Fold across the elements in non-decreasing order with right associativity. (For sets, this will always be increasing order)This function is  unambiguous if the combining function is fold-commutative, at all set types, and at bag types 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 fold-commutative, at all set types, and at bag types where no two equivalent elements exist in the bag. Otherwise it is  ambiguous.}Fold across the elements in non-decreasing order with left associativity. (For sets, this will always be increasing order)This function is  unambiguous if the combining function is fold-commutative, at all set types, and at bag types 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 fold-commutative, at all set types, and at bag types where no two equivalent elements exist in the bag. Otherwise it is  ambiguous.Fold across the elements in non-decreasing order with right associativity, or signal an error if the collection is empty. (For sets, this will always be increasing order)This function is  unambiguous if the combining function is fold-commutative, at all set types, and at bag types 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 fold-commutative, at all set types, and at bag types where no two equivalent elements exist in the bag. Otherwise it is  ambiguous.Fold across the elements in non-decreasing order with left associativity, or signal an error if the collection is empty. (For sets, this will always be increasing order)This function is  unambiguous if the combining function is fold-commutative, at all set types, and at bag types 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 fold-commutative, at all set types, and at bag types where no two equivalent elements exist in the bag. Otherwise it is  ambiguous.^List 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  unambiguousD if no two equivalent elements exist in the bag; otherwise it is  ambiguous.Map 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 yThis function is  unambiguous, under the precondition.eCollections with observable elements. See the module documentation for comments on observability.<List the elements of the collection in an unspecified order.This function is  ambiguous6 iff the collection contains more than one element.Lookup one element equal to the given element. If no elements exist in the collection equal to the given element, an error is signaled. If multiple copies of the given element exist in the collection, it is unspecified which is returned.This function is  ambiguousm at bag types, when more than one element equivalent to the given item is in the bag. Otherwise it is  unambiguous.vLookup one element equal to the given element. If no elements exist in the collection equal to the given element, w is called. If multiple copies of the given element exist in the collection, it is unspecified which is returned.This function is  ambiguousm at bag types, when more than one element equivalent to the given item is in the bag. Otherwise it is  unambiguous.rReturn a sequence containing all elements in the collection equal to the given element in an unspecified order.This function is  ambiguousm at bag types, when more than one element equivalent to the given item is in the bag. Otherwise it is  unambiguous.Lookup one element equal to the (second) given element in the collection. If no elements exist in the collection equal to the given element, then the default element is returned.This function is  ambiguousm at bag types, when more than one element equivalent to the given item is in the bag. Otherwise it is  unambiguous.CFold 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.wFold over all the elements in a collection in an unspecified order. 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.1Remove 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 F, this function walks the datastructure forcing closures. However,  strictWithb will additionally apply the given function to the collection 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 xsJwill force the spine of the datastructure and reduce each element to WHNF.This function is always  unambiguous.Sets where the elements also have an ordering relation. This class contains no methods; it is only an abbreviation for the context (OrdCollX c a,SetX c a).A collection where the set property is maintained; that is, a set contains at most one element of the equivalence class formed by the  instance on the elements.{Computes 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.oComputes the difference of two sets; that is, all elements in the first set which are not in the second set.This function is always  unambiguous.uComputes the symmetric difference of two sets; that is, all elements which appear in exactily one of the two sets.This function is always  unambiguous.Test whether the first set is a proper subset of the second set; that is, if every element in the first set is also a member of the second set AND there exists some element in the second set which is not present in the first.This function is always  unambiguous.Test whether the first set is a subset of the second set; that is, if 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.Delete the minimum element from the collection. If there is more than one minimum, it is unspecified which is deleted. If the collection is empty, it will be returned unchanged.This function is  ambiguousV at bag types if more than one minimum element exists in the bag. Otherwise it is  unambiguous.Delete the maximum element from the collection. If there is more than one maximum, it is unspecified which is deleted. If the collection is empty, it will be returned unchanged.This function is  ambiguousV at bag types if more than one maximum element exists in the bag. Otherwise it is  unambiguous.AInsert 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.AInsert 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.tConvert a sequence in non-decreasing order into a collection. For sets, the sequence must be in increasing order.This function is  unambiguous , under the above preconditions.HUnion two collections where every element in the first collection is <=[ every element in the second collection. 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 >9. 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.This is the root class of the collection hierarchy. However, it is perfectly adequate for many applications that use sets or bags.create a singleton collectionThis function is always  unambiguous.pConvert a sequence to a collection. For sets, it is unspecified which element is kept in case of duplicates.This function is  ambiguousW at set types if more than one equivalent item is in the sequence. Otherwise it is  unambiguous.qMerge a sequence of collections. For sets, it is unspecified which element is kept in the case of duplicates.This function is  ambiguousX at set types if the sets in the sequence are not mutually disjoint. Otherwise it is  unambiguous.Insert an element into a collection. For sets, if an equal element 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, the behavior with regard to multiple equal elements is unspecified.This function is  ambiguous at set types if the sequence contains more than one equivalent item or an item which is already in the set. Otherwise it is  unambiguous.Delete a single occurrence of the given element from a collection. For bags, it is unspecified which element will be deleted.This function is  ambiguoush at bag types if more than one item exists in the bag equivalent to the given item. Otherwise it is  unambiguous.dDelete 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 a collection. For bags, there may be multiple occurrences of a 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 exists in the bag equivalent to any item in the list and the number 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.0Return the number of elements in the collection.This function is always  unambiguous.4Test whether the given element is in the collection.Axioms: member x xs = (count x xs > 0)This function is always  unambiguous.nCount 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.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 strictK will result in bottom. Operationally, this function walks the datastructure forcing any closures. In many collections, the collction "shape" depends on the value of the elemnts; in such cases, the values of the elements will be forced to the extent necessary to force the structure of the collection, but no further.This function is always  unambiguous..A method to facilitate unit testing. Returns s if the structural invariants of the implementation hold for the given collection. If this function returns , it represents a bug; generally, either 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.wMerge two collections. For sets, it is unspecified which element is 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 elementelement to lookup collectionXX   Copyright (c) 1998 Chris Okasaki0MIT; see COPYRIGHT file for terms and conditionsrobdockins AT fastmail DOT fmstableGHC, Hugs (MPTC and FD)Safe79^Apply a function across all the elements in a collection and transform the collection type.`Map a partial function across all elements of a collection and transform the collection type.Map a monotonic function across all the elements of a collection and transform the collection type. The function is required to satisfy the following precondition: forall x y. x < y ==> f x < f yrMap a collection-producing function across all elements of a collection and collect the results together using . Copyright (c) 1998 Chris Okasaki0MIT; see COPYRIGHT file for terms and conditionsrobdockins AT fastmail DOT fmstableGHC, Hugs (MPTC and FD)Safe79oFinite maps with observable keys where the keys additionally have an ordering relation. This class introduces no new methods.!Finite maps with observable keys.Same as E, but with a combining function to resolve duplicates. 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 Eq9 instance on keys corresponds to indistinguishability.Same as F, but with a combining function to resolve duplicates. 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 Eq9 instance on keys corresponds to indistinguishability.Same as , except that the combining function 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 Eq9 instance on keys corresponds to indistinguishability.hAn 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 z if the associative collection is empty. Which binding is chosen if there are multiple minimum keys is unspecified.This function is  ambiguousf at finite relation types if more than one minimum key exists in the relation. Furthermore, it is  ambiguous7 with respect to the actual key observed unless the Eq8 instance on keys corresponds to indistinguisability.Find the binding with the minimum key in an associative collection and return the key and the element. Signals an error if the associative collection is empty. Which binding is chosen if there are multiple minimum keys is unspecified.This function is  ambiguousf at finite relation types if more than one minimum key exists in the relation. Furthermore, it is  ambiguous7 with respect to the actual key observed unless the Eq8 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 z if the associative collection is empty. Which binding is chosen if there are multiple maximum keys is unspecified.This function is  ambiguousf at finite relation types if more than one maximum key exists in the relation. Furthermore, it is  ambiguous7 with respect to the actual key observed unless the Eq8 instance on keys corresponds to indistinguisability.Find the binding with the maximum key in an associative collection and return the key and the element. Signals an error if the associative collection is empty. Which binding is chosen if there are multiple maximum keys is unspecified.This function is  ambiguousf at finite relation types if more than one maximum key exists in the relation. Furthermore, it is  ambiguous7 with respect to the actual key observed unless the Eq8 instance on keys corresponds to indistinguisability.Fold over all bindings in an associative collection in non-decreasing order by key with right associativity, given a combining function and an initial value. For finite maps, the order is increasing.foldrWithKey f is  ambiguousZ at finite relation types if the relation contains more than one equivalent key and f# is not fold-commutative OR if the EqA instance on keys does not correspond to indistingusihability.A strict variant of .foldrWithKey' f is  ambiguousZ at finite relation types if the relation contains more than one equivalent key and f# is not fold-commutative OR if the EqV instance on keys does not correspond to indistingusihability. Otherwise it is  unambiguous.Fold over all bindings in an associative collection in non-decreasing order by key with left associativity, given a combining function and an initial value. For finite maps, the order is increasing.foldlWithKey f is  ambiguousZ at finite relation types if the relation contains more than one equivalent key and f# is not fold-commutative OR if the EqU instance on keys does not correspond to indistingusihability. Otherwise it is  unambiguous.A strict variant of .foldlWithKey' f is  ambiguousZ at finite relation types if the relation contains more than one equivalent key and f# is not fold-commutative OR if the EqV instance on keys does not correspond to indistinguishability. Otherwise it is  unambiguous. Extract the bindings of an associative collection into a sequence, where 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 contains more than one equivalent key, or if the EqA instance on keys does not correspond to indistinguishability. 6Associative collections where the keys are observable. wExtract 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 iff the associative collection contains more than one binding. Furthermore, it is  ambiguous8 with respect to the actual key returned, unless the Eq8 instance on keys corresponds to indistinguisability. Extract the keys of an associative collection into a sequence. The keys are emitted in an unspecified order. For finite relations, 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 iff the associative collection contains more than one binding. Furthermore, it is  ambiguous8 with respect to the actual key returned, unless the Eq8 instance on keys corresponds to indistinguisability. Apply a function to every element in an associative collection. The mapped function additionally takes the value of the key.This function is  ambiguous9 with respect to the actual keys observed, unless the Eq8 instance on keys corresponds to indistinguisability.Combine all the elements in the associative collection, given a combining function and an initial value. The elements are processed in an unspecified order. The combining function additionally takes the value of the key. foldWithKey f is  unambiguous iff f is fold-commutative and the Eq5 instance on keys corresponds to indistinguisability.A strict variant of .foldWithKey' f is  unambiguous iff f is fold-commutative and the Eq5 instance on keys corresponds to indistinguisability.YExtract all bindings from an associative collection which satisfy the given predicate.This function is  ambiguous9 with respect to the actual keys observed, unless the Eq8 instance on keys corresponds to indistinguisability.Split an associative collection into two sub-collections containing those bindings which satisfy the given predicate and those which do not.This function is  ambiguous9 with respect to the actual keys observed, unless the Eq8 instance on keys corresponds to indistinguisability.kFinite maps where the keys additionally have an ordering relation. This class introduces no new methods.}An associative collection where the keys form a set; that is, each key appears in the associative collection at most once.Same as B6, but with a combining function to resolve duplicates.This function is always  unambiguous.Same as B, but with a combining function to resolve duplicates; the combining function takes the key in addition to the two elements.This function is always  unambiguous.Same as C6, but with a combining function to resolve duplicates.This function is  unambiguous.Same as C, but with a combining function to resolve duplicates; the combining function takes the key in addition to the two elements. The key passed to the combining function is always the same as the given key.This function is  unambiguous.Same as D6, but with a combining function to resolve duplicates.This function is  unambiguous.Same as D, but with a combining function to resolve duplicates; 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 E6, but with a combining function to resolve duplicates.This function is  unambiguous.Same as F6, but with a combining function to resolve duplicates.This function is  unambiguous.+Compute the intersection of two finite maps. The resulting finite map will contain bindings where the keys are the set intersection of the keys in the argument finite maps. The combining function computes the value of the element given the bound elements from the argument finite maps.This function is  unambiguous.Computes the difference of two finite maps; that is, all bindings in the first finite map whose keys to not appear in the second.This function is always  unambiguous. (Test whether the set of keys in the first finite map is a proper subset of the set of keys of the second; that is, every key present in the first finite map is also a member of the second finite map AND there exists some key in the second finite map which is not present in the first.This function is always  unambiguous.!Test whether the set of keys in the first finite map is a subset of 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." Test whether the first map is a submap of the second map given a comparison function on elements; that is, if every key present in the first map is also present in the second map and the comparison function returns true when applied two the bound elements.This function is always  unambiguous.#gTest whether the first map is a proper submap of the second map given a comparison function on elements; that is, if every key present in the first map is also present in the second map and the comparison function returns true when applied 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 function on elements; that is, if the first and second maps have the same set of keys and the comparison function returns true when applied to corresponding elements.This function is always  unambiguous.%SAn associative collection where the keys additionally have an ordering relation.&~Remove the binding with the minimum key, and return its element together with the remaining associative collection. Calls z if the associative collection is empty. Which binding is removed if there is more than one minimum is unspecified.This function is  ambiguousi at finite relation types if the finite relation contains more than one minimum key. Otherwise it is  unambiguous.'Find the binding with the minimum key and return its element. Signals an error if the associative collection is empty. Which element is chosen if there is more than one minimum is unspecified.This function is  ambiguousi at finite relation types if the finite relation contains more than one minimum key. Otherwise it is  unambiguous.(Remove the binding with the minimum key and return the remaining associative collection, or return empty if it is already empty.This function is  ambiguousi at finite relation types if the finite relation contains more than one minimum key. Otherwise it is  unambiguous.)_Insert a binding into an associative collection with the precondition that the given key is <=g any existing keys already in the collection. For finite maps, this precondition is strengthened to <.This function is  unambiguous under the preconditions.*~Remove the binding with the maximum key, and return its element together with the remaining associative collection. Calls z if the associative collection is empty. Which binding is removed if there is more than one maximum is unspecified.This function is  ambiguousi at finite relation types if the finite relation contains more than one minimum key. Otherwise it is  unambiguous.+Find the binding with the maximum key and return its element. Signals an error if the associative collection is empty. Which element is chosen if there is more than one maximum is unspecified.This function is  ambiguousi at finite relation types if the finite relation contains more than one minimum key. Otherwise it is  unambiguous.,Remove the binding with the maximum key and return the remaining associative collection, or return empty if it is already empty.This function is  ambiguousi at finite relation types if the finite relation contains more than one minimum key. Otherwise it is  unambiguous.-_Insert a binding into an associative collection with the precondition that the given key is >=g any existing keys already in the collection. For finite maps, this precondition is strengthened to >.This function is  unambiguous under the precondition..Fold across the elements of an associative collection in non-decreasing order by key with right associativity. For finite maps, the order is increasing.foldr f is  unambiguous if f is fold-commutative, at finite 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 map types, or at finite relation types if the relation contains no duplicate keys. Otherwise it is  ambiguous.0Fold across the elements of an associative collection in non-decreasing order by key with left associativity. For finite maps, the order is increasing.foldl f is  unambiguous if f is fold-commutative, at finite 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 map types, or at finite relation types if the relation contains no duplicate keys. Otherwise it is  ambiguous.2Fold across the elements of an associative collection in non-decreasing order by key with right associativity. Signals an error if the associative collection is empty. For finite maps, the order is increasing.foldr1 f is  unambiguous if f is fold-commutative, at finite 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 map types, or at finite relation types if the relation contains no duplicate keys. Otherwise it is  ambiguous.4Fold across the elements of an associative collection in non-decreasing order by key with left associativity. Signals an error if the associative collection is empty. For finite maps, the order is increasing.foldl1 f is  unambiguous if f is fold-commutative, at finite 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 map types, or at finite relation types if the relation contains no duplicate keys. Otherwise it is  ambiguous.6Convert a sequence of bindings into an associative collection with the precondition that the sequence is sorted into non-decreasing order by key. For finite maps, this precondition is strengthened to increasing order.This function is  unambiguous under the precondition.7qMerge two associative collections with the precondition that every key in the first associative collection is <=n every key in the second 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.<fSplit 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.=fSplit 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.>fSplit an associative collection into two sub-collections, containing those bindings whose keys are <# the given key and those which are >A. All bindings with keys equal to the given key are discarded.This function is always  unambiguous.?7The root class of the associative collection hierarchy.@!The empty associative collection.This function is always  unambiguous.A7Create an associative collection with a single binding.This function is always  unambiguous.BCreate an associative collection from a list of bindings. Which element 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, C8 keeps the new element in the case of duplicate keys.This function is  unambiguous.D Add a sequence of bindings to a collection. For finite maps, which key and which element are kept in the case of duplicates is unspecified. However, if a key appears in the sequence and in the map, (one of) the elements in the list will be given preference.This function is  ambiguous` at finite map types if the sequence contains more than one equivalent key. Otherwise it is  unambiguous.E{Merge two associative collections. For finite maps, which element to keep in the case of duplicate keys is unspecified.This function is  ambiguousK at finite map types if the map keys are not disjoint. Otherwise it is  unambiguous.FtMerge a sequence of associative collections. Which element to keep in the case of duplicate keys is unspecified.This function is  ambiguousT at finite map types if the map keys are not mutually disjoint. Otherwise it is  unambiguous.GDelete one binding with the given key, or leave the associative collection unchanged if it does not contain the key. For bag-like associative collections, it is unspecified which binding will be removed.This function is  ambiguousa at finite relation types if the key appears more than once in the relation. Otherwise it is  unambiguous.HxDelete all bindings with the given key, or leave the associative collection unchanged if it does not contain the key.This function is always  unambiguous.IDelete a single occurrence of each of the given keys from an associative collection. For bag-like associative collections containing duplicate keys, it is unspecified which bindings will be removed.This function is  ambiguous at finite relation types if any key appears both in the sequence and in the finite relation AND the number of occurrences in the sequence is less than the number of occurrences in the finite relation. Otherwise it is  unambiguous.J1Test 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.LBTest whether the given key is bound in the associative collection.This function is always  unambiguous.MfReturns the number of bindings with the given key. For finite maps this will always return 0 or 1.This function is always  unambiguous.NFind the element associated with the given key. Signals an error if the 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  ambiguousi 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 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  ambiguousi at finite relation types if the key appears more than once in the finite relation. Otherwise, it is  unambiguous.PCReturn all elements bound by the given key in an unspecified order.This function is  ambiguousi at finite relation types if the key appears more than once in the finite relation. Otherwise, it is  unambiguous.QFind the element associated with the given key; return the element and the collection with that element deleted. Signals an error if 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  ambiguousi at finite relation types if the key appears more than once in the finite relation. Otherwise, it is  unambiguous.R{Find the element associated with the given key; return the element and the collection with that element deleted. Calls fail if 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  ambiguousi at finite relation types if the key appears more than once in the finite relation. Otherwise, it is  unambiguous.SFind all elements bound by the given key; return a sequence containing all such bound elements in an unspecified order and the collection with all such elements deleted.This function is  ambiguousi 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  ambiguousi at finite relation types if the key appears more than once in the finite relation. Otherwise, it is  unambiguous.UChange a single binding for the given key by applying a function to its element. If the key binds more than one element, it is unspecified which will be modified. If the key is not found in the collection, it is returned unchanged.This function is  ambiguousi at finite relation types if the key appears more than once in the finite relation. Otherwise, it is  unambiguous.VChange all bindings for the given key by applying a function to its elements. If the key is not found in the collection, it is returned unchanged.This function is always  unambiguous.W7Searches for a matching key in the collection. If the key is found, the given function is called to adjust the value. If the key is not found, a new binding is inserted with the given element. If the given key is bound more than once in the collection, it is unspecified which element is adjusted.This function is  ambiguousi at finite relation types if the key appears more than once in the finite relation. Otherwise, it is  unambiguous.XSearches for all matching keys in the collection. If the key is found, the given function is applied to all its elements to adjust their values. If the key is not found, a new binding is inserted with the given element.This function is always  unambiguous.YwChange or delete a single binding for the given key by applying a function to its element. If the function returns Nothing, then the binding will be deleted. If the key binds more than one element, it is unspecified which will be modified. If the key is not found in the collection, it is returned unchanged.This function is  ambiguousi at finite relation types if the key appears more than once in the finite relation. Otherwise, it is  unambiguous.ZChange or delete all bindings for the given key by applying a function to its elements. For any element where the function returns Nothings, the corresponding binding is deleted. If the key is not found in the collection, it is returned unchanged.This function is always  unambiguous.[Combine all the elements in the associative collection, given a combining 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.]<Combine all the elements in a non-empty associative collection using the given combining function. Signals an error if the associative collection is empty. The elements are processed in an unspecified order. An 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._@Extract all bindings whose elements satisfy the given predicate.This function is always  unambiguous.`qSplit an associative collection into those bindings which satisfy the given predicate, and those which do not.This function is always  unambiguous.aRReturns all the elements in an associative collection, in an unspecified order.This function is  ambiguousB iff the associative collection contains more than one element.bSemanticly, 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 map are not forced.This function is always  unambiguous.c Similar to bF, this function walks the datastructure forcing closures. However,  strictWith[ will additionally apply the given function to the map 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 xsJwill 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 invariants of the implementation hold for the given associative collection. If this function returns , it represents a bug; generally, either the implementation itself is flawed, or an unsafe operation has been used while violating the preconditions.eHReturns the name of the module implementing this associative collection.fbApply 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 elementthe key to look upthe associative collectionUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxy      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyf?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcde%&'()*+,-./0123456789:;<=> !"#$     ghijklmnopqrstuvwxy       !"#$%&'()*+,-./0123456789:;<=>?&@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxy!Copyright (c) 2006 Robert Dockins0MIT; see COPYRIGHT file for terms and conditionsrobdockins AT fastmail DOT fmstableGHC, Hugs (MPTC and FD)Safe79zWLeft (front) cons on a sequence. The new element appears on the left. Identical to .{XRight (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{|}~!Copyright (c) 2006 Robert Dockins0MIT; see COPYRIGHT file for terms and conditionsrobdockins AT fastmail DOT fmstableGHC, Hugs (MPTC and FD)Safe79 %??%       !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]ZX[ "#$!WY%&'()+*,-./0123456@ABCDEFGHIJ789:ST;<=>?KLMNOPQRU^_`abcdefghijkl)*+,-./0mnopABqC%&'(;<Trstuvwxyz{|}~X SUVZ!Wnmp`abcdefguwxijz|kl{})*+,-./0~ZX ABqCE%&'(;<STUVW!Ediso_8Q6tFBF6AHE4SCGfMwZ7ZLData.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