• Announcement: Lua.org now officially recommends this forum as a meeting place for the Lua community

Sets please (1 Viewer)

Loggy

Newcomer
Joined
Dec 16, 2020
Messages
11
Reaction score
2
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

Newcomer
Joined
Dec 16, 2020
Messages
11
Reaction score
2
Wikipedia shows sets are available in quite a few programming languages:
 

darkwiiplayer

Newcomer
Joined
May 30, 2020
Messages
7
Reaction score
2
Age
27
Location
Germany
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

Newcomer
Joined
Dec 16, 2020
Messages
11
Reaction score
2
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

Newcomer
Joined
May 30, 2020
Messages
7
Reaction score
2
Age
27
Location
Germany
> 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

Newcomer
Joined
Jun 25, 2021
Messages
1
Reaction score
0
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

Newcomer
Creator of RiscLua
Joined
Oct 21, 2020
Messages
50
Reaction score
19
Age
82
Location
UK
Website
www.wra1th.plus.com
If you find yourself writing a program with sets (as opposed to ordered sets) in it, then you probably have the wrong algorithm.
 
Top