You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Original bug ID: 350 Reporter: administrator Status: closed Resolution: won't fix Priority: normal Severity: feature Category: ~DO NOT USE (was: OCaml general)
Bug description
Hello,
I have just noticed that there is no way to write some important class of
tail recursive functions on sets and maps (not even using impure features)
without potentially degrading performance by orders of magnitude. This
can be easily resolved by adding a "decompose" function.
E.g. here is the one for sets:
val decompose : t -> (elt * t * t) option
let decompose = function
| Empty -> None
| Node (l, v, r, _) -> Some (v, l, r)
This function is sound, of course, because subtrees are always balanced
and therefore sets, too. If there is a top node, the set is split up into
some pivot element and two sets, the one containing only lower, the other
only greater elements. This function is surely useful for many purposes.
The rationale behind this function is that we can get rid of the stack
when treating many sets, e.g. in purely functional graphs whose nodes use
sets to contain connections to neighbour nodes. Such graphs may easily
contain thousands of nodes, each of them being connected to maybe hundreds
of others. If we want to iterate through the graph in certain ways,
we could overflow the stack. To prevent this, one would currently have
to flatten all sets contained in traversed nodes to lists even if this
were not necessary to solve the problem (e.g. find a particular path).
With the function above, one can always get another unique element of
the set without having to convert it to a list first, storing only the
subsets in a list instead of all of their elements (flattened). A somewhat
similar trick is used in the already implemented "compare"-function of
sets to efficiently compare sets without having to convert them to lists.
The reason why I used an option instead of an exception for the "Empty"
case is that setting up exception handlers can destroy tail-recursiveness
again, though recursion is the most likely context in which this function
is used.
Uff, I hope my explanations were not too long and weird... ;)
Original bug ID: 350
Reporter: administrator
Status: closed
Resolution: won't fix
Priority: normal
Severity: feature
Category: ~DO NOT USE (was: OCaml general)
Bug description
Hello,
I have just noticed that there is no way to write some important class of
tail recursive functions on sets and maps (not even using impure features)
without potentially degrading performance by orders of magnitude. This
can be easily resolved by adding a "decompose" function.
E.g. here is the one for sets:
val decompose : t -> (elt * t * t) option
let decompose = function
| Empty -> None
| Node (l, v, r, _) -> Some (v, l, r)
This function is sound, of course, because subtrees are always balanced
and therefore sets, too. If there is a top node, the set is split up into
some pivot element and two sets, the one containing only lower, the other
only greater elements. This function is surely useful for many purposes.
The rationale behind this function is that we can get rid of the stack
when treating many sets, e.g. in purely functional graphs whose nodes use
sets to contain connections to neighbour nodes. Such graphs may easily
contain thousands of nodes, each of them being connected to maybe hundreds
of others. If we want to iterate through the graph in certain ways,
we could overflow the stack. To prevent this, one would currently have
to flatten all sets contained in traversed nodes to lists even if this
were not necessary to solve the problem (e.g. find a particular path).
With the function above, one can always get another unique element of
the set without having to convert it to a list first, storing only the
subsets in a list instead of all of their elements (flattened). A somewhat
similar trick is used in the already implemented "compare"-function of
sets to efficiently compare sets without having to convert them to lists.
The reason why I used an option instead of an exception for the "Empty"
case is that setting up exception handlers can destroy tail-recursiveness
again, though recursion is the most likely context in which this function
is used.
Uff, I hope my explanations were not too long and weird... ;)
Best regards,
Markus Mottl
--
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl
The text was updated successfully, but these errors were encountered: