Sets please (1 Viewer)

[Loggy]

One thing missing from all implementations AFAIK appears to be sets, with union, intersection etc operators.

In an earlier life I found Pascal (the best pre-open source revolution version was by Prospero) which taught me, as a then-Fortran user, the usefulness of understanding data structures as well as algorithms (praise to Knuth).

I regularly used set operations which were conveniently implemented as unlimited (effectively) membership at bit level so very efficient. In Lua the only way to do this would be to use associative tables which is very wasteful of space and efficiency.

There is the bit library (included in luajit) but that is rather low level - and (I assume) limits size or requires the set to be defined as a string which may make adding members messy and the library is aimed at twiddling bits rather than the more simple membership so includes shift, rotation etc which are not pertinent to sets.

 

[Loggy]

Wikipedia shows sets are available in quite a few programming languages:

 

[darkwiiplayer]

What's wrong with `{a = true, b = true, [20] = true}`? You can easily build your own set methods on top of that and if you do it as a C extension it will perform as if it were natively supported.

 

[Loggy]

Certainly you can use tables as sets and with metatables construct rules for membership, __adding, __deleting etc. But as these are associative tables rather than indexed tables, each access is quite slow and each element will take a considerable space. OK with GB memory and TB storage (if you can access it) this is not generally an issue but eventually these inefficiencies come home to bite you!

Sets (not multisets which are counts of membership so not binary) are best represented by bit patterns and I was looking for an equivalent that includes union, intersection, addition of new member, removal of new member etc. Even multisets with limited membership size can be more efficiently stored.

This may be a bit difficult in an interpreted environment where occasional access involves matching key patterns to find the index position of the set member so apart from the 0/1 or false/true storage that would be no different to using associative tables but for large applications, the small memory use and simplicity of set operations make for much more elegant code.

The first language I came across with sets was the original Jensen and Wirth Pascal and I have always found the concept interesting and a clear way of seeing code.

 

[darkwiiplayer]

> But as these are associative tables rather than indexed tables

Well, yes, but that's how sets usually work. Unless you want to throw them into an array, which nobody does for obvious reasons, you'll be using a hashset, which is not much different than a hashmap that maps values to booleans.

> Sets are best represented by bit patterns

How so?

 

[Limanam]

Certainly you can use tables as sets and with metatables construct rules for membership, __adding, __deleting etc. But as these are associative tables rather than indexed tables, each access is quite slow and each element will take a considerable space. OK with GB memory and TB storage (if you can access it) this is not generally an issue but eventually these inefficiencies come home to bite you!

Sets (not multisets which are counts of membership so not binary) are best represented by bit patterns and I was looking for an equivalent that includes union, intersection, addition of new member, removal of new member etc. Even multisets with limited membership size can be more efficiently stored.

This may be a bit difficult in an interpreted environment where occasional access involves matching key patterns to find the index position of the set member so apart from the 0/1 or false/true storage that would be no different to using associative tables but for large applications, the small memory use and simplicity of set operations make for much more elegant code.

The first language I came across with sets was the original Jensen and Wirth Pascal and I have always found the concept interesting and a clear way of seeing code.

Yeah sets are best representors,
That's good for me.

 

[GavinW]

If you find yourself writing a program with sets (as opposed to ordered sets) in it, then you probably have the wrong algorithm.