Re: Reverting changes on backtracking
Posted: 14 Nov 2022 13:54
Also, a few notes on your library: In many ways an interesting data structure. But ... ![Smile :-)](./images/smilies/icon_smile.gif)
It seems to me that the "more" abstract data type you are "actually" implementing is something like this:
Some of this could naturally be inherited from setM. But notice that none of this looks map-like; there is no Key-involvement.
However, the actual implementation of this data type involves using "small" positive numbers as array indices. And in order to make the abstract version of this data type we need an efficient collision free mapping from our @Data to "small" positive numbers. (Unlike hash functions which allows collisions (though fewer collisions is better)).
The interface (mapM_chain) you provide with a @Key (called @Site in your code) seems like a relatively "uninteresting" implementation detail. And as implementation detail it is over-generalized because: @Key will always be positive.
The problem in using this data structure lies in providing the mapping from @Data to positive.
Your objIdentNumber provides one such mapping, they must however be built into the data, which limits the generality. Furthermore, the "positive" numbers can be as large as the number of objects that was alive simultaneously at some point in time.
It is a known problem (at least to me) that when generalizing a data structure, you may need a mapping from the actual interesting data to some low-level internal "thing". And the resulting data structure will not be more efficient than that mapping.
![Smile :-)](./images/smilies/icon_smile.gif)
It seems to me that the "more" abstract data type you are "actually" implementing is something like this:
Code: Select all
interface chain{@Data}
predicates
insertBefore : (@Data Reference, @Data Data).
% plus other variations insertAfter, insertFirst, insertLast ...
predicates
contains : (@Data Value) determ.
predicates
tryGetNext (@Data Reference) -> @Data Value determ.
% plus other such things tryGetPrevious, isEmpty, ....
predicates
getAll_nd : () -> @Data Value nondeterm.
...
end interface chain
However, the actual implementation of this data type involves using "small" positive numbers as array indices. And in order to make the abstract version of this data type we need an efficient collision free mapping from our @Data to "small" positive numbers. (Unlike hash functions which allows collisions (though fewer collisions is better)).
The interface (mapM_chain) you provide with a @Key (called @Site in your code) seems like a relatively "uninteresting" implementation detail. And as implementation detail it is over-generalized because: @Key will always be positive.
The problem in using this data structure lies in providing the mapping from @Data to positive.
Your objIdentNumber provides one such mapping, they must however be built into the data, which limits the generality. Furthermore, the "positive" numbers can be as large as the number of objects that was alive simultaneously at some point in time.
It is a known problem (at least to me) that when generalizing a data structure, you may need a mapping from the actual interesting data to some low-level internal "thing". And the resulting data structure will not be more efficient than that mapping.