Add a new common base type, as replacement for IsCollection ?

[fingolfin]

We may wish to introduce a new common base filter for our data structures, e.g. IsDataStructure, although that is somewhat bland and generic.

The point of that would be that it could declare a few common operations and attributes, like IsEmpty and Size, so that we don't need to use InstallOtherMethod, but can use InstallMethod. Also, there could be a default method for IsEmpty which invokes Size. Also, default methods for ViewObj, PrintObj, ViewString etc. -- for this, we just need a way to map representation filters to strings, e.g. IsHashMapRep to "hash map".

[stevelinton]

I guess the question is why IsCollection and IsMapping don't do what we need?
Families? or some other problem?

It would be nice if the new filters had some relationship to these (we might also want something comparable but with multiset semantics) either as subfilters (specifying objects that satisfied some additional conventions introduced for the datastructures package) or as superfilters (so that it is possible to talk about the new structures and the existing ones in a uniform way for some simple objects.

In any case I think you have to distinguish set, multiset and mapping semantics from the very beginning.

[stevelinton]

One thing these would be nice for is to provide a hook for offering Iterators and Cursors in a uniform way. Iterators for sets and multi-sets we already have via Iterator and IteratorSorted we might also want IteratorInOrderOfInsertion. For map-type objects we probably want IteratorOfKeys and IteratorsOfKeysSorted ... Maybe values as well, but that opens up a couple of cans of worms about repetition and ordering.

Cursors we don't have, but see for instance the Java library design. A cursor is a uniform interface to mutable ordered datastructures allowing for efficiently searching, interrupting and resuming the search, inserting or deleting the "current" object without having to redo the search, etc.

[fingolfin]

@stevelinton the problem with IsCollection is that its documentation / definition says this: "A collection in GAP consists of elements in the same family". But that's just not something we enforce or want to enforce.

Likewise, IsList is wrong, and hence IMHO IsListOrCollection.

For a hashmap, one could of course also view it as an IsMapping, and install a method for Image -- that would be an alternative interface to it, I guess. But it doesn't help (as far as I can tell?) with heaps and queues and ...?

[ChrisJefferson]

I think we should consider IsListOrCollection. As I understand it, it isn't really about something being exactly a list or a collection, but to get around the problem that non-homogenous lists aren't collections.

Therefore, do we just want a (horribly named) IsNonhomogenousCollection, which would effectively be a collection without family, and we would in practice use that instead of IsListOrCollection.

[fingolfin]

So perhaps we add a new filter, say IsContainer, and then IsCollection and IsList would specialize that, but so would our types?

Also, iterators definitely are something I want (see also e.g. #30 which mentions iterators on hashmaps)

[fingolfin]

@ChrisJefferson I guess we are thinking in a similar direction, if one equates IsNonhomogenousCollection and IsContainer ?

[fingolfin]

(BTW drawback of the IsNonhomogenousCollection is the same as with "non-associative algebras" which usually denote algebras which may be non-associative, while the name suggest they must be non-associative). Of course IsContainer isn't particular great... if we could start from scratch, I'd call it IsCollection, and then call what is now IsCollection rather IsHomogeneousCollection, or IsStrictCollection or so... ah well, too late for that :)

[stevelinton]

I do think we need at least two base classes -- one for things with keys and values and one for things with just data. Within the data case you have to split pretty quickly into set and multiset semantics. We can then subsume IsListOrCollection into one of those.

The question is what operations do we promise (and what if anything do we say about their performance and semantics).

[stevelinton]

I've added a page on the wiki with some preliminary thoughts.