mC      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABportablestable+http://homepages.nildram.co.uk/~ahey/em.pngBasic data type. CD%Read the current comparison counter. &Reset the comparison counter to zero. E"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 F method from G 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 HO etc. in your own code (in any combining comparisons you define, for example). The Eq and Ord instances. SBegining with version 3.0 these are now derived, and hence are defined in terms of S strict structural equality, rather than observational equivalence. The reason for Y this change is that the observational equivalence abstraction was technically breakable S with the exposed API. But since this change, some functions which were previously P considered unsafe have become safe to expose (those that measure tree height). #BF=+1 (left height > right height) BF= 0 #BF=-1 (right height > left height)  Empty Tree I The empty AVL tree. Returns J if an AVL tree is empty. Complexity: O(1) Returns J 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 (K e).  Otherwise it returns Nothing. Complexity: O(1)    portablestable+http://homepages.nildram.co.uk/~ahey/em.png%Determine the height of an AVL tree. Complexity: O(log n) 1Adds the height of a tree to the first argument. Complexity: O(log n) XA 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. portablestable+http://homepages.nildram.co.uk/~ahey/em.png4Counts the total number of elements in an AVL tree.   =  0Complexity: O(n) /Adds the size of a tree to the first argument. ( This is just a convenience wrapper for . Complexity: O(n) OFast 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) LMNOP(Returns the exact tree size in the form (K n) if this is less than or ( equal to the input clip value. Returns Q of the size is greater than A the clip value. This function exploits the same optimisation as . AComplexity: O(min n c) where n is tree size and c is clip value. RSTUVWXYportablestable+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 Q if the tree is empty. Complexity: O(log n) Z["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 Q 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 Q if the search failed. Complexity: O(log n) BThis version returns the result of the selector (without adding a K wrapper) if the search  succeeds, or Q 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.png^ 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. _ 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. `[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) a\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) ^_`a^_`a portablestable+http://homepages.nildram.co.uk/~ahey/em.pngbInt fields are search depth and  path bits respecively. The  path bits consist of a  a string of depthH bits, left justified. MSB of 0 means go left, MSB of 1 means go right. cdefghiTFind the path to a AVL tree element, returns -1 (invalid path) if element not found Complexity: O(log n) j;Get the BinPath of an element using the supplied selector. Complexity: O(log n) kGGet the BinPath of an element using the supplied (combining) selector. Complexity: O(log n) lDOverwrite a tree element. Assumes the path bits were extracted from d 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) m?Read a tree element. Assumes the path bits were extracted from d constructor. 5 Raises an error if the path leads to an empty tree. Complexity: O(log n) noHInserts a new tree element. Assumes the path bits were extracted from a c 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 l for this). Complexity: O(log n) bcdfghijklmo bdccdfghijklmo 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 Q if applied to an empty tree. Complexity: O(log n) pqrs!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 Q if applied to an empty tree. Complexity: O(log n) tuvw#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 (xy 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 (xy e) constructor returned by % the selector. This function returns Q if the search failed. Complexity: O(log n) & Similar to #@, but also returns the original tree if the search succeeds but  the selector returns (xy Q)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 (xy Q)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.png(eGeneral 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 (xy 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  (xy Q)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.pngNz{|}~DDeletes a tree element. Assumes the path bits were extracted from a FullBP constructor. Complexity: O(log n) !z{|!z{| portablestable+http://homepages.nildram.co.uk/~ahey/em.png.TDelete the left-most element of an AVL tree. If the tree is sorted this will be the 9 least element. This function returns an empty tree if it's argument is an empty tree. Complexity: O(log n) /"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) 0)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 Q if it's argument is an empty tree. Complexity: O(log n) 1UDelete the right-most element of an AVL tree. If the tree is sorted this will be the < greatest element. This function returns an empty tree if it's argument is an empty tree. Complexity: O(log n) 2#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) 3*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 Q if it's argument is an empty tree. Complexity: O(log n) 4ZPop 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) 5Same as 4, except this version returns Q if it's argument is an empty tree. Complexity: O(log n) 6[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) 7Same as 6, except this version returns Q if it's argument is an empty tree. Complexity: O(log n) 8JGeneral 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) 9GThis version only deletes the element if the supplied selector returns (xy J).  If it returns (xy )? 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 (xy Q).  If it returns (xy (K 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 8;, 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 Q if the search fails. Complexity: O(log n) >CIn this case the selector returns two values if a search succeeds.  If the second is (K e) then the new value (e0) is substituted in the same place in the tree.  If the second is Q1 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 Q 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 J. If it's !, the original tree is returned. 4 This function raises an error if the search fails. Complexity: O(log n) A Similar to genPopIf, but returns Q if the search fails. Complexity: O(log n) ./0123456789:;<=>?@A./0123456789:;<=>?@Aportablestable+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/B/List AVL tree contents in left to right order. > The resulting list in ascending order if the tree is sorted. Complexity: O(n) CGJoin 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) D/List AVL tree contents in right to left order. ? The resulting list in descending order if the tree is sorted. Complexity: O(n) EGJoin 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) FThe 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 G for a strict version. It behaves as if defined..  , foldrAVL f a avl = foldr f a (asListL avl) For example, the B function could be defined..   asListL = foldrAVL (:) [] Complexity: O(n) GThe strict version of FA, 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) HThe 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 I for a strict version.  * foldr1AVL f avl = foldr1 f (asListL avl) 4This function raises an error if the tree is empty. Complexity: O(n) IThe strict version of HA, 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) JThis fold is a hybrid between F and H . As with H, 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 F).  As with F and H, this function is lazy, so it'$s best not to use it with functions / that are strict in their second argument. See K for a strict version. Complexity: O(n) KThe strict version of JA, 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) LThe 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 M for a strict version.  , foldlAVL f a avl = foldl f a (asListL avl) For example, the D function could be defined..  " asListR = foldlAVL (flip (:)) [] Complexity: O(n) MThe strict version of L@, 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) NThe 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 O for a strict version.  * foldl1AVL f avl = foldl1 f (asListL avl) 4This function raises an error if the tree is empty. Complexity: O(n) OThe strict version of N@, 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) PThis fold is a hybrid between L and N . As with N, 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 L).  As with L and N, this function is lazy, so it'$s best not to use it with functions . that are strict in their first argument. See Q for a strict version. Complexity: O(n) QThe strict version of P@, 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) R!This is a specialised version of G for use with an  unboxed3 Int accumulator (with GHC). Defaults to boxed Int  for other Haskells. Complexity: O(n) SThe AVL equivalent of Data.List.mapAccumL on lists. " It behaves like a combination of ^ and L. Y It applies a function to each element of a tree, passing an accumulating parameter from \ left to right, and returning a final value of this accumulator together with the new tree. 7Using this version with a function that is strict in it' s first argument will result in  O(n) stack use. See T for a strict version. Complexity: O(n) TThis is a strict version of S&, which is useful for functions which V are strict in their first 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) UThe AVL equivalent of Data.List.mapAccumR on lists. " It behaves like a combination of ^ and F. Y It applies a function to each element of a tree, passing an accumulating parameter from \ right to left, and returning a final value of this accumulator together with the new tree. 7Using this version with a function that is strict in it' s first argument will result in  O(n) stack use. See V for a strict version. Complexity: O(n) VThis is a strict version of U&, which is useful for functions which V are strict in their first 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) W!Glasgow Haskell only. Similar to T! but uses an unboxed pair in the  accumulating function. Complexity: O(n) X!Glasgow Haskell only. Similar to V! but uses an unboxed pair in the  accumulating function. Complexity: O(n) YXConvert 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) ZAs YG, 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) `aNConstruct a flat AVL tree of size n (n>=0), where all elements are identical. Complexity: O(log n) bCFlatten an AVL tree, preserving the ordering of the tree elements. Complexity: O(n) c Similar to bH, but the tree elements are reversed. This function has higher constant  factor overhead than ]. Complexity: O(n) d Similar to ^", but the resulting tree is flat. 8 This function has higher constant factor overhead than ^. Complexity: O(n) eSame as d1, but the supplied function is applied strictly. Complexity: O(n) fJRemove all AVL tree elements which do not satisfy the supplied predicate. < Element ordering is preserved. The resulting tree is flat.  See gE for an alternative implementation which is probably more efficient. Complexity: O(n) gJRemove all AVL tree elements which do not satisfy the supplied predicate.  Element ordering is preserved. Complexity: O(n) hNPartition 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) iERemove all AVL tree elements for which the supplied function returns Q. < Element ordering is preserved. The resulting tree is flat.  See jE for an alternative implementation which is probably more efficient. Complexity: O(n) jERemove all AVL tree elements for which the supplied function returns Q.  Element ordering is preserved. Complexity: O(n) kInvokes l on the empty AVL tree. Complexity: O(n.(log n)) ldPush the elements of an unsorted List in a sorted AVL tree using the supplied combining comparison. MComplexity: O(n.(log (m+n))) where n is the list length, m is the tree size. mSUses 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).  m c = B . k cComplexity: O(n.(log n)) nTUses 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).  n c = D . k cComplexity: O(n.(log n)) -BCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmn-BCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnportablestable+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. oOVerify 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) pVerify that a tree is sorted. Complexity: O(n) qRVerify 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 I 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]. rKDetetermine 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 sKDetetermine 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  opqrs opqrsportablestable+http://homepages.nildram.co.uk/~ahey/em.png t8Join two AVL trees. This is the AVL equivalent of (++).  / asListL (l `join` r) = asListL l ++ asListL r JComplexity: O(log n), where n is the size of the larger of the two trees. uConcatenate 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. v Similar to u%, 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. tuvtuvportablestable+http://homepages.nildram.co.uk/~ahey/em.pngQwA w4 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). x:Abstract data type for an unsuccessfully opened AVL tree. = A PAVL can be thought 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. y?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. zUOpens 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 Q 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 y using . 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 Q/ 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 Q 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 Q 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 x* with the supplied element, which becomes & the current element of the resulting y&. The supplied filling element should  be "equal"3 to the value used in the search which created the x. Complexity: O(1) "Essentially the same operation as , but the resulting y 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 Q9 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 Q: if the current element is already the rightmost element. /Complexity: O(1) average, O(log n) worst case. Returns J1 if the current element is the leftmost element. /Complexity: O(1) average, O(log n) worst case. Returns J2 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 R 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 S 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 Q9 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 Q: 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" w7 if a matching element was found, otherwise returns an "empty" w. Complexity: O(log n) .Returns the original tree, extracted from the w'. Typically you will not need this, as 9 the original tree will still be in scope in most cases. Complexity: O(1) Returns J if the w is "full"& (a corresponding element was found). Complexity: O(1) Returns J if the w is "empty"' (no corresponding element was found). Complexity: O(1) Read the element value from a "full" w.  This function returns Q if applied to an "empty" w. Complexity: O(1) Read the element value from a "full" w. 0 This function raises an error if applied to an "empty" w. Complexity: O(1) If the w 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) If the w 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 w)  Converts a "full" w as a y#. Raises an error if applied to an "empty" w. Complexity: O(log n)   Converts an "empty" w as a x". Raises an error if applied to a "full" w. Complexity: O(log n)  Converts a w to either a x or y (depending on whether it is "empty" or "full"). Complexity: O(log n) 8wxyz{|}~8wxyz{|}~portablestable+http://homepages.nildram.co.uk/~ahey/em.pngXUses 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). USimilar 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. portablestable+http://homepages.nildram.co.uk/~ahey/em.pngXUses 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).  Similar to B, 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. SUses 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' ( ccmp) empty avls_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.  Similar to B, 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.  Similar to 2, 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. Applies  to the empty list. Complexity: Not sure, but I'0d appreciate it if someone could figure it out.  Similar to :, 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. Applies  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.  Similar to 0, but also requires that the supplied combining  comparison returns (xy True) for matching elements. 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. portablestable+http://homepages.nildram.co.uk/~ahey/em.png 0An HAVL represents an AVL tree of known height. Empty HAVL (height is 0). Returns JK 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) Returns JO 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) Converts an AVL to HAVL ;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. Join 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.  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.  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.  portablestable+http://homepages.nildram.co.uk/~ahey/em.png; !"#$%&'()*+%Split an AVL tree from the Left. The ,0 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) -.&Split an AVL tree from the Right. The ,0 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) /0 This is a simplified version of + which does not return the remaining tree.  The ,O 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) 12 This is a simplified version of + which does not return the remaining tree.  The ,P 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) 34 This is a simplified version of = 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) 56 This is a simplified version of < 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) 78TSpan 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. [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) ]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)  Similar to D, but returns the rotated element. This function raises an error if  applied to an empty tree. Complexity: O(log n) 9 Similar to D, but returns the rotated element. This function raises an error if  applied to an empty tree. Complexity: O(log n) :TRotate 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. 8 The result of rotating an empty tree is an empty tree. Complexity: O(n) ;<URotate 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. 8 The result of rotating an empty tree is an empty tree. Complexity: O(n) =>^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) ^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)  Similar to  and 2, but returns any equal element found (instead of E incorporating it into the left or right tree results respectively). Complexity: O(log n)  This is a simplified version of ( which returns a sorted tree containing Y only those elements which are less than or equal to according to the supplied selector. $ This function also has the synonym . Complexity: O(log n) A synonym for . Complexity: O(log n)  This is a simplified version of ( which returns a sorted tree containing K only those elements which are greater according to the supplied selector. $ This function also has the synonym . Complexity: O(log n) A synonym for . Complexity: O(log n)  This is a simplified version of ( which returns a sorted tree containing M only those elements which are less than according to the supplied selector. $ This function also has the synonym . Complexity: O(log n) A synonym for . Complexity: O(log n)  This is a simplified version of ( which returns a sorted tree containing W only those elements which are greater or equal to according to the supplied selector. $ This function also has the synonym . Complexity: O(log n) A synonym for . Complexity: O(log n) 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)  Convert a  Data.Map.Map to a sorted (by key) AVL tree. Q Elements and element ordering are preserved (ascending order is left to right). Complexity: O(n)  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) ?AVL trees are an instance of @'. This definition has been placed here E to avoid introducing cyclic dependency between Types.hs and List.hs A.Show is based on showing the list produced by B'. This definition has been placed here E to avoid introducing cyclic dependency between Types.hs and List.hs   !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~  !"#$%&',-()*+.1/2038;9:4657<=>?@ABCDEYZ[\kl]^_SUTVWX`agjfihFGHIJKLMNOPQRbcdemntuvyx~z{|}wopqrsportableunstable+http://homepages.nildram.co.uk/~ahey/em.png+ ^_`abcdfghijklmo !"#$%&'()*+,-z{|./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~portableunstable+http://homepages.nildram.co.uk/~ahey/em.pngh8Run every test in this module (takes a very long time). ?Test isBalanced is capable of failing for a few non-AVL trees. @Test isSorted is capable of failing for a few non-sorted trees. Test size function Test clipSize function Test genWrite function Test genPush function Test genDel function Test genAssertPop function Test pushL function  Also exercises: asListL Test pushR function  Also exercises: asListR Test assertDelL function  Also exercises: asListL Test delR function  Also exercises: asListR Test assertPopL function  Also exercises: asListL Test popHL function = This test can only be run if popHL and HAVL are not hidden. C However, popHL is exercised by indirectly by testConcatAVL anyway Test assertPopR function  Also exercises: asListR Test flatten function & Also exercises: asListL,replicateAVL Test foldrAVL  Test foldrAVL' Test foldlAVL  Test foldlAVL' Test foldr1AVL Test foldr1AVL' Test foldl1AVL Test foldl1AVL' Test mapAccumLAVL Test mapAccumRAVL Test mapAccumLAVL' Test mapAccumRAVL' Test mapAccumLAVL'' Test mapAccumRAVL'' Test the join function Test the joinHAVL function Test the concatAVL function. Test the flatConcat function.  Test the filterViaList function Test the filterAVL function "Test the mapMaybeViaList function Test the mapMaybeAVL function Test splitAtL function Test takeL function Test dropL function Test splitAtR function  Test takeR function  Test dropR function  Test spanL function  Test takeWhileL function  Test dropWhileL function Test spanR function Test takeWhileR function Test dropWhileR function Test rotateL function Test rotateR function Test rotateByL function Test rotateByR function Test genForkL function Test genForkR function Test genFork function Test genTakeLE function Test genTakeLT function Test genTakeGT function Test genTakeGE function Test the genUnion function #Test the genSymDifference function  Test the genUnionMaybe function "Test the genIntersection function  'Test the genIntersectionMaybe function !)Test the genIntersectionAsListL function ".Test the genIntersectionMaybeAsListL function # Test the genDifference function $%Test the genDifferenceMaybe function % Test the genIsSubsetOf function &"Test the genIsSubsetOfBy function 'Test compareHeight function (Test Zipper open/close )Test Zipper delClose *Test Zipper assertOpenL/close +Test Zipper assertOpenR/close ,Test Zipper assertMoveL/ isRightmost -Test Zipper assertMoveR/ isLeftmost .Test Zipper insertL /Test Zipper insertMoveL 0Test Zipper insertR 1Test Zipper insertMoveR 2Test Zipper insertTreeL 3Test Zipper insertTreeR 4Test Zipper assertDelMoveL 5Test Zipper assertDelMoveR 6Test Zipper delAllL 7Test Zipper delAllR 8Test Zipper delAllCloseL 9Test Zipper delAllIncCloseL :Test Zipper delAllCloseR ;Test Zipper delAllIncCloseR <Test Zipper sizeL/sizeR/ sizeZAVL =Test Zipper genTryOpenGE >Test Zipper genTryOpenLE ?:Test Zipper genOpenEither (also tests fill and fillClose) @Test anyBAVLtoEither ATest Show,Read,Eq instances BTest readPath BCDe      !"#$%&'()*+,-./0123456789:;<=>?@ABeB      !"#$%&'A()*+,-./0123456789:;<>=?@e      !"#$%&'()*+,-./0123456789:;<=>?@ABE !"#$%&'()*+,-./012345 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V W XYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_]^`abcdaef]ghijklm]gnopqrstuvwxyz{|}~                      ]^                                                                              ae]]]]      !"#$%&]'(]')*+,-./01234556789:;<=>?@ABCDEFGHIaJKLMNOPQRSTUVWXYZ[\]^]_`abcd AvlTree-3.0Data.Tree.AVL.Test.Counter Data.Tree.AVLData.Tree.AVL.Test.AllTestsData.Tree.AVL.TypesData.Tree.AVL.HeightData.Tree.AVL.SizeData.Tree.AVL.ReadData.Tree.AVL.Internals.HPushData.Tree.AVL.Internals.BinPathData.Tree.AVL.WriteData.Tree.AVL.Push Data.Tree.AVL.Internals.DelUtilsData.Tree.AVL.DeleteData.Tree.AVL.Internals.HJoinData.Tree.AVL.ListData.Tree.AVL.Test.UtilsData.Tree.AVL.JoinData.Tree.AVL.ZipperData.Tree.AVL.Internals.HSetData.Tree.AVL.SetData.Tree.AVL.Internals.HAVLData.Tree.AVL.SplitData.Tree.AVLXXIntgetCount resetCountAVLPZNEemptyisEmpty isNonEmpty singletonpairtryGetSingletonheight addHeight compareHeightsizeaddSize fastAddSizeclipSize assertReadLtryReadL assertReadRtryReadR genAssertRead genTryReadgenTryReadMaybegenDefaultRead genContainswriteL tryWriteLwriteR tryWriteRgenWrite genWriteFast genTryWrite genWriteMaybegenTryWriteMaybegenPushgenPush' genPushMaybe genPushMaybe'pushLpushRdelL assertDelLtryDelLdelR assertDelRtryDelR assertPopLtryPopL assertPopRtryPopRgenDelgenDelIf genDelMaybe genDelFast genAssertPop genTryPopgenAssertPopMaybegenTryPopMaybegenAssertPopIf genTryPopIfasListLtoListLasListRtoListRfoldrAVL foldrAVL' foldr1AVL foldr1AVL' foldr2AVL foldr2AVL'foldlAVL foldlAVL' foldl1AVL foldl1AVL' foldl2AVL foldl2AVL' foldrAVL_UINT mapAccumLAVL mapAccumLAVL' mapAccumRAVL mapAccumRAVL'mapAccumLAVL''mapAccumRAVL'' asTreeLenLasTreeL asTreeLenRasTreeR reverseAVLmapAVLmapAVL' traverseAVL replicateAVLflatten flatReverseflatMapflatMap' filterViaList filterAVL partitionAVLmapMaybeViaList mapMaybeAVL genAsTree genPushListgenSortAscendinggenSortDescending isBalancedisSorted isSortedOK minElements maxElementsjoin 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 deleteBAVLfullBAVLtoZAVLemptyBAVLtoPAVLanyBAVLtoEithergenUnion genUnionMaybe genUnionsgenIntersectiongenIntersectionMaybegenIntersectionToListLgenIntersectionAsListLgenIntersectionMaybeToListLgenIntersectionMaybeAsListL genDifferencegenDifferenceMaybe genIsSubsetOfgenIsSubsetOfBygenSymDifferencesplitAtLsplitAtRtakeLtakeRdropLdropRspanLspanR takeWhileL takeWhileR dropWhileL dropWhileRrotateLrotateR popRotateL popRotateR rotateByL rotateByRgenForkLgenForkRgenFork genTakeLE genDropGT genTakeGT genDropLE genTakeLT genDropGE genTakeGE genDropLTset2AVLavl2Setmap2AVLavl2MapallTeststestIsBalanced testIsSortedtestSize testClipSize testGenWrite testGenPush testGenDeltestGenAssertPop testPushL testPushRtestAssertDelLtestAssertDelRtestAssertPopL testPopHLtestAssertPopR testFlatten testFoldrAVL testFoldrAVL' testFoldlAVL testFoldlAVL' testFoldr1AVLtestFoldr1AVL' testFoldl1AVLtestFoldl1AVL'testMapAccumLAVLtestMapAccumRAVLtestMapAccumLAVL'testMapAccumRAVL'testMapAccumLAVL''testMapAccumRAVL''testJoin testJoinHAVL testConcatAVLtestFlatConcattestFilterViaList testFilterAVLtestMapMaybeViaListtestMapMaybeAVL testSplitAtL testTakeL testDropL testSplitAtR testTakeR testDropR testSpanLtestTakeWhileLtestDropWhileL testSpanRtestTakeWhileRtestDropWhileR testRotateL testRotateR testRotateByL testRotateByR testGenForkL testGenForkR testGenFork testGenTakeLE testGenTakeLT testGenTakeGT testGenTakeGE testGenUniontestGenSymDifferencetestGenUnionMaybetestGenIntersectiontestGenIntersectionMaybetestGenIntersectionAsListLtestGenIntersectionMaybeAsListLtestGenDifferencetestGenDifferenceMaybetestGenIsSubsetOftestGenIsSubsetOfBytestCompareHeighttestGenOpenClose testDelClosetestOpenLClosetestOpenRClose testMoveL testMoveR testInsertLtestInsertMoveL testInsertRtestInsertMoveRtestInsertTreeLtestInsertTreeR testDelMoveL testDelMoveR testDelAllL testDelAllRtestDelAllCloseLtestDelAllIncCloseLtestDelAllCloseRtestDelAllIncCloseR testZipSizetestGenTryOpenGEtestGenTryOpenLEtestGenOpenEithertestBAVLtoZippertestShowReadEq testReadPathcountincCount $fOrdXIntbase GHC.ClassescompareOrdghc-primGHC.Primseq avlTyConNameGHC.BoolTrue Data.MaybeJustfasNPfasZfasG2fasG3fas2NothingcSzhcSzNP3cSzZ3cSzNPcSzZcSzG2cSzG3cSz2readLNEreadLEreadRNEreadREpushHLpushHRpushHL_pushHR_BinPathEmptyBPFullBPbit0selgoLgoR genFindPath genOpenPathgenOpenPathWith writePathreadPath readPath_ insertPathwriteL'writeLNwriteLZwriteLPwriteR'writeRNwriteRZwriteRP COrdering-2.3Data.COrderingEqdelLNdelLZdelLPdelLNZdelLZZdelLPZdelLZNdelLZPdelRNdelRZdelRPdelRNZdelRZZdelRPZdelRZNdelRZPpopLNpopLZpopLPpopLNZpopLZZpopLPZpopLZNpopLZPpopRNpopRZpopRPpopRNZpopRZZpopRPZpopRZNpopRZP deletePathdelNdelZdelPdelNLdNLdelNRdNRdelZLdZLdelZRdZRdelPLdPLdelPRdPRpopHLpopHLNpopHLZpopHLPpopHLN_popHLZ_popHLP_popHLNZpopHLZZpopHLPZpopHLZNpopHLZPrebalNrebalPchkLNchkLZchkLPchkRNchkRZchkRPsubNsubZRsubZLsubPchkLN'chkLZ'chkLP'chkRN'chkRZ'chkRP'FalsejoinH'joinHLjoinHRjoinHspliceHspliceHLspliceHR spliceHL_ spliceHR_spliceLspliceLNspliceLZspliceLP spliceLPZspliceRspliceRPspliceRZspliceRN spliceRNZtoListL'toListR'GHC.BasefoldrGHC.Listfoldr1foldl Data.Listfoldl1 TestTreespathTree checkHeightcHcH_allAVLallNonEmptyAVLnumTreesexhaustiveTestflatAVLHAVLSHHE concatHAVLS mergePairs mergePairs_mkHAVLSmkHAVLS_PathRPLPEPclose_noLPnoRP closeNoLP closeNoRPaddSizeP addSizeRP addSizeLPopenL_openLNopenLZopenR_openRPopenRZ Data.EitherRightLeftinsertLHinsertRHopenFull openEmptyunionH unionMaybeH intersectionHintersectionMaybeH differenceHdifferenceMaybeHsymDifferenceHHAVL 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__ $fFunctorAVLFunctor $fShowAVLtitlepassedfailed