--------------9EA6BDBDB10719DF95E85C2F Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Erik Zuurbier wrote: > Hi Fabien, Hi Erik, Please do accept my apologies for having you wait so long for an answer, but I have had some troubles with my computer lately. Also, let me from the outset precise to potential readers the precise topic of the letter. This is an answer to Erik requesting documentation about the AVL Tree package I offered on the Clean library pages. People interested in the development of an algorithms and data structures library tailored for Clean may find the following interesting and want to contact me - and Erik - privately. I must say, however, that multi-parameter type classes expected in Clean 2.0 may be wanted to achieve a good design for such a library. Erik, I also noted while rereading the code and answering some of your questions that implementations for the following overloaded map operators were laking : mapInsertWith, mapFindInsertWith, mapEraseWith. I plan to provide them quickly, and better documentation, in a next release. > I found your AVL-Tree package on the Clean list. Very impressive. I > thank you for taking the time and trouble to publish it. It looks well > designed. It would gain a lot of usefullness if some documentation were > added though. The main DCL (the only one one should need to understand > as a user) contains the following. I'll add some comments / questions > after => > Without answers to these questions, the package is totally useless to > me. Sure, I can dig up scientific articles about AVL-trees, or wade > through all your modules to find out. And I am sure it will give me a > good feeling: "Now I am an AVL-Tree expert!" But the point of Clean's > module system is that I should be able to use something without knowing > all the internals. Therefore I would like to invite you to take the > time to add some comments to this single DCL. While doing that, you > could also spend some words (the bare minimum) on explaining what an > AVL-Tree is, and how it compares to some other common container data > structures. > Regards Erik Zuurbier Thank you very much Erik for showing some interest in that library, I was desperately hoping it would be useful for somebody else than me :) Yes, you're absolutely right about the lack of documentation, I do agree with you that undocumented software is hardly usable. At the time when I undertook the development of the package, I began writing a complete doc explaining some of the theory of AVL trees, and the specific interest in the pure functional implementation offered here. I didn't take the time, though, to finish... However, I may well go back at work, seeing some interest from potential users :) Before I answer your specific questions, let me put a few words about the motivation and history of that library. I am a software engineer with a strong ADA/C++ background, and a passion for algorithms and data structures. I discovered Clean when looking for a good FPL to which I wanted to port a Prolog prototype program in order to gain efficiency and better control over the structure of the software - static typing -. I found, and still find, the language absolutely terrific, but I was appalled at seeing that virtually no algorithms and moderately advanced data structure library was provided with the language, as is now the case for C++ with the famous STL. Technically, however, most of the C++ features used in the STL design that people marvel at can be equally matched by Clean : lazy lists provide some kind of unidirectional iterators, polymorphic typing provides equivalent or superior facilities to C++ templates, higher-orderness and automatic currying allows for far more flexible designs that with so-called C++ 'function objects', and so on... Having used STL in some algorithmic-intensive C++ programs I have built - mostly Automatic Test Generator Programs for electronic boards - I appreciated the beauty of its design, and especially the practicalness of the few containers provided in STL, among which the map<> is my preferred one. You can guess now that the things I wanted most was to have the equivalent of STL in Clean, and so I started working on a Clean equivalent for map<>. The AVL-Tree package I offered is one part of that grand dream. I adopted a similar design as in STL, where the map<> and set<> containers are built on top of red-black binary search trees : in the AVL-Tree package, you have similary map<> and set<> operations built on top of the AVL-tree persistent binary search tree. So much for the motivation and history. Now allow me for a digression about the intrinsic interest of the implementation. Although you may find FPL implementations of balanced binary search tree in the literature - see for example the excellent Chris Okasaki's book 'Purely Functional Data Structures' - seldom will you find an implementation providing for the deletion operation. Also, AVL-Trees are usually implemented with an extra integer field on each node holding the height of the node - see Mark Allen Weiss's various algorithms books for Ada, C++, etc.. - in order to ease the implementation of rebalancing operations. Not so in the offered AVL-Tree package, where only the local imbalance status of the node is encoded in the node constructor. To the best of my knowledge, there exists only one paper - I do not have the reference handy - that describes such an implementaion in a pure FPL, but it does not describe deletion operations... Now let's go to the specifics :) > ========= > :: Tree a > > instance order ( Tree x ) | order x => Why can this not be | Ord x > (StdEnv)? The Ord x class of StdEnv defines overloaded operators based on the < overloaded operator, as follows : class (<) infix 4 a :: !a !a -> Bool // True if arg1 is less than arg2 class Ord a | < a where (>) infix 4 :: !a !a -> Bool | Ord a (>) x y :== y < x (<=) infix 4 :: !a !a -> Bool | Ord a (<=) x y :== not (y<x) (>=) infix 4 :: !a !a -> Bool | Ord a (>=) x y :== not (x<y) min::!a !a -> a | Ord a min x y :== if (x<y) x y max::!a !a -> a | Ord a max x y :== if (x<y) y x You see that the (<) overloaded operator returns a boolean, allowing for a two-branch case analysis based on the ordering of its arguments. In case x < y is false, then you will need an additional y < x check to assess whether y is lower than x, or y is equal to x - according to the ordering < -. When the x and y objects you are comparing are primitive objects, such as integers, the cost of repeating the second y < x comparison is negligible, but when the x and y objects are more complex, for example are sequences of elements whose ordering is the lexicographical ordering derived from the elements' ordering, you get an O(N) worst-case complexity for the comparison operation. In that case, having a three-branch 'comparison' operation that immediately returns '<' , '=', or '>' according to the ordering of the arguments will save an O(N) computation cost. This is what the overloaded order operator does, as the definition below shows : :: Order = LT | EQ | GT :: Order1 x :== ! x -> Order :: Order2 x :== ! x ! x -> Order class order x :: Order2 x > instance isEmpty Tree > instance forward Tree => What is this? > instance backward Tree => What is this? The elements stored in the AVL trees must overload the order operation. In turn, overloads of that operation are provided for Clean's lists, 2 and 3-tuples and various arrays and...AVL Trees themselves. That way, data containers are fully compositonal - as in STL - you can have trees of lists of arrays of trees with the order operator automatically defined thans to the magic of Clean's type classes. A similar trick C++ template trick is used in STL. The overloaded operators forward and backward, as declared below : class forward k :: ( k x ) -> [ x ] class backward k :: ( k x ) -> [ x ] lazily transforms their argument of type ( k x ) into a lazy list of x, [ x ]. The lazy list [ x ] can be understood as a kind of unidirectional iterator allowing to traverse the collection of elements held in the ( k x ) container. In general, the container is expected to hold its elements in some 'natural' order, according to the underlying data structure. The 'forward' iterator generates the list following that natural order, whereas the 'backward' iterator generates the list in the reverse order. In the case of AVL search trees, the order of the elements defines a sorted sequence. Also, the iterators have O(N) complexity, in the sense that the cost of generating the list for a container of length N is proportional to N. So, the instance declarations you are asking about states that the AVL tree data structures implements operations of sequential traversal. The various setX overloaded operators provide operations for dynamic sets, with logarithmic worst-case complexity in the size of the set. The following instance declarations below state that the AVL Tree data type does implement these operations. > instance setInsertWith Tree => What is this? > instance setEraseWith Tree => What is this? > instance setFindWith Tree => What is this? The additional With in the name of the operator indicates that instead of using the standard overloaded order operator, you provide your own to the operation. This is made explicit in the signature of these overloaded operators, where the ( Order2 x ) binary comparator or ( Order1 x ) unary comparator must be provided as an argument to the operator : class setInsertWith k :: ( Order2 x ) x ( k x ) -> k x class setFindWith k :: ( x -> z ) z ( Order1 x ) ( k x ) -> z class setEraseWith k :: ( Order1 x ) ( k x ) -> k x The corresponding operations that take the default overloaded order for the x type are simply defined as specialization of these, in the obvious manner below : setInsert :: x ( k x ) -> k x | setInsertWith k & order x setInsert x k = setInsertWith order x k setFind :: ( x -> y ) y x ( k x ) -> y | setFindWith k & order x setFind y n x k = setFindWith y n ( order x ) k setErase :: x ( k x ) -> k x | setEraseWith k & order x setErase x k = setEraseWith ( order x ) k Now, the operations do the following : setInsert inserts in O(log(N)) time an element x into a sorted set container ( k x ), based on the order specified as an argument, or the default overloaded order. setFind retrieves in O(log(N)) time an element x into a sorted set container ( k x ), based on the order specified as an argument, or the default overloaded order. setErase removes in O(log(N)) time an element x from a sorted set container ( k x ), based on the order specified as an argument, or the default overloaded order. > instance mapUpdateWith Tree => What is this? A similar remark for mapUpdate and mapUpdateWith about the default overloaded order, or provided by the user. Now, given an element x, an element y0 and a function f : y -> y mapUpdate searches the map for an ( x , y ) entry, and updates it to ( x , f y ) in case such an entry is found, based on the key x. If no such an entry is found, the entry ( x , f y0 ) is instead inserted into the map. All this in O(log(N)) time. A typical use of that operation is to accumulate in a map statistical entries about elements, for example, computing in O(Nlog(N)) time the number of occurrences of elements, as the following example demonstrates : multiset :: ( [ x ] -> [ ( x , Int ) ] ) | order x multiset = forward o foldr ( \ x -> mapUpdate (+) 0 ( x , 1 ) ) treeEmpty The [ x ] list is folded with mapUpdate into an Tree ( x , Int ) that implements a map from elements x to occurences counts. The y0 argument of mapUpdate is 0, for the initial count, the update function f is (+), and the y element used to update the map entry is 1. Afterward, the tree is folded into a list using the forward iterator. A similar computation pattern applies to the following function that groups in O(Nlog(N)) time ( x , y ) pairs listed in a [ ( x , y ) ] list based on the value of the key x : group :: ([(a,b)] -> [(a,[b])]) | order a group = forward o foldr ( \ xy -> mapUpdate cons [] xy ) treeEmpty where cons h t = [ h : t ] > instance mapMap Tree => What is this? Well, mapMap implements the analogue of the map :: ( x -> y ) [ x ] -> [ y ] operations for lists. That is : class mapMap k :: ( y -> z ) ( k ( x , y ) ) -> k ( x , z ) states that the map container k from x keys to y values support the map operation. Normally, you will use the AVL Tree through the overloaded set and map operators seen above. You will only need - usually - the treeEmpty function to build an empty tree, to which you will apply the map or sets functions, according to the way you want to consider the tree : either as a map, or a set. > treeEmpty :: Tree .a > treeIsEmpty :: ! ( Tree .a ) -> .Bool > treeCheck :: . ( Tree a ) -> .Bool | order a The following are so to speak 'internal' operations proper to the AVL Tree data structure, that are used to implement the various instances of the sets and maps overloaded operators. You normally won't want to use these directly. > treeInsert :: ( Order2 a ) a ! ( Tree a ) -> Tree a > => What is (Order2 a)? > treeFind :: ( a -> b ) b ( Order1 a ) ! ( Tree a ) -> > b => What is this (a -> b) and what is (Orderl a)? You have the following definitions in the orderClass module : :: Order = LT | EQ | GT :: Order1 x :== ! x -> Order :: Order2 x :== ! x ! x -> Order That is, Order represents the relative order of two elements : LT stands for '<', EQ stands for '=', and 'GT' stands for '>'. Order2 x is then the type of a function comparing two elements, a so-called 'binary' comparator and Order1 x is then the type of a a function comparing an element to a supposedly known other element. An ( Order1 x ) is usually a partially applied ( Order2 x ). > treeFindInsert :: ( Order2 a ) ( a -> b ) ( ( Tree a ) -> b ) a ! ( > Tree a ) -> b => What is ((Tree a)->b)? Hmmm ! You put the figure on the hot spot. I won't give you the full details of the implementation's logic. But let me say only that the ( Tree a ) -> b argument is a function that transforms a tree, and that that function is internally used as an argument to an higher order function that rebalances the locally modified tree... > treeErase :: ( Order1 a ) !( Tree a ) -> Tree > a => What is this? This is also an internal operation implementing the deletion of a node of the tree, based on a unary comparator to search for the tree element. > treeUnsafeUpdate :: ( Order1 a ) ( a -> a ) a ! ( Tree a ) -> Tree > a => What is so unsafe? What is a if you have (a->a)? > > treeUnsafeMap :: ( a -> b ) ! ( Tree a ) -> Tree > b => What is so unsafe? These operation are said to be unsafe, because used unwisely they may violate the invariant of the AVL search Tree according to which the values at the nodes are sorted in an infix traversal of the tree. These operations are internally used - wisely - for the implementation of the overloaded operators mapUpdate and mapMap, which are safe. > treeForward :: ! ( Tree . a ) -> [ .a ] => What is > this? (Sure I can guess, but why should you let me?) > => How does it relate to instance forward > Tree? This is directly the implementation of the forward iterator for the AVL tree. > treeBackward :: ! ( Tree . a ) -> [ .a ] => What is > this? How does it relate to instance backward Tree? Similar remark for the backward operator. > ========= Best regards, Fabien TODESCATO --------------9EA6BDBDB10719DF95E85C2F Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit <!doctype html public "-//w3c//dtd html 4.0 transitional//en"> Erik Zuurbier wrote:Hi Fabien,Hi Erik,Please do accept my apologies for having you wait so long for an answer, but I have had some troubles with my computer lately. Also, let me from the outset precise to potential readers the precise topic of the letter. This is an answer to Erik requesting documentation about the AVL Tree package I offered on the Clean library pages. People interested in the development of an algorithms and data structures library tailored for Clean may find the following interesting and want to contact me - and Erik - privately. I must say, however, that multi-parameter type classes expected in Clean 2.0 may be wanted to achieve a good design for such a library.
Erik, I also noted while rereading the code and answering some of your questions that implementations for the following overloaded map operators were laking : mapInsertWith, mapFindInsertWith, mapEraseWith. I plan to provide them quickly, and better documentation, in a next release.
I found your AVL-Tree package on the Clean list. Very impressive. I thank you for taking the time and trouble to publish it. It looks well designed. It would gain a lot of usefullness if some documentation were added though. The main DCL (the only one one should need to understand as a user) contains the following. I'll add some comments / questions after =>Without answers to these questions, the package is totally useless to me. Sure, I can dig up scientific articles about AVL-trees, or wade through all your modules to find out. And I am sure it will give me a good feeling: "Now I am an AVL-Tree expert!" But the point of Clean's module system is that I should be able to use something without knowing all the internals. Therefore I would like to invite you to take the time to add some comments to this single DCL. While doing that, you could also spend some words (the bare minimum) on explaining what an AVL-Tree is, and how it compares to some other common container data structures.Regards Erik Zuurbier
Thank you very much Erik for showing some interest in that library, I was desperately hoping it would be useful for somebody else than me :) Yes, you're absolutely right about the lack of documentation, I do agree with you that undocumented software is hardly usable. At the time when I undertook the development of the package, I began writing a complete doc explaining some of the theory of AVL trees, and the specific interest in the pure functional implementation offered here. I didn't take the time, though, to finish... However, I may well go back at work, seeing some interest from potential users :)Before I answer your specific questions, let me put a few words about the motivation and history of that library. I am a software engineer with a strong ADA/C++ background, and a passion for algorithms and data structures. I discovered Clean when looking for a good FPL to which I wanted to port a Prolog prototype program in order to gain efficiency and better control over the structure of the software - static typing -. I found, and still find, the language absolutely terrific, but I was appalled at seeing that virtually no algorithms and moderately advanced data structure library was provided with the language, as is now the case for C++ with the famous STL. Technically, however, most of the C++ features used in the STL design that people marvel at can be equally matched by Clean : lazy lists provide some kind of unidirectional iterators, polymorphic typing provides equivalent or superior facilities to C++ templates, higher-orderness and automatic currying allows for far more flexible designs that with so-called C++ 'function objects', and so on... Having used STL in some algorithmic-intensive C++ programs I have built - mostly Automatic Test Generator Programs for electronic boards - I appreciated the beauty of its design, and especially the practicalness of the few containers provided in STL, among which the map<> is my preferred one. You can guess now that the things I wanted most was to have the equivalent of STL in Clean, and so I started working on a Clean equivalent for map<>. The AVL-Tree package I offered is one part of that grand dream. I adopted a similar design as in STL, where the map<> and set<> containers are built on top of red-black binary search trees : in the AVL-Tree package, you have similary map<> and set<> operations built on top of the AVL-tree persistent binary search tree.
So much for the motivation and history. Now allow me for a digression about the intrinsic interest of the implementation. Although you may find FPL implementations of balanced binary search tree in the literature - see for example the excellent Chris Okasaki's book 'Purely Functional Data Structures' - seldom will you find an implementation providing for the deletion operation. Also, AVL-Trees are usually implemented with an extra integer field on each node holding the height of the node - see Mark Allen Weiss's various algorithms books for Ada, C++, etc.. - in order to ease the implementation of rebalancing operations. Not so in the offered AVL-Tree package, where only the local imbalance status of the node is encoded in the node constructor. To the best of my knowledge, there exists only one paper - I do not have the reference handy - that describes such an implementaion in a pure FPL, but it does not describe deletion operations...
Now let's go to the specifics :)
=========The Ord x class of StdEnv defines overloaded operators based on the < overloaded operator, as follows :
:: Tree ainstance order ( Tree x ) | order x => Why can this not be | Ord x (StdEnv)?
class (<) infix 4 a :: !a !a -> Bool // True if arg1 is less than arg2
class Ord a | < a
where
(>) infix 4 :: !a !a -> Bool | Ord a
(>) x y :== y < x(<=) infix 4 :: !a !a -> Bool | Ord a
(<=) x y :== not (y<x)(>=) infix 4 :: !a !a -> Bool | Ord a
(>=) x y :== not (x<y)min::!a !a -> a | Ord a
min x y :== if (x<y) x ymax::!a !a -> a | Ord a
max x y :== if (x<y) y xYou see that the (<) overloaded operator returns a boolean, allowing for a two-branch case analysis based on the ordering of its arguments. In case x < y is false, then you will need an additional y < x check to assess whether y is lower than x, or y is equal to x - according to the ordering < -. When the x and y objects you are comparing are primitive objects, such as integers, the cost of repeating the second y < x comparison is negligible, but when the x and y objects are more complex, for example are sequences of elements whose ordering is the lexicographical ordering derived from the elements' ordering, you get an O(N) worst-case complexity for the comparison operation. In that case, having a three-branch 'comparison' operation that immediately returns '<' , '=', or '>' according to the ordering of the arguments will save an O(N) computation cost. This is what the overloaded order operator does, as the definition below shows :
:: Order = LT | EQ | GT
:: Order1 x :== ! x -> Order
:: Order2 x :== ! x ! x -> Orderclass order x :: Order2 x
instance isEmpty TreeThe elements stored in the AVL trees must overload the order operation. In turn, overloads of that operation are provided for Clean's lists, 2 and 3-tuples and various arrays and...AVL Trees themselves. That way, data containers are fully compositonal - as in STL - you can have trees of lists of arrays of trees with the order operator automatically defined thans to the magic of Clean's type classes. A similar trick C++ template trick is used in STL.
instance forward Tree => What is this?
instance backward Tree => What is this?The overloaded operators forward and backward, as declared below :
class forward k :: ( k x ) -> [ x ]
class backward k :: ( k x ) -> [ x ]lazily transforms their argument of type ( k x ) into a lazy list of x, [ x ]. The lazy list [ x ] can be understood as a kind of unidirectional iterator allowing to traverse the collection of elements held in the ( k x ) container. In general, the container is expected to hold its elements in some 'natural' order, according to the underlying data structure. The 'forward' iterator generates the list following that natural order, whereas the 'backward' iterator generates the list in the reverse order. In the case of AVL search trees, the order of the elements defines a sorted sequence. Also, the iterators have O(N) complexity, in the sense that the cost of generating the list for a container of length N is proportional to N. So, the instance declarations you are asking about states that the AVL tree data structures implements operations of sequential traversal.
The various setX overloaded operators provide operations for dynamic sets, with logarithmic worst-case complexity in the size of the set. The following instance declarations below state that the AVL Tree data type does implement these operations.
instance setInsertWith Tree => What is this?The additional With in the name of the operator indicates that instead of using the standard overloaded order operator, you provide your own to the operation. This is made explicit in the signature of these overloaded operators, where the ( Order2 x ) binary comparator or ( Order1 x ) unary comparator must be provided as an argument to the operator :
instance setEraseWith Tree => What is this?
instance setFindWith Tree => What is this?class setInsertWith k :: ( Order2 x ) x ( k x ) -> k x
class setFindWith k :: ( x -> z ) z ( Order1 x ) ( k x ) -> z
class setEraseWith k :: ( Order1 x ) ( k x ) -> k xThe corresponding operations that take the default overloaded order for the x type are simply defined as specialization of these, in the obvious manner below :
setInsert :: x ( k x ) -> k x | setInsertWith k & order x
setInsert x k = setInsertWith order x ksetFind :: ( x -> y ) y x ( k x ) -> y | setFindWith k & order x
setFind y n x k = setFindWith y n ( order x ) ksetErase :: x ( k x ) -> k x | setEraseWith k & order x
setErase x k = setEraseWith ( order x ) kNow, the operations do the following :
setInsert inserts in O(log(N)) time an element x into a sorted set container ( k x ), based on the order specified as an argument, or the default overloaded order.
setFind retrieves in O(log(N)) time an element x into a sorted set container ( k x ), based on the order specified as an argument, or the default overloaded order.
setErase removes in O(log(N)) time an element x from a sorted set container ( k x ), based on the order specified as an argument, or the default overloaded order.
instance mapUpdateWith Tree => What is this?A similar remark for mapUpdate and mapUpdateWith about the default overloaded order, or provided by the user. Now, given an element x, an element y0 and a function f : y -> y mapUpdate searches the map for an ( x , y ) entry, and updates it to ( x , f y ) in case such an entry is found, based on the key x. If no such an entry is found, the entry ( x , f y0 ) is instead inserted into the map. All this in O(log(N)) time. A typical use of that operation is to accumulate in a map statistical entries about elements, for example, computing in O(Nlog(N)) time the number of occurrences of elements, as the following example demonstrates :multiset :: ( [ x ] -> [ ( x , Int ) ] ) | order x
multiset = forward o foldr ( \ x -> mapUpdate (+) 0 ( x , 1 ) ) treeEmptyThe [ x ] list is folded with mapUpdate into an Tree ( x , Int ) that implements a map from elements x to occurences counts. The y0 argument of mapUpdate is 0, for the initial count, the update function f is (+), and the y element used to update the map entry is 1. Afterward, the tree is folded into a list using the forward iterator.
A similar computation pattern applies to the following function that groups in O(Nlog(N)) time ( x , y ) pairs listed in a [ ( x , y ) ] list based on the value of the key x :
group :: ([(a,b)] -> [(a,[b])]) | order a
group = forward o foldr ( \ xy -> mapUpdate cons [] xy ) treeEmpty
where
cons h t = [ h : t ]
instance mapMap Tree => What is this?Well, mapMap implements the analogue of the map :: ( x -> y ) [ x ] -> [ y ] operations for lists. That is :class mapMap k :: ( y -> z ) ( k ( x , y ) ) -> k ( x , z )
states that the map container k from x keys to y values support the map operation.
Normally, you will use the AVL Tree through the overloaded set and map operators seen above. You will only need - usually - the treeEmpty function to build an empty tree, to which you will apply the map or sets functions, according to the way you want to consider the tree : either as a map, or a set.
treeEmpty :: Tree .aThe following are so to speak 'internal' operations proper to the AVL Tree data structure, that are used to implement the various instances of the sets and maps overloaded operators. You normally won't want to use these directly.
treeIsEmpty :: ! ( Tree .a ) -> .Bool
treeCheck :: . ( Tree a ) -> .Bool | order atreeInsert :: ( Order2 a ) a ! ( Tree a ) -> Tree a => What is (Order2 a)?You have the following definitions in the orderClass module :
treeFind :: ( a -> b ) b ( Order1 a ) ! ( Tree a ) -> b => What is this (a -> b) and what is (Orderl a)?:: Order = LT | EQ | GT
:: Order1 x :== ! x -> Order
:: Order2 x :== ! x ! x -> OrderThat is, Order represents the relative order of two elements : LT stands for '<', EQ stands for '=', and 'GT' stands for '>'. Order2 x is then the type of a function comparing two elements, a so-called 'binary' comparator and Order1 x is then the type of a a function comparing an element to a supposedly known other element. An ( Order1 x ) is usually a partially applied ( Order2 x ).
treeFindInsert :: ( Order2 a ) ( a -> b ) ( ( Tree a ) -> b ) a ! ( Tree a ) -> b => What is ((Tree a)->b)?Hmmm ! You put the figure on the hot spot. I won't give you the full details of the implementation's logic. But let me say only that the ( Tree a ) -> b argument is a function that transforms a tree, and that that function is internally used as an argument to an higher order function that rebalances the locally modified tree...treeErase :: ( Order1 a ) !( Tree a ) -> Tree a => What is this?This is also an internal operation implementing the deletion of a node of the tree, based on a unary comparator to search for the tree element.treeUnsafeUpdate :: ( Order1 a ) ( a -> a ) a ! ( Tree a ) -> Tree a => What is so unsafe? What is a if you have (a->a)?These operation are said to be unsafe, because used unwisely they may violate the invariant of the AVL search Tree according to which the values at the nodes are sorted in an infix traversal of the tree. These operations are internally used - wisely - for the implementation of the overloaded operators mapUpdate and mapMap, which are safe.treeUnsafeMap :: ( a -> b ) ! ( Tree a ) -> Tree b => What is so unsafe?
treeForward :: ! ( Tree . a ) -> [ .a ] => What is this? (Sure I can guess, but why should you let me?)This is directly the implementation of the forward iterator for the AVL tree.
=> How does it relate to instance forward Tree?treeBackward :: ! ( Tree . a ) -> [ .a ] => What is this? How does it relate to instance backward Tree?Similar remark for the backward operator.=========Best regards, Fabien TODESCATO