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

Set should have a way to access the "middle" element and its left and right nodes. #5740

Closed
vicuna opened this issue Aug 27, 2012 · 4 comments

Comments

@vicuna
Copy link

vicuna commented Aug 27, 2012

Original bug ID: 5740
Reporter: furuse
Assigned to: @alainfrisch
Status: resolved (set by @alainfrisch on 2016-12-09T08:22:29Z)
Resolution: won't fix
Priority: normal
Severity: feature
Version: 4.00.0
Category: standard library

Bug description

It would be handy if Set provides an easy access to its binary tree structure:

val middle (* or whatever *) : t -> (t * elt * t) option

let middle = function
| Empty -> None
| Node (left, v, right, _) -> Some (left, v, right)

Currently we can have this function with very dirty workaround using iter/filter and side effects. Such a implementation by me recently broke by the change of search order of filter.

This function exposes the internal detail of Set, therefore it is against the spirit of the implementation encapsulation, but still it is very useful.

@vicuna
Copy link
Author

vicuna commented Nov 17, 2012

Comment author: @xavierleroy

Hi Jun,

This function is not just "against the spirit of the implementation encapsulation": it is not even a function, in that it can map equal sets (according to the "equal" predicate) to different results.

So, pray tell, what is a good use case for this function? Something that you can't achieve just by using the current Set interface, esp. Set.fold?

@vicuna
Copy link
Author

vicuna commented Nov 21, 2012

Comment author: thelema

Batteries has a Set.choose value that just returns an arbitrary element of a non-empty set, which I find useful for initializing folds where there's no reasonable initial value to start the fold with (and just a pain to be constantly matching None) or recursive functions that repeatedly choose an element of the set and do some work that possibly removes other elements from the set before repeating.

This pattern of removing an arbitrary element of a set became common enough that I added a Set.pop : t -> elt * t that returns an arbitrary element and a new set of the remaining elements.

That said, neither of these breach the encapsulation, as long as you don't depend on any properties of the chosen element.

@vicuna
Copy link
Author

vicuna commented Jan 4, 2013

Comment author: berenger

Don't you need a find actually?

Cf. #5864

@vicuna
Copy link
Author

vicuna commented Dec 9, 2016

Comment author: @alainfrisch

No activity for a long time, and Xavier was not convinced by the proposal ==> marking as "won't fix" for now.

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

2 participants