Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Remove immutable variants of datastructure (types)? #29

Open
markuspf opened this issue Aug 3, 2017 · 5 comments
Open

Remove immutable variants of datastructure (types)? #29

markuspf opened this issue Aug 3, 2017 · 5 comments

Comments

@markuspf
Copy link
Member

markuspf commented Aug 3, 2017

No description provided.

@fingolfin
Copy link
Member

What exactly is this about? Is it still relevant?

@markuspf
Copy link
Member Author

BindGlobal( "PairingHeapTypeMutable", NewType(HeapFamily,

@fingolfin
Copy link
Member

Well, we can do that, but then we should also prevent our objects from being made immutable. (Can one do that? @stevelinton ?) Right now, one can do that, with all the bad consequences...:

gap> heap:=BinaryHeap();
<binary heap with 0 entries>
gap> MakeImmutable(heap);;
gap> IsEmpty(heap);
true
gap> Push(heap,1);
gap> IsEmpty(heap);
true

So an immediate thing to do here is to require IsMutable in the Push and Pop declarations resp. methods. But ideally, it just should be impossible to do MakeImmutable

@fingolfin
Copy link
Member

Looking at the code for MakeImmutable, it calls MakeImmutablePosObj, which just does this:

  CALL_2ARGS( RESET_FILTER_OBJ, obj, IsMutableObjFilt );
  CALL_1ARGS( PostMakeImmutableOp, obj);

So we can install a method which gets triggered after the fact... but no way to prevent the operation from happening :-(.

@stevelinton
Copy link
Contributor

We had this debate many years ago over Iterators. The conclusion is that Immutable structures, while not necessarily very useful, are harmless and forbidding them creates problems elsewhere. So in this case Push and Pop would be declared requiring IsMutable. You could still, for example ask for the Size of Max of such a heap. For something like a binary search tree there is still quite a lot you can do with an immutable tree (and one could use PostMakeImmutable to balance it or turn it into an immutable sorted list or whatever).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants