Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

problem writing tail-recursive functions on sets and maps #2756

Closed
vicuna opened this issue May 2, 2001 · 1 comment
Closed

problem writing tail-recursive functions on sets and maps #2756

vicuna opened this issue May 2, 2001 · 1 comment

Comments

@vicuna
Copy link

vicuna commented May 2, 2001

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

@vicuna
Copy link
Author

vicuna commented Nov 13, 2002

Comment author: administrator

Usefulness is unclear; proposed extension would be hard to document :-)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant