+]      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijk l m n o p q r s t u v w x y z { | } ~        !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\#portablestable+http://homepages.nildram.co.uk/~ahey/em.pngBasic data type. ]^%Read the current comparison counter. &Reset the comparison counter to zero. _"A side effecting instance of Ord. portablestable+http://homepages.nildram.co.uk/~ahey/em.png AVL tree data type. The balance factor (BF) of an > tree node is defined as the difference between the height of " the left and right sub-trees. An 0 tree is ALWAYS height balanced, such that |BF| <= 1.  The functions in this library ( Data.Tree.AVL,) are designed so that they never construct  an unbalanced tree (well that's assuming they're not broken). The  tree type defined here & has the BF encoded the constructors. &Some functions in this library return  trees that are also "flat", which (in the context ] of this library) means that the sizes of left and right sub-trees differ by at most one and ` are also flat. Flat sorted trees should give slightly shorter searches than sorted trees which a are merely height balanced. Whether or not flattening is worth the effort depends on the number H of times the tree will be searched and the cost of element comparison. >In cases where the tree elements are sorted, all the relevant  functions follow the V convention that the leftmost tree element is least and the rightmost tree element is W the greatest. Bear this in mind when defining general comparison functions. It should Y also be noted that all functions in this library for sorted trees require that the tree . does not contain multiple elements which are "equal"" (according to whatever criterion ' has been used to sort the elements). WIt is important to be consistent about argument ordering when defining general purpose M comparison functions (or selectors) for searching a sorted tree, such as ..   ! myComp :: (k -> e -> Ordering)  -- or.. $ myCComp :: (k -> e -> COrdering a) ]In these cases the first argument is the search key and the second argument is an element of  the  tree. For example..    key `myCComp` element -> Lt implies key <* element, proceed down the left sub-tree  key `myCComp`G element -> Gt implies key > element, proceed down the right sub-tree 7This convention is same as that used by the overloaded ` method from a class. WWARNING: The constructors of this data type are exported from this module but not from  the top level  wrapper ( Data.Tree.AVL). Don't try to construct your own   trees unless you'Cre sure you know what your doing. If you end up creating and using   trees that aren't you'0ll break most of the functions in this library. Controlling Strictness. The . data type is declared as non-strict in all it' s fields, L but all the functions in this library behave as though it is strict in its Q recursive fields (left and right sub-trees). Strictness in the element field is V controlled either by using the strict variants of functions (defined in this library L where appropriate), or using strict variants of the combinators defined in Data.COrdering,  or using bO etc. in your own code (in any combining comparisons you define, for example).  A note about c and a class instances. For  trees the defined instances of a and c0 are based on the lists that are produced using  the Data.Tree.AVL.List.asListL+ function (it could just as well have been Data.Tree.AVL.List.asListR, n the choice is arbitrary but I can only chose one). This means that two trees which contain the same elements m in the same order are equal regardless of detailed tree structure. The same principle has been applied to  the instances of d and eC. Unfortunately, this has the undesirable and non-intuitive effect  of making "equal"J trees potentially distinguishable using some functions (such as height). [ All such functions have been placed in the Data.Tree.AVL.Internals modules, which are not  included in the main  Data.Tree.AVL wrapper. For all "normal" functions (f) exported by  Data.Tree.AVL * it is safe to assume that if a and b are = trees then (a == b) implies (f a == f b), provided the same  is true for the tree elements. #BF=+1 (left height > right height) BF= 0 #BF=-1 (right height > left height)  Empty Tree f The empty AVL tree. Returns g if an AVL tree is empty. Complexity: O(1) Returns g if an AVL tree is non-empty. Complexity: O(1) +Creates an AVL tree with just one element. Complexity: O(1) MCreate an AVL tree of two elements, occuring in same order as the arguments. 5If the AVL tree is a singleton (has only one element e) then this function returns (h e).  Otherwise it returns Nothing. Complexity: O(1)        portablestable+http://homepages.nildram.co.uk/~ahey/em.pngi%Determine the height of an AVL tree. Complexity: O(log n) j1Adds the height of a tree to the first argument. Complexity: O(log n) kXA fast algorithm for comparing the heights of two trees. This algorithm avoids the need ^ to compute the heights of both trees and should offer better performance if the trees differ a significantly in height. But if you need the heights anyway it will be quicker to just evaluate $ them both and compare the results. KComplexity: O(log n), where n is the size of the smaller of the two trees. lOFast algorithm to calculate size. This avoids visiting about 50% of tree nodes N by using fact that trees with small heights can only have particular shapes.  So it'?s still O(n), but with substantial saving in constant factors. Complexity: O(n) mnopijklijklportablestable+http://homepages.nildram.co.uk/~ahey/em.png4Counts the total number of elements in an AVL tree. Complexity: O(n) /Adds the size of a tree to the first argument. Complexity: O(n) portablestable+http://homepages.nildram.co.uk/~ahey/em.pngq A version of pushLG for an AVL tree of known height. Returns an AVL tree of known height.  It'Us OK if height is relative, with fixed offset. In this case the height of the result " will have the same fixed offset. r A version of pushRG for an AVL tree of known height. Returns an AVL tree of known height.  It'Us OK if height is relative, with fixed offset. In this case the height of the result " will have the same fixed offset. s[Push a singleton tree (first arg) in the leftmost position of an AVL tree of known height, * returning an AVL tree of known height. It'/s OK if height is relative, with fixed offset. H In this case the height of the result will have the same fixed offset. Complexity: O(log n) t\Push a singleton tree (third arg) in the rightmost position of an AVL tree of known height, * returning an AVL tree of known height. It'/s OK if height is relative, with fixed offset. H In this case the height of the result will have the same fixed offset. Complexity: O(log n) qrstqrstportable experimentalpaul@cogito.org.uk ?A Boundary is a division of an ordered type into values above 9and below the boundary. No value can sit on a boundary. Known bug: for Bounded types  BoundaryAbove maxBound < BoundaryAboveAll )BoundaryBelow minBound > BoundaryBelowAll;This is incorrect because there are no possible values in 9between the left and right sides of these inequalities. The boundary below all values. The boundary above all values. 5The argument is the lowest value above the boundary. 6The argument is the highest value below the boundary. FDistinguish between dense and sparse ordered types. A dense type is one in which any two values v1 < v2 have a third value v3 such that v1 < v3 < v2. PIn theory the floating types are dense, although in practice they can only have 8finitely many values. This class treats them as dense. NTuples up to 4 members are declared as instances. Larger tuples may be added if necessary. IThis approach was suggested by Ben Rudiak-Gould on comp.lang.functional.  Two values x and y are adjacent if x < y and there does not + exist a third value between them. Always False for dense types. >Check adjacency for sparse enumerated types (i.e. where there  is no value between x and succ x). Use as the definition of  adjacent for most enumerated types. CCheck adjacency, allowing for case where x = maxBound. Use as the  definition of adjacent4 for bounded enumerated types such as Int and Char. :True if the value is above the boundary, false otherwise. Same as ;, but with the arguments reversed for more intuitive infix  usage.   portable experimentalpaul@cogito.org.uk(A Range has upper and lower boundaries. !"#'True if the value is within the range. $/True if the value is within one of the ranges. %The empty range &+The full range. All values are within it. '"A range containing a single value (EA range is empty unless its upper boundary is greater than its lower  boundary. )7Two ranges overlap if their intersection is non-empty. *KThe first range encloses the second if every value in the second range is I also within the first range. If the second range is empty then this is  always true. +$Intersection of two ranges, if any. ,2Union of two ranges. Returns one or two results. FIf there are two results then they are guaranteed to have a non-empty 4 gap in between, but may not be in ascending order. -range1 minus range20. Returns zero, one or two results. Multiple N results are guaranteed to have non-empty gaps in between, but may not be in  ascending order.  !"#$%&'()*+,- !"%&()*#$'+,- !" !"#$%&'()*+,-.IAn RSet (for Ranged Set) is a list of ranges. The ranges must be sorted  and not overlap. u/0KDetermine if the ranges in the list are both in order and non-overlapping. F If so then they are suitable input for the unsafeRangedSet function. 1IRearrange and merge the ranges in the list so that they are in order and  non-overlapping. v2ECreate a new Ranged Set from a list of ranges. The list may contain 4 ranges that overlap or are not in ascending order. 3/Create a new Ranged Set from a list of ranges. validRangeList ranges  must return True%. This precondition is not checked. 4+Create a Ranged Set from a single element. 5 True if the set has no members. w0True if the negation of the set has no members. 67ITrue if the value is within the ranged set. Infix precedence is left 5. 89FTrue if the first argument is a subset of the second argument, or is  equal. Infix precedence is left 5. :;FTrue if the first argument is a strict subset of the second argument. Infix precedence is left 5. <=8Set union for ranged sets. Infix precedence is left 6. >??Set intersection for ranged sets. Infix precedence is left 7. @A-Set difference. Infix precedence is left 6. BSet negation. CThe empty set. D"The set that contains everything. EConstruct a range set. A first lower boundary. BA function from a lower boundary to an upper boundary, which must : return a result greater than the argument (not checked). $A function from a lower boundary to Maybe the successor lower A boundary, which must return a result greater than the argument  (not checked). x./0123456789:;<=>?@ABCDE.//2301457698;:=<?>A@BCDE.//0123456789:;<=>?@ABCDE2 !"#$%&'()*+,-./0123456789:;<=>?@ABCDE/FA set of values a, implemented as bitwise operations. Useful F for members of class Enum with no more elements than there are bits  in Word. yGz{HO(1). Is this the empty set? IO(1)%. The number of elements in the set. JO(1). Is the element in the set? KO(1). The empty set. LO(1). Create a singleton set. MO(1). Insert an element in a set. B If the set already contains an element equal to the given value, $ it is replaced with the new value. NO(1) . Delete an element from a set. OO(1)9. Is this a proper subset? (ie. a subset but not equal). PO(1). Is this a subset?  (s1 P s2) tells whether s1 is a subset of s2. QThe minimal element of a set. |RThe maximal element of a set. }SDelete the minimal element. TDelete the maximal element. UVWThe union of a list of sets: (W == ~ X K). XO(1). The union of two sets. YO(1). Difference of two sets. ZO(1) . The intersection of two sets. [O(1)2. The complement of a set with its universe set.   complement; can be used with bounded types for which the universe set  will be automatically created. \]O(n)2. Filter all elements that satisfy the predicate. ^O(n)F. Partition the set into two sets, one with all elements that satisfy 1 the predicate and one with all elements that don't satisfy the predicate.  See also i. _O(n).  _ f s! is the set obtained by applying f to each element of s. It'>s worth noting that the size of the result may be smaller if,  for some (x,y), x /= y && f x == f y ``) is provided for compatibility with the  Data.Set interface. aO(n);. Fold over the elements of a set in an unspecified order. bcO(n). The elements of a set. dO(n)). Convert the set to a list of elements. eO(n)4. Convert the set to an ascending list of elements. fO(n)(. Create a set from a list of elements. g fromAscList and fromDistinctAscList maintained for compatibility , with Data.Set, but here give no advantage. hij%FGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghij%FGHIJPOKLMNXWYZ[\]^ij_`abQRSTUVcdfegh%FGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghij MPTC+FD experimental+jeanphilippe.bernardy (google mail address)&k$Data structures that can be folded. Minimal complete definition: m or n. For example, given a data type  9 data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a) a suitable instance would be   instance Foldable Tree  foldMap f Empty = mempty  foldMap f (Leaf x) = f x M foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r CThis is suitable even for abstract types, as the monoid is assumed  to satisfy the monoid laws. l4Combine the elements of a structure using a monoid. m/Map each element of the structure to a monoid,  and combine the results. n'Right-associative fold of a structure. n f z =  f z . o&Left-associative fold of a structure. o f z = ~ f z . p A variant of n that has no base case, 7 and thus may only be applied to non-empty structures. p f =  f . q A variant of o that has no base case, 7 and thus may only be applied to non-empty structures. q f =  f . r&Tells whether the structure is empty. s#Returns the size of the structure. t7Tells whether the structure contains a single element. u'Fold over the elements of a structure, ) associating to the right, but strictly. v/Monadic fold over the elements of a structure, 4 associating to the right, i.e. from right to left. w'Fold over the elements of a structure, ( associating to the left, but strictly. x/Monadic fold over the elements of a structure, 3 associating to the left, i.e. from left to right. y7Map each element of a structure to an action, evaluate ; these actions from left to right, and ignore the results. zz is y with its arguments flipped. {>Map each element of a structure to a monadic action, evaluate ; these actions from left to right, and ignore the results. || is { with its arguments flipped. }:Evaluate each action in the structure from left to right,  and ignore the results. ~BEvaluate each monadic action in the structure from left to right,  and ignore the results. 1The sum of a collection of actions, generalizing . 1The sum of a collection of actions, generalizing . !List of elements of a structure. ?The concatenation of all the elements of a container of lists. DMap a function over all the elements of a container and concatenate  the resulting lists. ; returns the conjunction of a container of Bools. For the  result to be g , the container must be finite;  , however,  results from a ' value finitely far from the left end. ; returns the disjunction of a container of Bools. For the  result to be  , the container must be finite; g , however,  results from a g' value finitely far from the left end. IDetermines whether any element of the structure satisfies the predicate. HDetermines whether all elements of the structure satisfy the predicate. The : function computes the sum of the numbers of a structure. The > function computes the product of the numbers of a structure. &The largest element of the structure. AThe largest element of a non-empty structure with respect to the  given comparison function. +The least element of a non-null structure. ?The least element of a non-empty structure with respect to the  given comparison function. )Does the element occur in the structure?  is the negation of . The 8 function takes a predicate and a structure and returns B the leftmost element of the structure matching the predicate, or   if there is no such element. $klmnopqrstuvwxyz{|}~$klmnopqrstuwvxyz}{|~$k lmnopqrstlmnopqrstuvwxyz{|}~ portablestable+http://homepages.nildram.co.uk/~ahey/em.png"Result of a combining comparison. *A combining comparison for an instance of a* which returns unit () where appropriate. *unitCC a b = case compare a b of LT -> Lt - EQ -> Eq () * GT -> Gt bCreate a combining comparison from an ordinary comparison by returning unit () where appropriate. ,unitByCC cmp a b = case cmp a b of LT -> Lt / EQ -> Eq () , GT -> Gt *A combining comparison for an instance of a which keeps the first argument K if they are deemed equal. The second argument is discarded in this case. +fstCC a a' = case compare a a' of LT -> Lt - EQ -> Eq a + GT -> Gt XCreate a combining comparison from an ordinary comparison by keeping the first argument K if they are deemed equal. The second argument is discarded in this case. +fstByCC cmp a b = case cmp a b of LT -> Lt - EQ -> Eq a + GT -> Gt *A combining comparison for an instance of a! which keeps the second argument J if they are deemed equal. The first argument is discarded in this case. +sndCC a a' = case compare a a' of LT -> Lt . EQ -> Eq a' + GT -> Gt YCreate a combining comparison from an ordinary comparison by keeping the second argument J if they are deemed equal. The first argument is discarded in this case. +sndByCC cmp a b = case cmp a b of LT -> Lt - EQ -> Eq b + GT -> Gt YCreate a combining comparison using the supplied combining function, which is applied if  ` returns . See * for a stricter version of this function. .withCC f a a' = case compare a a' of LT -> Lt 7 EQ -> Eq (f a a') . GT -> Gt Same as 5, except the combining function is applied strictly. /withCC' f a a' = case compare a a' of LT -> Lt K EQ -> let b = f a a' in b `seq` Eq b / GT -> Gt TCreate a combining comparison using the supplied comparison and combining function, , which is applied if the comparison returns . See  for a stricter version  of this function. .withByCC cmp f a b = case cmp a b of LT -> Lt 6 EQ -> Eq (f a b) . GT -> Gt Same as 5, except the combining function is applied strictly. /withByCC' cmp f a b = case cmp a b of LT -> Lt J EQ -> let c = f a b in c `seq` Eq c / GT -> Gt IConverts a comparison to one which takes arguments in flipped order, but 3 preserves the ordering that would be given by the " unflipped"% version (disregarding type issues).  So it'$s not the same as using the prelude * (which would reverse the ordering too). )flipC cmp b a = case cmp a b of LT -> GT ) EQ -> EQ ) GT -> LT SConverts a combining comparison to one which takes arguments in flipped order, but 3 preserves the ordering that would be given by the " unflipped"% version (disregarding type issues).  So it'$s not the same as using the prelude * (which would reverse the ordering too). 0flipCC cmp b a = case cmp a b of Lt -> Gt / e@(Eq _) -> e 0 Gt -> Lt  portablestable+http://homepages.nildram.co.uk/~ahey/em.png !Read the leftmost element from a  non-empty- tree. Raises an error if the tree is empty. ; If the tree is sorted this will return the least element. Complexity: O(log n)  Similar to  but returns  if the tree is empty. Complexity: O(log n) "Read the rightmost element from a  non-empty- tree. Raises an error if the tree is empty. > If the tree is sorted this will return the greatest element. Complexity: O(log n)  Similar to  but returns  if the tree is empty. Complexity: O(log n) \General purpose function to perform a search of a sorted tree, using the supplied selector. 3 This function raises a error if the search fails. Complexity: O(log n) \General purpose function to perform a search of a sorted tree, using the supplied selector.  This function is similar to , but returns  if the search failed. Complexity: O(log n) BThis version returns the result of the selector (without adding a h wrapper) if the search  succeeds, or  if it fails. Complexity: O(log n) \General purpose function to perform a search of a sorted tree, using the supplied selector.  This function is similar to 6, but returns a the default value (first argument) if  the search fails. Complexity: O(log n) \General purpose function to perform a search of a sorted tree, using the supplied selector. , Returns True if matching element is found. Complexity: O(log n) portablestable+http://homepages.nildram.co.uk/~ahey/em.pngInt fields are search depth and  path bits respecively. The  path bits consist of a  a string of depthI bits, left justified. MSB of 0 means go left, MSB of 1 means go right. TFind the path to a AVL tree element, returns -1 (invalid path) if element not found Complexity: O(log n) ;Get the BinPath of an element using the supplied selector. Complexity: O(log n) GGet the BinPath of an element using the supplied (combining) selector. Complexity: O(log n) DOverwrite a tree element. Assumes the path bits were extracted from  constructor. 5 Raises an error if the path leads to an empty tree. EN.B This operation does not change tree shape (no insertion occurs). Complexity: O(log n) ?Read a tree element. Assumes the path bits were extracted from  constructor. 5 Raises an error if the path leads to an empty tree. Complexity: O(log n) HInserts a new tree element. Assumes the path bits were extracted from a  constructor. _ This function replaces the first Empty node it encounters with the supplied value, regardless b of the current path bits (which are not checked). DO NOT USE THIS FOR REPLACING ELEMENTS ALREADY  PRESENT IN THE TREE (use  for this). Complexity: O(log n)   portablestable+http://homepages.nildram.co.uk/~ahey/em.pngGReplace the left most element of a tree with the supplied new element. < This function raises an error if applied to an empty tree. Complexity: O(log n)  Similar to , but returns  if applied to an empty tree. Complexity: O(log n) HReplace the right most element of a tree with the supplied new element. < This function raises an error if applied to an empty tree. Complexity: O(log n)  Similar to , but returns  if applied to an empty tree. Complexity: O(log n) WA general purpose function to perform a search of a tree, using the supplied selector. D If the search succeeds the found element is replaced by the value (e ) of the (c e) d constructor returned by the selector. If the search fails this function returns the original tree. Complexity: O(log n) Functionally identical to ;, but returns an identical tree (one with all the nodes on ] the path duplicated) if the search fails. This should probably only be used if you know the ^ search will succeed and will return an element which is different from that already present. Complexity: O(log n) WA general purpose function to perform a search of a tree, using the supplied selector. - The found element is replaced by the value (e ) of the (c e) constructor returned by % the selector. This function returns  if the search failed. Complexity: O(log n)  Similar to @, but also returns the original tree if the search succeeds but  the selector returns (c )5. (This version is intended to help reduce heap burn  rate if it'7s likely that no modification of the value is needed.) Complexity: O(log n)  Similar to @, but also returns the original tree if the search succeeds but  the selector returns (c )5. (This version is intended to help reduce heap burn  rate if it'7s likely that no modification of the value is needed.) Complexity: O(log n) portablestable+http://homepages.nildram.co.uk/~ahey/em.pngeGeneral push. This function searches the AVL tree using the supplied selector. If a matching element  is found it's replaced by the value (e) returned in the (c e)' constructor returned by the selector. j If no match is found then the default element value is added at in the appropriate position in the tree. bNote that for this to work properly requires that the selector behave as if it were comparing the N (potentially) new default element with existing tree elements, even if it isn't.  Note also that this function is  non-strict in it'+s second argument (the default value which V is inserted if the search fails or is discarded if the search succeeds). If you want $ to force evaluation, but only if it'-s actually incorprated in the tree, then use  Complexity: O(log n) Almost identical to @, but this version forces evaluation of the default new element F (second argument) if no matching element is found. Note that it does not do this if X a matching element is found, because in this case the default new element is discarded ^ anyway. Note also that it does not force evaluation of any replacement value provided by the C selector (if it returns Eq). (You have to do that yourself if that's what you want.) Complexity: O(log n)  Similar to D, but returns the original tree if the combining comparison returns  (c )M. So this function can be used reduce heap burn rate by avoiding duplication Q of nodes on the insertion path. But it may also be marginally slower otherwise. Note that this function is  non-strict in it'+s second argument (the default value which V is inserted in the search fails or is discarded if the search succeeds). If you want $ to force evaluation, but only if it'-s actually incorprated in the tree, then use  Complexity: O(log n) Almost identical to @, but this version forces evaluation of the default new element F (second argument) if no matching element is found. Note that it does not do this if X a matching element is found, because in this case the default new element is discarded  anyway. Complexity: O(log n) dPush a new element in the leftmost position of an AVL tree. No comparison or searching is involved. Complexity: O(log n) ePush a new element in the rightmost position of an AVL tree. No comparison or searching is involved. Complexity: O(log n) portablestable+http://homepages.nildram.co.uk/~ahey/em.png&/List AVL tree contents in left to right order. > The resulting list in ascending order if the tree is sorted. Complexity: O(n) GJoin the AVL tree contents to an existing list in left to right order. A This is a ++ free function which behaves as if defined thusly..  ) avl `toListL` as = (asListL avl) ++ as Complexity: O(n) /List AVL tree contents in right to left order. ? The resulting list in descending order if the tree is sorted. Complexity: O(n) GJoin the AVL tree contents to an existing list in right to left order. A This is a ++ free function which behaves as if defined thusly..  ) avl `toListR` as = (asListR avl) ++ as Complexity: O(n) The AVL equivalent of G on lists. This is a the lazy version (as lazy as the folding function A anyway). Using this version with a function that is strict in it'&s second argument will result in O(n)  stack use. See  for a strict version. It behaves as if defined..  , foldrAVL f a avl = foldr f a (asListL avl) For example, the  function could be defined..   asListL = foldrAVL (:) [] Complexity: O(n) The strict version of A, which is useful for functions which are strict in their second f argument. The advantage of this version is that it reduces the stack use from the O(n) that the lazy > version gives (when used with strict functions) to O(log n). Complexity: O(n) The AVL equivalent of G on lists. This is a the lazy version (as lazy as the folding function A anyway). Using this version with a function that is strict in it'&s second argument will result in O(n)  stack use. See  for a strict version.  * foldr1AVL f avl = foldr1 f (asListL avl) 4This function raises an error if the tree is empty. Complexity: O(n) The strict version of A, which is useful for functions which are strict in their second f argument. The advantage of this version is that it reduces the stack use from the O(n) that the lazy > version gives (when used with strict functions) to O(log n). Complexity: O(n) This fold is a hybrid between  and  . As with , it requires a a non-empty tree, but instead of treating the rightmost element as an initial value, it applies V a function to it (second function argument) and uses the result instead. This allows O a more flexible type for the main folding function (same type as that used by ).  As with  and , this function is lazy, so it'$s best not to use it with functions / that are strict in their second argument. See  for a strict version. Complexity: O(n) The strict version of A, which is useful for functions which are strict in their second f argument. The advantage of this version is that it reduces the stack use from the O(n) that the lazy > version gives (when used with strict functions) to O(log n). Complexity: O(n) The AVL equivalent of ~G on lists. This is a the lazy version (as lazy as the folding function A anyway). Using this version with a function that is strict in it'%s first argument will result in O(n)  stack use. See  for a strict version.  , foldlAVL f a avl = foldl f a (asListL avl) For example, the  function could be defined..  " asListR = foldlAVL (flip (:)) [] Complexity: O(n) The strict version of @, which is useful for functions which are strict in their first f argument. The advantage of this version is that it reduces the stack use from the O(n) that the lazy > version gives (when used with strict functions) to O(log n). Complexity: O(n) The AVL equivalent of G on lists. This is a the lazy version (as lazy as the folding function A anyway). Using this version with a function that is strict in it'%s first argument will result in O(n)  stack use. See  for a strict version.  * foldl1AVL f avl = foldl1 f (asListL avl) 4This function raises an error if the tree is empty. Complexity: O(n) The strict version of @, which is useful for functions which are strict in their first f argument. The advantage of this version is that it reduces the stack use from the O(n) that the lazy > version gives (when used with strict functions) to O(log n). Complexity: O(n) This fold is a hybrid between  and  . As with , it requires ` a non-empty tree, but instead of treating the leftmost element as an initial value, it applies V a function to it (second function argument) and uses the result instead. This allows O a more flexible type for the main folding function (same type as that used by ).  As with  and , this function is lazy, so it'$s best not to use it with functions . that are strict in their first argument. See  for a strict version. Complexity: O(n) The strict version of @, which is useful for functions which are strict in their first f argument. The advantage of this version is that it reduces the stack use from the O(n) that the lazy > version gives (when used with strict functions) to O(log n). Complexity: O(n) XConvert a list of known length into an AVL tree, such that the head of the list becomes ] the leftmost tree element. The resulting tree is flat (and also sorted if the supplied list  is sorted in ascending order). MIf the actual length of the list is not the same as the supplied length then  an error will be raised. Complexity: O(n) As G, except the length of the list is calculated internally, not supplied  as an argument. Complexity: O(n) XConvert a list of known length into an AVL tree, such that the head of the list becomes ^ the rightmost tree element. The resulting tree is flat (and also sorted if the supplied list ! is sorted in descending order). MIf the actual length of the list is not the same as the supplied length then  an error will be raised. Complexity: O(n) As G, except the length of the list is calculated internally, not supplied  as an argument. Complexity: O(n) CReverse an AVL tree (swaps and reverses left and right sub-trees). 9 The resulting tree is the mirror image of the original. Complexity: O(n) ZApply a function to every element in an AVL tree. This function preserves the tree shape. 2 There is also a strict version of this function (). ON.B. If the tree is sorted the result of this operation will only be sorted if R the applied function preserves ordering (for some suitable ordering definition). Complexity: O(n)  Similar to 1, but the supplied function is applied strictly. Complexity: O(n) NConstruct a flat AVL tree of size n (n>=0), where all elements are identical. Complexity: O(log n) CFlatten an AVL tree, preserving the ordering of the tree elements. Complexity: O(n)  Similar to H, but the tree elements are reversed. This function has higher constant  factor overhead than . Complexity: O(n)  Similar to ", but the resulting tree is flat. 8 This function has higher constant factor overhead than . Complexity: O(n) Same as 1, but the supplied function is applied strictly. Complexity: O(n) JRemove all AVL tree elements which do not satisfy the supplied predicate. < Element ordering is preserved. The resulting tree is flat. Complexity: O(n) NPartition an AVL tree using the supplied predicate. The first AVL tree in the R resulting pair contains all elements for which the predicate is True, the second U contains all those for which the predicate is False. Element ordering is preserved. ' Both of the resulting trees are flat. Complexity: O(n) ERemove all AVL tree elements for which the supplied function returns . < Element ordering is preserved. The resulting tree is flat. Complexity: O(n) Invokes  on the empty AVL tree. Complexity: O(n.(log n)) dPush the elements of an unsorted List in a sorted AVL tree using the supplied combining comparison. NComplexity: O(n.(log (m+n))) where n is the list length, m is the tree size. SUses the supplied combining comparison to sort list elements into ascending order. Y Multiple occurences of the same element are eliminated (they are combined in some way). Complexity: O(n.(log n)) TUses the supplied combining comparison to sort list elements into descending order. Y Multiple occurences of the same element are eliminated (they are combined in some way). Complexity: O(n.(log n)) $$$portablestable+http://homepages.nildram.co.uk/~ahey/em.pngQAVL Tree test data. Each element of a the list is a pair consisting of a height, T and list of all possible sorted trees of the same height, paired with their sizes. 1 The elements of each tree of size s are 0..s-1. ?Infinite test tree. Used for test purposes for BinPath module. . Value at each node is the path to that node. OVerify that a tree is height balanced and that the BF of each node is correct. Complexity: O(n) CVerify that a tree is balanced and the BF of each node is correct. 1 Returns (Just height) if so, otherwise Nothing. Complexity: O(n) Verify that a tree is sorted. Complexity: O(n) RVerify that a tree is sorted, height balanced and the BF of each node is correct. Complexity: O(n)  All possible sorted AVL trees. Same as ., but excluding the empty tree (of height 0). <Returns the number of possible AVL trees of a given height. Behaves as if defined..  3 numTrees h = (\(_,xs) -> length xs) (allAVL !! h) )and satisfies this recurrence relation..   numTrees 0 = 1  numTrees 1 = 1 J numTrees h = (2*(numTrees (h-2)) + (numTrees (h-1))) * (numTrees (h-1)) OApply the test function to each AVL tree in the TestTrees argument, and report M progress as test proceeds. The first two arguments of the test function are $ tree height and size respectively. /Generates a flat AVL tree of n elements [0..n-1]. KDetetermine the minimum number of elements in an AVL tree of given height. 4 This function satisfies this recurrence relation..   minElements 0 = 0  minElements 1 = 1 ; minElements h = 1 + minElements (h-1) + minElements (h-2) B -- = Some weird expression involving the golden ratio KDetetermine the maximum number of elements in an AVL tree of given height. 4 This function satisfies this recurrence relation..   maxElements 0 = 0 6 maxElements h = 1 + 2 * maxElements (h-1) -- = 2^h-1  portablestable+http://homepages.nildram.co.uk/~ahey/em.pngNDDeletes a tree element. Assumes the path bits were extracted from a FullBP constructor. Complexity: O(log n) !!portablestable+http://homepages.nildram.co.uk/~ahey/em.png"Delete the left-most element of a  non-empty2 AVL tree. If the tree is sorted this will be the 3 least element. This function raises an error if it's argument is an empty tree. Complexity: O(log n) )Try to delete the left-most element of a  non-empty2 AVL tree. If the tree is sorted this will be the & least element. This function returns  if it's argument is an empty tree. Complexity: O(log n) #Delete the right-most element of a  non-empty2 AVL tree. If the tree is sorted this will be the 6 greatest element. This function raises an error if it's argument is an empty tree. Complexity: O(log n) *Try to delete the right-most element of a  non-empty2 AVL tree. If the tree is sorted this will be the ) greatest element. This function returns  if it's argument is an empty tree. Complexity: O(log n) ZPop the left-most element from a non-empty AVL tree, returning the popped element and the J modified AVL tree. If the tree is sorted this will be the least element. $ This function raises an error if it's argument is an empty tree. Complexity: O(log n) Same as , except this version returns  if it's argument is an empty tree. Complexity: O(log n) [Pop the right-most element from a non-empty AVL tree, returning the popped element and the M modified AVL tree. If the tree is sorted this will be the greatest element. $ This function raises an error if it's argument is an empty tree. Complexity: O(log n) Same as , except this version returns  if it's argument is an empty tree. Complexity: O(log n) JGeneral purpose function for deletion of elements from a sorted AVL tree. R If a matching element is not found then this function returns the original tree. Complexity: O(log n) GThis version only deletes the element if the supplied selector returns (c g).  If it returns (c )? or if no matching element is found then this function returns  the original tree. Complexity: O(log n) GThis version only deletes the element if the supplied selector returns (c ).  If it returns (c (h e)). then the matching element is replaced by e. O If no matching element is found then this function returns the original tree. Complexity: O(log n) Functionally identical to ;, but returns an identical tree (one with all the nodes on ] the path duplicated) if the search fails. This should probably only be used if you know the  search will succeed. Complexity: O(log n) FGeneral purpose function for popping elements from a sorted AVL tree. J An error is raised if a matching element is not found. The pair returned F by this function consists of the popped value and the modified tree. Complexity: O(log n)  Similar to genPop, but this function returns  if the search fails. Complexity: O(log n) CIn this case the selector returns two values if a search succeeds.  If the second is (h e) then the new value (e0) is substituted in the same place in the tree.  If the second is 1 then the corresponding tree element is deleted. 4 This function raises an error if the search fails. Complexity: O(log n)  Similar to , but returns  if the search fails. Complexity: O(log n) A simpler version of ;. The corresponding element is deleted if the second value  returned by the selector is g. If it's !, the original tree is returned. 4 This function raises an error if the search fails. Complexity: O(log n)  Similar to genPopIf, but returns  if the search fails. Complexity: O(log n) !portablestable+http://homepages.nildram.co.uk/~ahey/em.png7Join two trees of known height, returning an AVL tree.  It'Es OK if heights are relative (I.E. if they share same fixed offset). FComplexity: O(d), where d is the absolute difference in tree heights. KJoin two AVL trees of known height, returning an AVL tree of known height.  It'Es OK if heights are relative (I.E. if they share same fixed offset). FComplexity: O(d), where d is the absolute difference in tree heights. JSplice two AVL trees of known height using the supplied bridging element. ' That is, the bridging element appears " in the middle" of the resulting AVL tree. U The elements of the first tree argument are to the left of the bridging element and K the elements of the second tree are to the right of the bridging element. VThis function does not require that the AVL heights are absolutely correct, only that W the difference in supplied heights is equal to the difference in actual heights. So it's X OK if the input heights both have the same unknown constant offset. (The output height 8 will also have the same constant offset in this case.) FComplexity: O(d), where d is the absolute difference in tree heights.     portablestable+http://homepages.nildram.co.uk/~ahey/em.png  8Join two AVL trees. This is the AVL equivalent of (++).  / asListL (l `join` r) = asListL l ++ asListL r KComplexity: O(log n), where n is the size of the larger of the two trees. Concatenate a finiteB list of AVL trees. During construction of the resulting tree the ` input list is consumed lazily, but it will be consumed entirely before the result is returned.  3 asListL (concatAVL avls) = concatMap asListL avls WComplexity: Umm..Dunno. Uses a divide and conquer approach to splice adjacent pairs of [ trees in the list recursively, until only one tree remains. The complexity of each splice 4 is proportional to the difference in tree heights.  Similar to %, except the resulting tree is flat. R This function evaluates the entire list of trees before constructing the result. QComplexity: O(n), where n is the total number of elements in the resulting tree. portablestable+http://homepages.nildram.co.uk/~ahey/em.pngQA 4 is like a pointer reference to somewhere inside an  tree. It may be either "full" F (meaning it points to an actual tree node containing an element), or "empty" (meaning it H points to the position in a tree where an element was expected but wasn' t found). :Abstract data type for an unsuccessfully opened AVL tree. < A PAVL can be tought of as a functional pointer to the gap . where the expected element should be (but isn' t). You can fill this gap using  the  8 function, or fill and close at the same time using the   function. ?Abstract data type for a successfully opened AVL tree. All ZAVL's are non-empty! I A ZAVL can be tought of as a functional pointer to an AVL tree element.  !"#UOpens a sorted AVL tree at the element given by the supplied selector. This function ? raises an error if the tree does not contain such an element. Complexity: O(log n) RAttempts to open a sorted AVL tree at the element given by the supplied selector.  This function returns  if there is no such element. VNote that this operation will still create a zipper path structure on the heap (which Z is promptly discarded) if the search fails, and so is potentially inefficient if failure 7 is likely. In cases like this it may be better to use * , test for "fullness"  using , and then convert to a  using 2. Complexity: O(log n) eAttempts to open a sorted AVL tree at the least element which is greater than or equal, according to . the supplied selector. This function returns / if the tree does not contain such an element. Complexity: O(log n) eAttempts to open a sorted AVL tree at the greatest element which is less than or equal, according to f the supplied selector. This function returns _Nothing_ if the tree does not contain such an element. Complexity: O(log n) 4Opens a non-empty AVL tree at the leftmost element. 5 This function raises an error if the tree is empty. Complexity: O(log n) ?Attempts to open a non-empty AVL tree at the leftmost element.  This function returns  if the tree is empty. Complexity: O(log n) $%&5Opens a non-empty AVL tree at the rightmost element. 5 This function raises an error if the tree is empty. Complexity: O(log n) @Attempts to open a non-empty AVL tree at the rightmost element.  This function returns  if the tree is empty. Complexity: O(log n) '()Returns (* zavl)$ if the expected element was found, (+ pavl) if the # expected element was not found. It'*s OK to use this function on empty trees. Complexity: O(log n)  Fill the gap pointed to by a * with the supplied element, which becomes & the current element of the resulting &. The supplied filling element should  be "equal"3 to the value used in the search which created the . Complexity: O(1)  "Essentially the same operation as  , but the resulting  is closed  immediately. Complexity: O(log n)  Closes a Zipper. Complexity: O(log n)  8Deletes the current element and then closes the Zipper. Complexity: O(log n)  &Gets the current element of a Zipper. Complexity: O(1) ,Overwrites the current element of a Zipper. Complexity: O(1) @Applies a function to the current element of a Zipper (lazily).  See also ( for a strict version of this function. Complexity: O(1) @Applies a function to the current element of a Zipper strictly.  See also , for a non-strict version of this function. Complexity: O(1) Moves one step left. W This function raises an error if the current element is already the leftmost element. /Complexity: O(1) average, O(log n) worst case.  Attempts to move one step left.  This function returns 9 if the current element is already the leftmost element. /Complexity: O(1) average, O(log n) worst case. Moves one step right. X This function raises an error if the current element is already the rightmost element. /Complexity: O(1) average, O(log n) worst case. !Attempts to move one step right.  This function returns : if the current element is already the rightmost element. /Complexity: O(1) average, O(log n) worst case. Returns g1 if the current element is the leftmost element. /Complexity: O(1) average, O(log n) worst case. Returns g2 if the current element is the rightmost element. /Complexity: O(1) average, O(log n) worst case. DInserts a new element to the immediate left of the current element. /Complexity: O(1) average, O(log n) worst case. LInserts a new element to the immediate left of the current element and then S moves one step left (so the newly inserted element becomes the current element). /Complexity: O(1) average, O(log n) worst case. EInserts a new element to the immediate right of the current element. /Complexity: O(1) average, O(log n) worst case. MInserts a new element to the immediate right of the current element and then T moves one step right (so the newly inserted element becomes the current element). /Complexity: O(1) average, O(log n) worst case. EInserts a new AVL tree to the immediate left of the current element. @Complexity: O(log n), where n is the size of the inserted tree. ,FInserts a new AVL tree to the immediate right of the current element. @Complexity: O(log n), where n is the size of the inserted tree. -5Deletes the current element and moves one step left. W This function raises an error if the current element is already the leftmost element. /Complexity: O(1) average, O(log n) worst case. ?Attempts to delete the current element and move one step left.  This function returns 9 if the current element is already the leftmost element. /Complexity: O(1) average, O(log n) worst case. 6Deletes the current element and moves one step right. X This function raises an error if the current element is already the rightmost element. /Complexity: O(1) average, O(log n) worst case.  @Attempts to delete the current element and move one step right.  This function returns : if the current element is already the rightmost element. /Complexity: O(1) average, O(log n) worst case. !8Delete all elements to the left of the current element. Complexity: O(log n) "9Delete all elements to the right of the current element. Complexity: O(log n) # Similar to !G, in that all elements to the left of the current element are deleted, 8 but this function also closes the tree in the process. Complexity: O(log n) $ Similar to "H, in that all elements to the right of the current element are deleted, 8 but this function also closes the tree in the process. Complexity: O(log n) % Similar to #/, but in this case the current element and all 7 those to the left of the current element are deleted. Complexity: O(log n) & Similar to $/, but in this case the current element and all 8 those to the right of the current element are deleted. Complexity: O(log n) 'ACounts the number of elements to the left of the current element . (this does not include the current element). /Complexity: O(n), where n is the count result. (BCounts the number of elements to the right of the current element . (this does not include the current element). /Complexity: O(n), where n is the count result. )/Counts the total number of elements in a ZAVL. Complexity: O(n) *Search for an element in a sorted # tree using the supplied selector.  Returns a "full" 7 if a matching element was found, otherwise returns an "empty" . Complexity: O(log n) +.Returns the original tree, extracted from the '. Typically you will not need this, as 9 the original tree will still be in scope in most cases. Complexity: O(1) ,Returns g if the  is "full"& (a corresponding element was found). Complexity: O(1) -Returns g if the  is "empty"' (no corresponding element was found). Complexity: O(1) .Read the element value from a "full" .  This function returns  if applied to an "empty" . Complexity: O(1) /Read the element value from a "full" . 0 This function raises an error if applied to an "empty" . Complexity: O(1) 0If the  is "full"A, this function returns the original tree with the corresponding < element replaced by the new element (first argument). If it's "empty" the original tree is returned  with the new element inserted. Complexity: O(log n) 1If the  is "full"A, this function returns the original tree with the corresponding  element deleted. If it's "empty"+ the original tree is returned unmodified. +Complexity: O(log n) (or O(1) for an empty ) 2 Converts a "full"  as a #. Raises an error if applied to an "empty" . Complexity: O(log n) .3 Converts an "empty"  as a ". Raises an error if applied to a "full" . Complexity: O(log n) /4 Converts a  to either a  or  (depending on whether it is "empty" or "full"). Complexity: O(log n) 8      !"#$%&'()*+,-./012348      !"#$%&'()*+,-./012348      !"#$%&'()*+,-./01234"portablestable+http://homepages.nildram.co.uk/~ahey/em.png 00An HAVL represents an AVL tree of known height. 12Empty HAVL (height is 0). 3Returns gK if the AVL component of an HAVL tree is empty. Note that height component  is ignored, so it'As OK to use this function in cases where the height is relative. Complexity: O(1) 4Returns gO if the AVL component of an HAVL tree is non-empty. Note that height component  is ignored, so it'As OK to use this function in cases where the height is relative. Complexity: O(1) 5Converts an AVL to HAVL 6;Splice two HAVL trees using the supplied bridging element. ' That is, the bridging element appears  in the middle of the resulting HAVL tree. U The elements of the first tree argument are to the left of the bridging element and K the elements of the second tree are to the right of the bridging element. VThis function does not require that the AVL heights are absolutely correct, only that W the difference in supplied heights is equal to the difference in actual heights. So it's X OK if the input heights both have the same unknown constant offset. (The output height 8 will also have the same constant offset in this case.) FComplexity: O(d), where d is the absolute difference in tree heights. 7Join two HAVL trees.  It'Es OK if heights are relative (I.E. if they share same fixed offset). FComplexity: O(d), where d is the absolute difference in tree heights. 8 A version of pushL for HAVL trees.  It'Us OK if height is relative, with fixed offset. In this case the height of the result " will have the same fixed offset. 9 A version of pushR for HAVL trees.  It'Us OK if height is relative, with fixed offset. In this case the height of the result " will have the same fixed offset. 0123456789 01123456789portablestable+http://homepages.nildram.co.uk/~ahey/em.png;:;<=>?@ABCDE5%Split an AVL tree from the Left. The F0 argument n (n >= 0) specifies the split point. 1 This function raises an error if n is negative. PIf the tree size is greater than n the result is (Right (l,r)) where l contains ` the leftmost n elements and r contains the remaining rightmost elements (r will be non-empty). _If the tree size is less than or equal to n then the result is (Left s), where s is tree size. 6An empty tree will always yield a result of (Left 0). Complexity: O(n) GH6&Split an AVL tree from the Right. The F1 argument n (n >= 0) specifies the split point. 1 This function raises an error if n is negative. PIf the tree size is greater than n the result is (Right (l,r)) where r contains ` the rightmost n elements and l contains the remaining leftmost elements (l will be non-empty). _If the tree size is less than or equal to n then the result is (Left s), where s is tree size. 6An empty tree will always yield a result of (Left 0). Complexity: O(n) IJ7 This is a simplified version of 5+ which does not return the remaining tree.  The FO argument n (n >= 0) specifies the number of elements to take (from the left). 1 This function raises an error if n is negative. LIf the tree size is greater than n the result is (Right l) where l contains  the leftmost n elements. _If the tree size is less than or equal to n then the result is (Left s), where s is tree size. 6An empty tree will always yield a result of (Left 0). Complexity: O(n) KL8 This is a simplified version of 6+ which does not return the remaining tree.  The FP argument n (n >= 0) specifies the number of elements to take (from the right). 1 This function raises an error if n is negative. LIf the tree size is greater than n the result is (Right r) where r contains  the rightmost n elements. _If the tree size is less than or equal to n then the result is (Left s), where s is tree size. 6An empty tree will always yield a result of (Left 0). Complexity: O(n) MN9 This is a simplified version of 5= which returns the remaining tree only (rightmost elements). 1 This function raises an error if n is negative. LIf the tree size is greater than n the result is (Right r) where r contains / the remaining elements (r will be non-empty). _If the tree size is less than or equal to n then the result is (Left s), where s is tree size. 6An empty tree will always yield a result of (Left 0). Complexity: O(n) OP: This is a simplified version of 6< which returns the remaining tree only (leftmost elements). 1 This function raises an error if n is negative. LIf the tree size is greater than n the result is (Right l) where l contains / the remaining elements (l will be non-empty). _If the tree size is less than or equal to n then the result is (Left s), where s is tree size. 6An empty tree will always yield a result of (Left 0). Complexity: O(n) QR;TSpan an AVL tree from the left, using the supplied predicate. This function returns Q a pair of trees (l,r), where l contains the leftmost consecutive elements which P satisfy the predicate. The leftmost element of r (if any) is the first to fail [ the predicate. Either of the resulting trees may be empty. Element ordering is preserved. ,Complexity: O(n), where n is the size of l. <USpan an AVL tree from the right, using the supplied predicate. This function returns R a pair of trees (l,r), where r contains the rightmost consecutive elements which Q satisfy the predicate. The rightmost element of l (if any) is the first to fail [ the predicate. Either of the resulting trees may be empty. Element ordering is preserved. ,Complexity: O(n), where n is the size of r. = This is a simplified version of ;* which does not return the remaining tree O The result is the leftmost consecutive sequence of elements which satisfy the * supplied predicate (which may be empty). 5Complexity: O(n), where n is the size of the result. > This is a simplified version of <* which does not return the remaining tree P The result is the rightmost consecutive sequence of elements which satisfy the * supplied predicate (which may be empty). 5Complexity: O(n), where n is the size of the result. ? This is a simplified version of ;+ which does not return the tree containing 4 the elements which satisfy the supplied predicate. _ The result is a tree whose leftmost element is the first to fail the predicate, starting from  the left (which may be empty). =Complexity: O(n), where n is the number of elements dropped. @ This is a simplified version of <+ which does not return the tree containing 4 the elements which satisfy the supplied predicate. ` The result is a tree whose rightmost element is the first to fail the predicate, starting from ! the right (which may be empty). =Complexity: O(n), where n is the number of elements dropped. A[Rotate an AVL tree one place left. This function pops the leftmost element and pushes into = the rightmost position. An empty tree yields an empty tree. Complexity: O(log n) B]Rotate an AVL tree one place right. This function pops the rightmost element and pushes into < the leftmost position. An empty tree yields an empty tree. Complexity: O(log n) C Similar to AD, but returns the rotated element. This function raises an error if  applied to an empty tree. Complexity: O(log n) SD Similar to BD, but returns the rotated element. This function raises an error if  applied to an empty tree. Complexity: O(log n) TETRotate an AVL tree left by n places. If s is the size of the tree then ordinarily n  should be in the range [0..s-1]7. However, this function will deliver a correct result  for any n (n<0 or n>+=s), the actual rotation being given by (n `mod` s) in such cases. 9 The result of rotating an empty tree is an empty tree. Complexity: O(n) UVFURotate an AVL tree right by n places. If s is the size of the tree then ordinarily n  should be in the range [0..s-1]7. However, this function will deliver a correct result  for any n (n<0 or n>+=s), the actual rotation being given by (n `mod` s) in such cases. 9 The result of rotating an empty tree is an empty tree. Complexity: O(n) WXG^Divide a sorted AVL tree into left and right sorted trees (l,r), such that l contains all the p elements less than or equal to according to the supplied selector and r contains all the elements greater than % according to the supplied selector. Complexity: O(log n) H^Divide a sorted AVL tree into left and right sorted trees (l,r), such that l contains all the c elements less than supplied selector and r contains all the elements greater than or equal to the  supplied selector. Complexity: O(log n) I Similar to G and H2, but returns any equal element found (instead of E incorporating it into the left or right tree results respectively). Complexity: O(log n) J This is a simplified version of G( which returns a sorted tree containing Z only those elements which are less than or equal to according to the supplied selector. $ This function also has the synonym K. Complexity: O(log n) KA synonym for J. Complexity: O(log n) L This is a simplified version of G( which returns a sorted tree containing L only those elements which are greater according to the supplied selector. $ This function also has the synonym M. Complexity: O(log n) MA synonym for L. Complexity: O(log n) N This is a simplified version of H( which returns a sorted tree containing N only those elements which are less than according to the supplied selector. $ This function also has the synonym O. Complexity: O(log n) OA synonym for N. Complexity: O(log n) P This is a simplified version of H( which returns a sorted tree containing X only those elements which are greater or equal to according to the supplied selector. $ This function also has the synonym Q. Complexity: O(log n) QA synonym for P. Complexity: O(log n) 56789:;<=>?@ABCDEFGHIJKLMNOPQ56789:ABCDEF;<=?>@GHIJKNOLMPQ56789:;<=>?@ABCDEFGHIJKLMNOPQ#portablestable+http://homepages.nildram.co.uk/~ahey/em.pngYXUses the supplied combining comparison to evaluate the union of two sets represented as [ sorted AVL trees of known height. Whenever the combining comparison is applied, the first [ comparison argument is an element of the first tree and the second comparison argument is  an element of the second tree. Complexity: Not sure, but I'0d appreciate it if someone could figure it out. 6 (Faster than Hedge union from Data.Set at any rate). ZUSimilar to _unionH_, but the resulting tree does not include elements in cases where + the supplied combining comparison returns  (Eq Nothing). LComplexity: Not sure, but I_d appreciate it if someone could figure it out. [_Uses the supplied combining comparison to evaluate the intersection of two sets represented as K sorted AVL trees. This function requires no height information at all for R the two tree inputs. The absolute height of the resulting tree is returned also. LComplexity: Not sure, but I_d appreciate it if someone could figure it out. \\Similar to _intersectionH_, but the resulting tree does not include elements in cases where + the supplied combining comparison returns  (Eq Nothing). LComplexity: Not sure, but I_d appreciate it if someone could figure it out. ]XUses the supplied comparison to evaluate the difference between two sets represented as  sorted AVL trees. VN.B. This function works with relative heights for the first tree and needs no height \ information for the second tree, so it_s OK to initialise the height of the first to zero, b rather than calculating the absolute height. However, if you do this the height of the resulting U tree will be incorrect also (it will have the same fixed offset as the first tree). LComplexity: Not sure, but I_d appreciate it if someone could figure it out. ^OSimilar to _differenceH_, but the resulting tree also includes those elements a_ for which the  combining comparison returns  Eq (Just a_). VN.B. This function works with relative heights for the first tree and needs no height \ information for the second tree, so it_s OK to initialise the height of the first to zero, b rather than calculating the absolute height. However, if you do this the height of the resulting U tree will be incorrect also (it will have the same fixed offset as the first tree). LComplexity: Not sure, but I_d appreciate it if someone could figure it out. _XThe symmetric difference is the set of elements which occur in one set or the other but not both. LComplexity: Not sure, but I_d appreciate it if someone could figure it out. YZ[\]^_YZ[\]^_portablestable+http://homepages.nildram.co.uk/~ahey/em.png`abRXUses the supplied combining comparison to evaluate the union of two sets represented as b sorted AVL trees. Whenever the combining comparison is applied, the first comparison argument is c an element of the first tree and the second comparison argument is an element of the second tree. Complexity: Not sure, but I'0d appreciate it if someone could figure it out. 6 (Faster than Hedge union from Data.Set at any rate). S Similar to RB, but the resulting tree does not include elements in cases where + the supplied combining comparison returns  (Eq Nothing). Complexity: Not sure, but I'0d appreciate it if someone could figure it out. TSUses the supplied combining comparison to evaluate the union of all sets in a list B of sets represented as sorted AVL trees. Behaves as if defined.. genUnions ccmp avls = foldl' (R ccmp) empty avlsU_Uses the supplied combining comparison to evaluate the intersection of two sets represented as  sorted AVL trees. Complexity: Not sure, but I'0d appreciate it if someone could figure it out. V Similar to UB, but the resulting tree does not include elements in cases where + the supplied combining comparison returns  (Eq Nothing). Complexity: Not sure, but I'0d appreciate it if someone could figure it out. W Similar to U2, but prepends the result to the supplied list in P left to right order. This is a (++) free function which behaves as if defined:  SgenIntersectionToListL c setA setB cs = asListL (genIntersection c setA setB) ++ csComplexity: Not sure, but I'0d appreciate it if someone could figure it out. XApplies W to the empty list. Complexity: Not sure, but I'0d appreciate it if someone could figure it out. Y Similar to W:, but the result does not include elements in cases where + the supplied combining comparison returns  (Eq Nothing). Complexity: Not sure, but I'0d appreciate it if someone could figure it out. ZApplies Y to the empty list. Complexity: Not sure, but I'0d appreciate it if someone could figure it out. [XUses the supplied comparison to evaluate the difference between two sets represented as $ sorted AVL trees. The expression..   genDifference cmp setA setB -.. is a set containing all those elements of setA which do not appear in setB. Complexity: Not sure, but I'0d appreciate it if someone could figure it out. \ Similar to [7, but the resulting tree also includes those elements a' for which the  combining comparison returns  (Eq (Just a')). Complexity: Not sure, but I'0d appreciate it if someone could figure it out. ]VUses the supplied comparison to test whether the first set is a subset of the second, X both sets being represented as sorted AVL trees. This function returns True if any of ! the following conditions hold.. @ The first set is empty (the empty set is a subset of any set).  The two sets are equal. 5 The first set is a proper subset of the second set. Complexity: Not sure, but I'0d appreciate it if someone could figure it out. ^XThe symmetric difference is the set of elements which occur in one set or the other but not both. Complexity: Not sure, but I'0d appreciate it if someone could figure it out. RSTUVWXYZ[\]^ RST[\^UVWXYZ] RSTUVWXYZ[\]^portablestable+http://homepages.nildram.co.uk/~ahey/em.png_ Convert a  Data.Set.Set? (from the base package Data.Set module) to a sorted AVL tree. Q Elements and element ordering are preserved (ascending order is left to right). Complexity: O(n) ` Convert a sorted AVL tree to a  Data.Set.Set* (from the base package Data.Set module). . Elements and element ordering are preserved. Complexity: O(n) a Convert a  Data.Map.MapH (from the base package Data.Map module) to a sorted (by key) AVL tree. Q Elements and element ordering are preserved (ascending order is left to right). Complexity: O(n) b Convert a sorted (by key) AVL tree to a  Data.Map.Map* (from the base package Data.Map module). . Elements and element ordering are preserved. Complexity: O(n) cAVL trees are an instance of d'. This definition has been placed here E to avoid introducing cyclic dependency between Types.hs and List.hs e.Show is based on showing the list produced by '. This definition has been placed here E to avoid introducing cyclic dependency between Types.hs and List.hs f7Ordering is based on ordering of the lists produced by '. This definition has been placed here E to avoid introducing cyclic dependency between Types.hs and List.hs g1Eq is based on equality of the lists produced by '. This definition has been placed here E to avoid introducing cyclic dependency between Types.hs and List.hs        !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`ab_`ab_`abportable provisional+http://homepages.nildram.co.uk/~ahey/em.png6cA set of values a. hidO(1). The empty set. eO(1). Create a singleton set. fO(1). Is this the empty set? gO(n)%. The number of elements in the set. hO(log n). Is the element in the set? iO(?). Is this a subset?  (s1 i s2) tells whether s1 is a subset of s2. jO(?)9. Is this a proper subset? (ie. a subset but not equal). kO(?)7. The union of two sets, preferring the first set when " equal elements are encountered. lThe union of a list of sets: (l == foldl' k d). mO(?). See n. nO(?). Difference of two sets. oO(?) . The intersection of two sets. pO(log n). Insert an element in a set. B If the set already contains an element equal to the given value, $ it is replaced with the new value. qO(log n) . Delete an element from a set. rO(n)5. Build a set from an ascending list in linear time.  :The precondition (input list is ascending) is not checked. sO(n)J. Build a set from an ascending list of distinct elements in linear time.  CThe precondition (input list is strictly ascending) is not checked. t O(n*log n)(. Create a set from a list of elements. uO(n). The elements of a set. vO(n)). Convert the set to a list of elements. wO(n)4. Convert the set to an ascending list of elements. xO(n)2. Filter all elements that satisfy the predicate. yO(n)F. Partition the set into two sets, one with all elements that satisfy 1 the predicate and one with all elements that don't satisfy the predicate.  See also z. zO(log n). The expression (z x set ) is a pair  (set1,set2)  where all elements in set1 are lower than x and all elements in  set2 larger than x. x is not found in neither set1 nor set2. {O(log n) . Performs a z$ but also returns whether the pivot ( element was found in the original set. | O(n*log n).  | f s! is the set obtained by applying f to each element of s. It'>s worth noting that the size of the result may be smaller if,  for some (x,y), x /= y && f x == f y }O(n). The identity } f s == | f s, works only when f is monotonic.   The precondition is not checked.  Semi-formally, we have: / and [x < y ==> f x < f y | x <- ls, y <- ls] 5 ==> mapMonotonic f s == map f s  where ls = toList s ~O(n);. Fold over the elements of a set in an unspecified order. O(log n) . The minimal element of a set. O(log n) . The maximal element of a set. O(log n). Delete the minimal element. O(log n). Delete the maximal element. O(log n)'. Delete and find the minimal element. 2 deleteFindMin set = (findMin set, deleteMin set) O(log n)'. Delete and find the maximal element. 2 deleteFindMax set = (findMax set, deleteMax set) O(n)/. Test if the internal set structure is valid. O(n)P. Convert a Data.Set.Set to an AVL tree based Set (as provided by this module). O(n)P. Convert an AVL tree based Set (as provided by this module) to a Data.Set.Set. O(1) . Convert a sortedA AVL tree to an AVL tree based Set (as provided by this module). < This function does not check the input AVL tree is sorted. O(1)S. Convert an AVL tree based Set (as provided by this module) to a sorted AVL tree. Obsolete equivalent of d. Obsolete equivalent of t. Obsolete equivalent of u. Obsolete equivalent of e. Obsolete equivalent of h. Obsolete equivalent of f. Obsolete equivalent of g. Obsolete equivalent of l. Obsolete equivalent of n. Obsolete equivalent of |. Obsolete equivalent of o. Obsolete equivalent of  p. Obsolete equivalent of  q. 4cdefghijklmnopqrstuvwxyz{|}~4cmfghijdepqklnoxyz{|}~uvtwrs4cdefghijklmnopqrstuvwxyz{|}~portable provisional+http://homepages.nildram.co.uk/~ahey/em.pngNA Map from keys k to values a. jklmnopqO(1). The empty map. O(1). A map with a single element. O(1). Is the map empty? O(n)%. The number of elements in the map. O(log n)". Is the key a member of the map? O(log n). Find the value at a key.  Calls r$ when the element can not be found. sO(log n). Find the value at a key.  Calls r$ when the element can not be found. O(log n)(. Lookup the value at a key in the map. O(log n). The expression ( def k map) returns  the value at key k or returns def! when the key is not in the map. O(log n)). Insert a new key and value in the map. C If the key is already present in the map, the associated value is ( replaced with the supplied value, i.e.  is equivalent to   t. O(log n)$. Insert with a combining function. O(log n)$. Insert with a combining function. O(log n). The expression ( f k x map) 0 is a pair where the first element is equal to ( k map) " and the second element equal to ( f k x map). @TODO: only one traversal. This requires fiddling with AVL.Push. O(log n)?. Delete a key and its value from the map. When the key is not 4 a member of the map, the original map is returned. O(n)-. Map a function over all values in the map. O(n)-. Map a function over all values in the map. O(n). The function  threads an accumulating 6 argument through the map in ascending order of keys. O(n)0. Filter all values that satisfy the predicate. O(n). Filter all keys/#values that satisfy the predicate. uO(n)8. partition the map according to a predicate. The first F map contains all elements that satisfy the predicate, the second all # elements that fail the predicate. O(n)8. partition the map according to a predicate. The first F map contains all elements that satisfy the predicate, the second all # elements that fail the predicate. O(log n). The expression ( x set ) is a pair  (set1,set2)  where all elements in set1 are lower than x and all elements in  set2 larger than x. x is not found in neither set1 nor set2. O(log n). The expression ( k map) splits a map just  like  but also returns  k map. O(log n). The minimal key of the map. O(log n). Delete the minimal key. O(log n)'. Delete and find the minimal element. O(log n)'. Delete and find the maximal element. O(log n). The minimal key of the map. O(log n). Delete the minimal key. O(n+m)4. Intersection of two maps. The values in the first  map are returned, i.e.  ( m1 m2 ==  t m1 m2). O(n+m)*. Intersection with a combining function. O(n+m)*. Intersection with a combining function. + Intersection is more efficient on (bigset  smallset) O(n). Convert to a list of key/ value pairs. O(n). Convert to a list of key/ value pairs. O(n). Convert to a list of key/ value pairs. O(n). Convert to a list of keys. O(n)". The set of all keys of the map. O(n)J. Apply a function to each element of a set and return the resulting map. O(n). Convert to a list of values. O(n)(. Fold the values in the map, such that   f z ==  Prelude.foldr f z . .  For example,  elems map = fold (:) [] map O(n+m). See . O(n+m). Difference of two maps. O(n+m)(. Difference with a combining function. O(n)J. Build a map from an ascending list of distinct elements in linear time.   The precondition is not checked. O(n)5. Build a map from an ascending list in linear time.  :The precondition (input list is ascending) is not checked. O(n)^. Build a map from an ascending list in linear time with a combining function for equal keys.  :The precondition (input list is ascending) is not checked. O(n);. Build a map from an ascending list in linear time with a $ combining function for equal keys.  :The precondition (input list is ascending) is not checked. The union of a list of maps:  ( ==  Prelude.foldl  ). 9The union of a list of maps, with a combining operation:  ( f ==  Prelude.foldl ( f) ). O(n+m).  The expression ( t1 t2!) takes the left-biased union of t1 and t2.  It prefers t1& when duplicate keys are encountered,  i.e. ( ==  t). ' The implementation uses the efficient  hedge-union algorithm. * Hedge-union is more efficient on (bigset  smallset)? O(n+m)$. Union with a combining function. O(n+m). # Union with a combining function. O(n+m).  This function is defined as ( =  (==)). O(n+m).  The expression ( f t1 t2 ) returns g if  all keys in t1 are in tree t2 , and when f returns g when @ applied to their respective values. For example, the following  expressions are all g:  E isSubmapOfBy (==) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) E isSubmapOfBy (<=) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) M isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1),('b',2)]) But the following are all : E isSubmapOfBy (==) (fromList [('a',2)]) (fromList [('a',1),('b',2)]) E isSubmapOfBy (<) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) E isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1)]) O(log n). The expression ( f k map) alters the value x at k, or absence thereof.  7 can be used to insert, delete, or update a value in a .  In short :  k ( f k m) = f ( k m) O(log n)8. Adjust a value at a specific key. When the key is not 4 a member of the map, the original map is returned. O(log n)8. Adjust a value at a specific key. When the key is not 4 a member of the map, the original map is returned. O(log n). The expression ( f k map) updates the value x  at k (if it is in the map). If (f x) is , the element is  deleted. If it is (h y ), the key k is bound to the new value y. O(log n). The expression ( f k map) updates the  value x at k (if it is in the map). If (f k x) is , # the element is deleted. If it is (h y ), the key k is bound  to the new value y. O(log n). Lookup and update. @TODO: only one traversal. This requires fiddling with AVL.Push.  O(n*log n) . Build a map from a list of key/0value pairs with a combining function. See also .  O(n*log n) . Build a map from a list of key/0value pairs with a combining function. See also . O(1) . Convert a sortedA AVL tree to an AVL tree based Set (as provided by this module). < This function does not check the input AVL tree is sorted. O(1)S. Convert an AVL tree based Set (as provided by this module) to a sorted AVL tree. vCCCMPTC, FD, undecidable instances experimental#jeanphilippe.bernardy; google mail.\wView" to the elements of a dictionnary View to the keys of a dictionnary <Class for set-like collection types. A set is really a map ' with no value associated to the keys,  so Set just states so. .Dummy method for haddock to accept the class. xyz{>Class of map-like types. (aka. for sparse associative types). JIn opposition of Indexed, Map supports unexisting value for some indices. NRemove a key from the keySet (and therefore the associated value in the Map). .Tells whether an key is member of the keySet. Union of two keySets. T When duplicates are encountered, the keys may come from any of the two input sets. 4 Values come from the map given as first arguement. Intersection of two keySets. SWhen duplicates are encountered, the keys may come from any of the two input sets. 4 Values come from the map given as first arguement. Difference of two keySets. ! Difference is to be read infix: a  b returns a set containing the  elements of a that are also absent from b. s1  s2C returns True iff. the keys in s1 form a subset of the keys in s2. !Lookup the value at a given key. ,Change the value associated to a given key. ! represents no associated value. "Insert with a combining function. insertWith f key value m  will insert the pair  (key, value) into m if key does @ not exist in the map. If the key does exist, the function will  insert the pair (key, f new_value old_value).  Convert a k to a , with a combining function. 3 Note the applications of the combining function:  1fromFoldableWith (+) [(k,x1), (k,x2), ..., (k,xn)], = fromFoldable [(k, xn + (... + (x2 + x1)))]  or more generally fromFoldableWith f [(k,x) | x <- l]& = fromFoldable [(k,foldl1 (flip f) l)]  ) is probably less surprising, so use it.  Convert a k to a , with a combining function.  sfoldGroups f a l = let mkGroup g = (fst $ head g, foldr f a (map snd g)) in fromList . map mkGroup . groupBy ((==) on fst)) . toList -Apply a function over all values in the map. "Union with a combining function. (Intersection with a combining function. &Difference with a combining function.  isSubmapBy if (l,r) = bounds c, then  inDomain k c  == l <= k <= r CConstruct an array with the specified bounds and containing values ( for given indices within these bounds. AThe array is undefined (i.e. bottom) if any index in the list is E out of bounds. The Haskell 98 Report further specifies that if any E two associations in the list have the same index, the value at that 2 index is undefined (i.e. bottom). However in GHC's implementation, F the value at such an index is the value part of the last association  with that index in the list. 6Because the indices must be checked for these errors,  is E strict in the bounds argument and in the indices of the association C list, but nonstrict in the values. Thus, recurrences such as the  following are possible:  @ a = array (1,100) ((1,1) : [(i, i * a!(i-1)) | i <- [2..100]]) BNot every index within the bounds of the array need appear in the F association list, but the values associated with indices that do not ) appear will be undefined (i.e. bottom). GIf, in any dimension, the lower bound is greater than the upper bound, E then the array is legal, but empty. Indexing an empty array always " gives an array-bounds error, but  still yields the bounds ' with which the array was constructed. Class of indexed types.  The collection is dense: there is no way to remove an element nor for lookup  to return  not found. IIn practice however, most shallow collection types will instanciate this  class in addition of 9, and leave the responsibility of failure to the caller.  index c k returns element associated to k  adjust f k c applies f to element associated to k' and returns the resulting collection. if  inDomain k c, then  index c k is guaranteed not to fail. KConstructs a collection identical to the first argument except that it has 9 been updated by the associations in the right argument.  For example, if m is a 1-origin, n by n matrix, then   m//[((i,i), 0) | i <- [1..n]] 9is the same matrix, except with the diagonal zeroed.  f8 takes an array and an association list and accumulates C pairs from the list into the array with the accumulating function f.  Thus  accumArray can be defined using : #Class of sequential-access types.  In addition of the  9 services, it provides deconstruction and concatenation.  The first i elements of a sequence. 'Elements of a sequence after the first i. #Split a sequence at a given index. Reverse a sequence. $Analyse the left end of a sequence. %Analyse the right end of a sequence. 2Add an element to the left end of a sequence. /Add an element to the right end of a sequence. The 3 function takes two seqences and returns True iff & the first is a prefix of the second. |}FClass of collection with unobservable elements. It is the dual of the k class. 'natural', insertion of an element into a collection. The empty collection.  ,Creates a collection with a single element.  'Insert all the elements of a foldable.  GSame as insertMany, but with the unchecked precondition that the input k is sorted.  Class of collection types.   filter f cE returns the collection of those elements that satisfy the predicate f. ~,Conversion from a Foldable to a Collection. 5Conversion from a Foldable to a Collection, with the  unchecked( precondition that the input is sorted #Converts a list into a collection. SConverts a list into a collection, with the precondition that the input is sorted. Concatenate two sequences. Infix version of 0: add an element to the left end of a sequence. A Mnemonic: a triangle with the single element at the pointy end. Infix version of 1: add an element to the right end of a sequence. B Mnemonic: a triangle with the single element at the pointy end. Infix verion of . Concatenate two sequences. CThe concatenation of all the elements of a container of sequences. DMap a function over all the elements of a container and concatenate  the resulting sequences. Infix version of , with arguments swapped.  3Tells whether a key is not a member of the keySet. !The expression (! def k map) returns  the value at key k or returns def! when the key is not in the map. "3Specialized version of fromFoldableWith for lists. #Same as  , but with a more general type. $Same as  , but with a more general type. %&Infix version of  . Difference of two (key) sets. Infix version of . Union of two (key) sets. Infix version of ". Intersection of two (key) sets. 'Union of many (key) sets. (2Union of many (key) sets, with combining function )*xklmnopqrstuvwxyz{|}~      !"#$%&'()*T     !(#$%' &")*Q           !"#$%&'()*MPTC, FD, undecidable instances experimental#jeanphilippe.bernardy; google mail.Logic equivalence +7foldable_properties returns the following properties:  size  # size c == foldr (const (+1)) 0 c  null  " null c <==> all (const False) c   isSingleton  ! isSingleton c <==> size c == 1  eq_elem { c1 == c2 ==> elem x c1 == elem x c2 -- note that the order of folding is not enforced, and that the converse is not true ,9unfoldable_properties returns the following properties:   singleton   singleton a == insert a empty   insertMany  . insertMany l c == Foldable.foldr insert c l  insertManySorted 4 insertManySorted l c == Foldable.foldr insert c l  where l = List.sort l0 -9collection_properties returns the following properties:   collection   foldr insert empty c == c  empty   null empty  insert1  e a `elem` (insert a c) -- insert puts the element in the collection  insert2  a a /= a' ==> (a' `elem` c <== a' `elem` (insert a c)) -- insert does not insert other elements  insert3  v let c' = insert a c in x `elem` c && y `elem` c ==> x `elem` c' || y `elem` c' -- insert alters at most one element  filter 3 (a `elem` filter f c) <==> ((a `elem` c) && f a) .2map_properties returns the following properties:  alter  + lookup k (alter f k m) == f (lookup k m)   mapWithKey  7 lookup k (mapWithKey f m) == fmap (f k) (lookup k m)   unionWith  E lookup k (unionWith f m1 m2) == case (lookup k m1, lookup k m2) of " (Nothing,Nothing) -> Nothing ! (Just x, Nothing) -> Just x ! (Nothing,Just x) -> Just x ' (Just x, Just y) -> Just (f x y)  intersectionWith  L lookup k (intersectionWith f m1 m2) == case (lookup k m1, lookup k m2) of & (Just x, Just y) -> Just (f x y)  _ -> Nothing  differenceWith  J lookup k (differenceWith f m1 m2) == case (lookup k m1, lookup k m2) of ! (Just x, Nothing) -> Just x  (Just x, Just y) -> f x y " (Nothing, _) -> Nothing   isSubmapBy  c isSubmapBy f m1 m2 <==> differenceWith (\x y->if f x y then Nothing else Just v) m1 m2 == mempty   insertWith  Z insertWith f k a m == alter (\x -> Just $ case x of {Nothing->a;Just a' -> f a a'}) k m  fromFoldableWith  B fromFoldableWith f l == foldr (uncurry (insertWith f)) mempty l  delete  * delete k m == alter (const Nothing) k m  member  & member k m <==> isJust (lookup k m)  union  ' union m1 m2 == unionWith const m1 m2   intersection  6 intersection m1 m2 == intersectionWith const m1 m2   difference  = difference m1 m2 == differenceWith (\_ _ -> Nothing) m1 m2  subset  6 isSubset m1 m2 <==> isSubmapBy (\_ _ -> True) m1 m2  mempty   lookup k mempty == Nothing  mappend   mappend m1 m2 == union m1 m2   eq_lookup r c1 == c2 ==> lookup x c1 == lookup x c2 -- should really be: c1 == c2 <==> forall x. lookup x c1 == lookup x c2 /9map_unfold_properties returns the following properties:  mempty   mempty == empty  insert 1 insert (k,v) m == insertWith (\x _ -> x) k v m 07map_fold_properties returns the following properties:  foldable  I maybeToList (lookup k m) == map snd (filter ((== k) . fst) (toList m))  size + sizeExcept (alter f k m) == sizeExcept m A where sizeExcept m = size m - maybe 0 (const 1) (lookup k m) 19set_unfold_properties returns the following properties:  mempty   mempty == empty  insert , insert k m == insertWith (\x _->x) k () m 27set_fold_properties returns the following properties:  foldable  H maybeToList (lookup k m) == map (const ()) (filter (== k) (toList m))  size + sizeExcept (alter f k m) == sizeExcept m A where sizeExcept m = size m - maybe 0 (const 1) (lookup k m) 36indexed_properties returns the following properties:  adjust = k `inDomain` m ==> index k (adjust f k m) == f (index k m) 47sequence_properties returns the following properties:  fold0   foldMap f empty == mempty  fold1  2 foldMap f (x <| s) == f x `mappend` foldMap f s  fold2  2 foldMap f (s |> x) == foldMap f s `mappend` f x  fold3  : foldMap f (s >< t) == foldMap f s `mappend` foldMap f t  front0   front empty == Nothing  front1   front (x <| s) == Just (x,s)  front2  e front (s |> x) == case front s of {Nothing -> Just (x, empty); Just (x',s') -> Just (x', s' |> x)}  front3  e front (s >< t) == case front s of {Nothing -> front t; Just (x',s') -> Just (x', s' >< t)}  back0   back empty == Nothing  back1   back (s |> x) == Just (s,x)  back2  c back (x <| s) == case back s of {Nothing -> Just (empty, x); Just (s',x') -> Just (x <| s', x')}  back3  c back (t >< s) == case back s of {Nothing -> back t; Just (s',x') -> Just (t >< s', x')}  drop1   drop 0 s == s  drop2  W n>0 ==> drop (n+1) s == case front (drop n s) of Nothing -> empty; Just (_,s') -> s'  take1   take 0 s == empty  take2  Z n>0 ==> take (n+1) s == case front s of Nothing -> empty; Just (x,s') -> x <| take n s'  reverse  : foldMap f (reverse s) == getDual (foldMap (Dual . f) s)  mempty   mempty == empty  eq_fold , s1 == s2 ==> foldMap f s1 == foldMap f s2 5?indexed_sequence_properties returns the following properties:  domain  + k `inDomain` s <==> k >= 0 && k < size s  left1  < k `inDomain` s ==> index (k+1) (x <| s) == index k s  left2  6 index 0 (x <| s) == x  right1  < k `inDomain` s ==> index k (s |> x) == index k s  right2  4 index (size s) (s |> x) == x  append1  < k `inDomain` t ==> index (k+size s) (s >< t) == index k t  append2 < k `inDomain` s ==> index k (s >< t) == index k s 6:indexed_map_properties returns the following properties:  domain  # k `inDomain` m <==> k `member` m  index ; case lookup k m of {Just x -> x == index k m; _ -> True} +,-./0123456 ,+-./1026435 +,-./01234567View a list (actually any ) of  (key,value) pairs as a  collection. fThis allows to feed sequences into algorithms that require a map without building a full-fledged map. f Most of the time this will be used only when the parameter list is known to be very small, such that ) conversion to a Map would be to costly. 878787889View a list of as a  collection. fThis allows to feed sequences into algorithms that require a Set without building a full-fledged Set. f Most of the time this will be used only when the parameter list is known to be very small, such that ) conversion to a Set would be to costly. :;9:;9:;9:;:;Munknown This module provides a basic implementation of the Trie data type.volatile#jeanphilippe.bernardy; google mail.(<!A Trie with key elements of type k (keys of type [k]) and values of type v. ^ Note that the type is not opaque: user can pattern match on it and construct and Trie value. @ This is because there is no non-trivial invariant to preserve. =>?@A Modify the ? field of a trie.  Modify the ? field of a trie. BThe empty trie. CIs the trie empty ? DThe singleton trie. E4Combining two tries. The first shadows the second. F:Combining two tries. If the two define the same key, the ' specified combining function is used. G@Combining two tries. If the two tries define the same key, the ' specified combining function is used. HIJKLMNOPQprefixLookup k p returns a sequence of all (k',v) pairs, such that k is a prefix of k'. 8 The sequence is sorted by lexicographic order of keys. R%An upwards accumulation on the trie. S&A downwards accumulation on the trie. T)Return the prefix of the trie satisfying f. U)Return the prefix of the trie satisfying f on all values present. VJReturn the fringe of the trie (the trie composed of only the leaf nodes). WXYZ[\!<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\!<=>?MCNLQBDOPAEFJIHG@XYZW[KRSTUV\!<=>?=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\$%&$'($)*++,-./0123456789:;<=>?@ABCDEFFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmn9o36pqrstuvwxyz{|}~  n 9           !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~l36n9osr{zm|}pqtuvwxy36n9opqtvxyuw}m|z{lqo{}|p36mz3n6{}|op         !"#T$%&l'()*+,-./01+2   34 5 6718 9 : ; <=>?@ABCDEFGHIJ K L M N O P Q RSTUV W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~                                      !!!!!!!!!!!!!!!!!!!"""""""""" #######    1 l1 !"#$%&'()*+,-collections-0.3.1Data.CollectionsData.Tree.AVL.Test.CounterData.Tree.AVL.TypesData.Tree.AVL.SizeData.Ranged.BoundariesData.Ranged.RangesData.Ranged.RangedSet Data.Set.EnumData.Collections.FoldableData.COrderingData.Tree.AVL.ReadData.Tree.AVL.WriteData.Tree.AVL.PushData.Tree.AVL.ListData.Tree.AVL.Test.UtilsData.Tree.AVL.DeleteData.Tree.AVL.JoinData.Tree.AVL.ZipperData.Tree.AVL.SplitData.Tree.AVL.Set Data.Tree.AVL Data.Set.AVL Data.Map.AVLData.Collections.Properties Data.Map.List Data.Set.List Data.Trie#Data.Tree.AVL.Internals.HeightUtilsData.Tree.AVL.Internals.HPush Data.RangedData.Tree.AVL.Internals.BinPath Data.Tree.AVL.Internals.DelUtilsData.Tree.AVL.Internals.HJoinData.Tree.AVL.Internals.HAVLData.Tree.AVL.Internals.HSetcontainers-0.3.0.0 Data.IntMapIntMap Data.IntSetIntSet Data.SequenceSeqXIntgetCount resetCountAVLPZNEemptyisEmpty isNonEmpty singletonpairtryGetSingletonsizeaddSizeBoundaryBoundaryBelowAllBoundaryAboveAll BoundaryBelow BoundaryAboveDiscreteOrderedadjacent enumAdjacentboundedAdjacentabove/>/Range rangeLower rangeUpperrangeHas rangeListHas emptyRange fullRangesingletonRange rangeIsEmpty rangeOverlap rangeEnclosesrangeIntersection rangeUnionrangeDifferenceRSet rSetRangesvalidRangeListnormaliseRangeList makeRangedSetunsafeRangedSet rSingleton rSetIsEmptyrSetHas-?- rSetIsSubset-<=-rSetIsSubsetStrict-<- rSetUnion-\/-rSetIntersection-/\-rSetDifference-!- rSetNegation rSetEmptyrSetFull rSetUnfoldSet\\nullmemberinsertdeleteisProperSubsetOf isSubsetOffindMinfindMax deleteMin deleteMax deleteFindMin deleteFindMaxunionsunion difference intersection complementcomplementWithfilter partitionmap mapMonotonicfoldfoldrelemstoList toAscListfromList fromAscListfromDistinctAscListsplit splitMemberFoldablefoldMapfoldlfoldr1foldl1 isSingletonfoldr'foldrMfoldl'foldlM traverse_for_mapM_forM_ sequenceA_ sequence_asummsumandoranyallsumproductmaximum maximumByminimum minimumByelemnotElemfind COrderingGtEqLtunitCCunitByCCfstCCfstByCCsndCCsndByCCwithCCwithCC'withByCC withByCC'flipCflipCC assertReadLtryReadL assertReadRtryReadR genAssertRead genTryReadgenTryReadMaybegenDefaultRead genContainswriteL tryWriteLwriteR tryWriteRgenWrite genWriteFast genTryWrite genWriteMaybegenTryWriteMaybegenPushgenPush' genPushMaybe genPushMaybe'pushLpushRasListLtoListLasListRtoListRfoldrAVL foldrAVL' foldr1AVL foldr1AVL' foldr2AVL foldr2AVL'foldlAVL foldlAVL' foldl1AVL foldl1AVL' foldl2AVL foldl2AVL' asTreeLenLasTreeL asTreeLenRasTreeR reverseAVLmapAVLmapAVL' traverseAVL replicateAVLflatten flatReverseflatMapflatMap' filterViaList partitionAVLmapMaybeViaList genAsTree genPushListgenSortAscendinggenSortDescending TestTreespathTree isBalanced checkHeightisSorted isSortedOKallAVLallNonEmptyAVLnumTreesexhaustiveTestflatAVL minElements maxElements assertDelLtryDelL assertDelRtryDelR assertPopLtryPopL assertPopRtryPopRgenDelgenDelIf genDelMaybe genDelFast genAssertPop genTryPopgenAssertPopMaybegenTryPopMaybegenAssertPopIf genTryPopIfjoin concatAVL flatConcatBAVLPAVLZAVL genAssertOpen genTryOpen genTryOpenGE genTryOpenLE assertOpenLtryOpenL assertOpenRtryOpenR genOpenEitherfill fillCloseclosedelClose getCurrent putCurrent applyCurrent applyCurrent' assertMoveLtryMoveL assertMoveRtryMoveR isLeftmost isRightmostinsertL insertMoveLinsertR insertMoveR insertTreeL insertTreeRassertDelMoveL tryDelMoveLassertDelMoveR tryDelMoveRdelAllLdelAllR delAllCloseL delAllCloseRdelAllIncCloseLdelAllIncCloseRsizeLsizeRsizeZAVL genOpenBAVL closeBAVLfullBAVL emptyBAVL tryReadBAVL readFullBAVLpushBAVL deleteBAVLfullBAVLtoZAVLemptyBAVLtoPAVLanyBAVLtoEithersplitAtLsplitAtRtakeLtakeRdropLdropRspanLspanR takeWhileL takeWhileR dropWhileL dropWhileRrotateLrotateR popRotateL popRotateR rotateByL rotateByRgenForkLgenForkRgenFork genTakeLE genDropGT genTakeGT genDropLE genTakeLT genDropGE genTakeGE genDropLTgenUnion genUnionMaybe genUnionsgenIntersectiongenIntersectionMaybegenIntersectionToListLgenIntersectionAsListLgenIntersectionMaybeToListLgenIntersectionMaybeAsListL genDifferencegenDifferenceMaybe genIsSubsetOfgenSymDifferenceset2AVLavl2Setmap2AVLavl2Mapvalid fromStdSettoStdSetunsafeFromTreetoTreeemptySetmkSet setToListunitSet elementOf isEmptySet cardinality unionManySetsminusSetmapSet intersectaddToSet delFromSetMap!lookupfindWithDefault insertWith insertWithKeyinsertLookupWithKey mapWithKeymapAccum filterWithKeypartitionWithKey splitLookupintersectionWithintersectionWithKeyassocskeyskeysSet liftKeysSet foldWithKeydifferenceWithdifferenceWithKeyfromAscListWithfromAscListWithKey unionsWith unionWith unionWithKey isSubmapOf isSubmapOfByalteradjust adjustWithKeyupdate updateWithKeyupdateLookupWithKey fromListWithfromListWithKey ElemsView fromElemsViewKeysView fromKeysView haddock_candyisSubsetfromFoldableWith foldGroups isSubmapByArrayboundsarrayIndexedindexinDomain//accumSequencetakedropsplitAtreversefrontbackconssnocisPrefix Unfoldable insertManyinsertManySorted Collection RangedSetAvlMapAvlSetStdMapStdSet fromFoldablefromAscFoldableappend<||>><concat concatMapheadtail notMemberlookupWithDefaultintersectionWith'differenceWith' mapWithKey'withKeys withElemsfoldable_propertiesunfoldable_propertiescollection_propertiesmap_propertiesmap_unfold_propertiesmap_fold_propertiesset_unfold_propertiesset_fold_propertiesindexed_propertiessequence_propertiesindexed_sequence_propertiesindexed_map_properties AssocListSetList fromSetListTrievaluechildren retypeKeys prefixLookupupwards downwards takeWhile takeWhile'fringecountincCount $fOrdXIntbase GHC.ClassescompareOrdghc-primGHC.PrimseqGHC.ReadReadGHC.ShowShow avlTyConNameGHC.BoolTrue Data.MaybeJustheight addHeight compareHeight fastAddSizefasNfasZfasPfaspushHLpushHRpushHL_pushHR_ normalise rSetIsFullprop_intersection_commutes wordLengthcheck findMinIndex findMaxIndexGHC.ListfoldBits foldBits'bitcountls1bms1bGHC.Base Data.ListFalseNothingcOrderingTyConName GHC.OrderingEQflipreadLNEreadLEreadRNEreadREBinPathEmptyBPFullBPbit0selgoLgoR genFindPath genOpenPathgenOpenPathWith writePathreadPath readPath_ insertPathwriteL'writeLNwriteLZwriteLPwriteR'writeRNwriteRZwriteRPtoListL'toListR'cHcH_delLNdelLZdelLPdelLNZdelLZZdelLPZdelLZNdelLZPdelRNdelRZdelRPdelRNZdelRZZdelRPZdelRZNdelRZPpopLNpopLZpopLPpopLNZpopLZZpopLPZpopLZNpopLZPpopRNpopRZpopRPpopRNZpopRZZpopRPZpopRZNpopRZP deletePathdelNdelZdelPdelNLdNLdelNRdNRdelZLdZLdelZRdZRdelPLdPLdelPRdPRpopHLpopHLNpopHLZpopHLPpopHLN_popHLZ_popHLP_popHLNZpopHLZZpopHLPZpopHLZNpopHLZPrebalNrebalPchkLNchkLZchkLPchkRNchkRZchkRPsubNsubZRsubZLsubPchkLN'chkLZ'chkLP'chkRN'chkRZ'chkRP'joinH'joinHLjoinHRjoinHspliceHspliceHLspliceHR spliceHL_ spliceHR_spliceLspliceLNspliceLZspliceLP spliceLPZspliceRspliceRPspliceRZspliceRN spliceRNZHAVLSHHE concatHAVLS mergePairs mergePairs_mkHAVLSmkHAVLS_PathRPLPEPclose_noLPnoRP closeNoLP closeNoRPaddSizeP addSizeRP addSizeLPopenL_openLNopenLZopenR_openRPopenRZ Data.EitherRightLeftinsertLHinsertRHopenFull openEmptyHAVL emptyHAVL isEmptyHAVLisNonEmptyHAVLtoHAVL spliceHAVLjoinHAVL pushLHAVL pushRHAVLTakeWhileResultTheLotTWSomeTW SpanResultTheLotSome TakeResultMoreTRAllTR SplitResultMoreAll GHC.TypesIntsplitLsplitL_splitRsplitR_takeL_takeL__takeR_takeR__dropL_dropL__dropR_dropR__ popRotateL' popRotateR' rotateByL_ rotateByL__ rotateByR_ rotateByR__unionH unionMaybeH intersectionHintersectionMaybeH differenceHdifferenceMaybeHsymDifferenceHSubsetForkLResForkLNout $fFunctorAVLFunctor $fShowAVL$fOrdAVL$fEqAVLshowSet readValCCmcmpmfcmpmmfcmp toOrderingtoOrdGHC.Errerrorconstmp foldlStrictTORLSortingCollectionminViewunfold\//\lifted<==>ontoMaybevalue_u children_utesting