[simple_set] simple version of set

[lightmark]

Description

I simplified insert and remove api by enforcing copy + drop

Test Plan

ut

[geekflyer]

please add a method to get all the set elements, like:

public fun into_keys<K: copy + drop>(self: SimpleSet<K>): vector<K>

[lightmark]

please add a method to get all the set elements, like:

public fun into_keys<K: copy + drop>(self: SimpleSet<K>): vector<K>

Can you explain the necessity as SimpleMap doesn't provide this.

[wrwg]

please add a method to get all the set elements, like:

public fun into_keys<K: copy + drop>(self: SimpleSet<K>): vector<K>

Let’s first talk about this as this causes problems by exposing implementation details via the exposed order. There is a reason we do not have this for SimpleMap

[geekflyer]

please add a method to get all the set elements, like:

public fun into_keys<K: copy + drop>(self: SimpleSet<K>): vector<K>

Can you explain the necessity as SimpleMap doesn't provide this.

A common use-case for Sets is to use them as an intermediary to dedupe values in a vector and return the deduped items as a simple vector. Order doesn't matter.

[lightmark]

@movekevin Think of undroppable(uncopyable) objects, how do you want to use it with set? Do you remember why Table has key type copyable required?.. For example, contains() need a &Key so in order to know it contains a key you have to pass in a reference to the key. If this key is not copyable, how do you get it's reference when itself is in the set. It makes little sense, right?

[movekevin]

do

Your point about copyable makes sense. But what about droppable?

[davidiw]

I'm fine with this, but I wonder why we didn't just make a dummy value and use SimpleMap.

SimpleMap<Key, DummyValue> where struct DummyValue has store { }

[wrwg]

I don't think we can have this part of our framework and call it a "set" because it doesn't has a very simple property important for sets: equality. Equality of two sets with different order of insertion is not given.

Being able to compare sets for equality independent of insertion order is a very common use case for sets (I used it often in my daily programming). This cannot go like this into the framework.

Really torn about this. It feels this will be still a utility of use, but set equality is really a common use case (whereas map equality isn't, so SimpleMap not having this is ok).

We are really doctoring around that we do not have an adequate native comparison operator in Move. We should add this one ASAP.

In the meantime, maybe we should call this SimpleIntensionalSet. An intensional data structure, in some mathematic worlds, is one which does not have equality (in difference to extensionality, which is characterized by the law of extensionality, i.e. x == y <==> ALL e. (e in x) == (e in y).

[movekevin]

I don't think we can have this part of our framework and call it a "set" because it doesn't has a very simple property important for sets: equality. Equality of two sets with different order of insertion is not given.

May be this can be provided with adding a native function for serializing the set into bytes that ensures order of elements?

[movekevin]

I don't think we can have this part of our framework and call it a "set" because it doesn't has a very simple property important for sets: equality. Equality of two sets with different order of insertion is not given.

May be this can be provided with adding a native function for serializing the set into bytes that ensures order of elements?

[lightmark]

I'm fine with this, but I wonder why we didn't just make a dummy value and use SimpleMap.

SimpleMap<Key, DummyValue> where struct DummyValue has store { }

I plan to reuse simple map with SimpleMap<Key, ()> once we loose all the V: store constraints.

[lightmark]

extensionality

I don't think we can have this part of our framework and call it a "set" because it doesn't has a very simple property important for sets: equality. Equality of two sets with different order of insertion is not given.

Being able to compare sets for equality independent of insertion order is a very common use case for sets (I used it often in my daily programming). This cannot go like this into the framework.

I took a look at cpp unordered_set and set. The time complexity of their == operator is n^2 and n, respectively. So it can be implemented, just with high cost in MOVE. Simple_set is by nature unordered and the in-memory version that we discussed in slack can be ordered and serialized as a sequence of tuples so that equality can be implemented by comparing their byte format.

btw, in programming world, I think equality just means extensionality... So why would we bother to over-complicate the concept by giving such a name...

[davidiw]

do you want to rename this unordered_set?

[lightmark]

do you want to rename this unordered_set?

Why? Do you rename simple_map to unordered_map?

btw, do we have any plan to implement native implementation for simple_map that it reads a blob from storage and instantiate an in-memory hashmap/btreemap and serialize it into a deterministic binary format into write_set? I believe this may benefit a lot implementation including smart_table.

[wrwg]

do you want to rename this unordered_set?

Why? Do you rename simple_map to unordered_map?

btw, do we have any plan to implement native implementation for simple_map that it reads a blob from storage and instantiate an in-memory hashmap/btreemap and serialize it into a deterministic binary format into write_set? I believe this may benefit a lot implementation including smart_table.

We need to discuss perhaps in person. I definitely are of the opinion a set type without correct equality cannot be part of the framework. The current simple_map is already bad enough. General and fast comparison is coming to Move. Then this can be done right.

[lightmark]

cc @movekevin .Please take a look at @wrwg 's comment. Then let's hold off putting this inside framework and you can use simple_map for now for multi-sig acct.