wdte icon indicating copy to clipboard operation
wdte copied to clipboard

wdte: add sets

Open DeedleFake opened this issue 7 years ago • 1 comments

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 avatar Sep 13 '18 03:09 DeedleFake

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 avatar Sep 14 '18 02:09 DeedleFake