Standard Set type?

Does Haxe come with a standard Set type (data structure)? I’m not seeing it at api.haxe.org nor anywhere in the cookbook.

Nope.
But you can search for haxe libraries at lib.haxe.org or on github.
E.g. thx.Set - thx libraries

1 Like

I didn’t have much luck searching lib.haxe.org for “set type” or “set class”, but looking at your recommendation I see that there’s actually a bunch of thx libraries. Will try out thx.Set. Thanks!

Just curious, where do you use a Set for, and what is it different from a Map/Array?

In my mind, arrays, maps, and sets are all separate concepts, and so in code I want to use separate data structures to represent them.

The set of shirt colors in my closet is a set. In my code I want to use a set (data structure) to represent that. I could use a map with keys being colors and values being 1 or something, but now I’ve added extra mental friction between the concept (set of shirt colors) and the code representing it. Whenever I look at a map (in code), the first thing I think is, “ok, a map, got it, now what is mapping to what?”, but now I’d have to stop in my tracks and say, “back up, no, in this case I’m just using a map here because it’s handy; the colors (keys) aren’t mapping to anything useful, just ignore them”. Bleh.

Same thing with arrays: I could use an array to represent that set of colors, but then would have to check it each time before adding a color to make sure that color isn’t already in there; and anyway, I don’t need them ordered. Looking at my code later I might think, “I can’t remember, why did I want them ordered? Is some function elsewhere relying on them being ordered?”. And, “wait, why did I use an array for this instead of a set?”

***

Back when I first learned Perl 5, I used maps’ keys as sets, but it wasn’t optimal. I think at some point later I found a suitable set implementation on cpan and used that.

(Actually, as an aside, I remember from Perl 5 having quite a long list of best-practice “just always use these” cpan modules at the top of every program.)

Then when I learned Python I thought, “ah, finally, the big three (arrays, maps, and sets) are all right here”. Python even added a literal syntax for sets at some point. Clojure has all three as well. It strikes me as odd and old-fashioned that Haxe doesn’t have sets built in, but I can make a habit out of using thx.core any time I stumble and remember that Haxe doesn’t have them. That said, it may turn off some prospective new Haxe users to not have them built in.

2 Likes

I believe Polygonal has one:
https://github.com/polygonal/ds/tree/master/src/polygonal/ds

It is one of the best places to look for Haxe data types, I first used his library when it was originally in the as3 form, he has pooling and some other good stuff, obviously you can always try making your own datastructures. Every now and then he goes through and improves the library checking performance against targets, but I don’t think it updated often. It’s one of the libraries haxe uses to test against when major releases are made.

1 Like
1 Like

Fwiw, it’s very simple to create a basic Set abstract based on Array - something like

@:forward(iterator, keyValueIterator, pop, shift)
abstract Set<T>(Array<T>) to Array<T> {
    public inline function new(a:Array<T>) {
        this = [];
        for (v in a) push(v);
    }
    @:from static public function fromArray<T>(a:Array<T>) return new Set<T>(a);
    public function push(v:T) if (!has(v)) this.push(v);
    public function unshift(v:T) if (!has(v)) this.unshift(v);
    public function concat(s:Set<T>) for (v in s) push(v);
    inline function has(v:T) return this.indexOf(v) >= 0;
}

Should work in most situations.

2 Likes

@cambiata Basing a set on an array seems like a bad idea due to the complexity implications that has. You probably wouldn’t expect that adding something to a set would be O(n), same for checking whether the set contains something… a Map<T, Bool> works much better in that regard.

3 Likes

I tried to create an abstract set based on a Map with generic value as you suggest.

abstract Set<T>(Map<T, Bool>) {
    public function new() {
        this = new Map<T, Bool>();
    }

    public function push(val:T) this[val] = true;
    public function pop(val:T) this.remove(val);
    public function has(val:T):Bool return this.exists(val);
    public function toString() return toArray().toString();

	@:from static public function fromArray(arr:Array<Int>) {
        final newSet = new Set();
        for (val in arr) newSet.push(val);
        return newSet;
    }

    @:to public function toArray<T>() {
        return [for (val in this.keys()) val];
    };
}

But there’s an issue, when trying to create an instance of this type I get the following error:
Set.hx:3: characters 16-34 : Abstract haxe.ds.Map has no @:to function that accepts haxe.IMap<Set.T, Bool>

I think it’s related to Map not supporting all types, e.g. Float.

Do you have a suggestion to solve this issue?
I can just create a non-generic set, but it would be pretty nice to have a generic version.