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

wdte: add sets #111

Open
DeedleFake opened this issue Sep 13, 2018 · 1 comment
Open

wdte: add sets #111

DeedleFake opened this issue Sep 13, 2018 · 1 comment

Comments

@DeedleFake
Copy link
Owner

Sets are quite useful, especially in a functional language like this. Scopes already provide a key-value mapping system, in a way, but it would be useful to be able to just store an unsorted list of unique values. Some functions, such as known, should probably return a set instead of an array.

@DeedleFake
Copy link
Owner Author

The issue is that sets have to be immutable in order to fit with the functional programing setup properly. There are two primary ways to implement them in a way that makes them immutable:

  • Back them with Scope-style linked list. This makes adding values without affecting existing references relatively simple and efficient, but means that lookups are O(n). It also complicates removals, to some extent.
  • Back them with a map[wdte.Func]struct{}. This makes lookups efficient, but requires that the entire set be copied every time something is added to it or removed.

@DeedleFake DeedleFake changed the title Add Sets wdte: add sets Nov 28, 2018
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