feat: add Set stdlib module #466
Conversation
There was a problem hiding this comment.
This is awesome! Thanks for putting this together 😄
Re: make vs. init, make creates an empty structure, and init allows you to create a structure with some initial data. Hopefully that answers your question, but let me know if that's not what you were asking.
I think this largely looks good, but for the backing data structure, I believe that we do want it to be an Array, like Maps. Sets are essentially just Map<t, Void>, so the implementation can be pretty much exactly the same as Map, but the buckets would not have a value property. This way, your Set.contains and Set.add are both O(1) in the average case, versus O(n) to search/insert into a list.
Let me know if that makes sense or if there's anything I can clarify!
zweimach
force-pushed
the
set
branch
2 times, most recently
from
d3381c1
to
e4d47c3
Compare
stdlib/set.gr
Outdated
| let set = make(); | ||
| List.forEach((key) => { | ||
| add(key, set); | ||
| }, List.unique(list)); |
There was a problem hiding this comment.
We should be able to drop the unique call here, since add should take care of it (and it'll be faster!)
There was a problem hiding this comment.
Yes, add should be enough. Thank you.
stdlib/set.gr
Outdated
| let set = make(); | ||
| Array.forEach((key) => { | ||
| add(key, set); | ||
| }, Array.unique(array)); |
Add initial implementation of Set module using
List as thethe same underlying data structure as Map.It reuses many modified helper functions from the Map module.
Maybe we could unify those functions?
@ospencer, what is the convention for
initandmakefamily of functions?