#17693: mutable poset: a data structure for asymptotic expressions
-------------------------------------+-------------------------------------
Reporter: dkrenn | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.9
Component: asymptotic | Resolution:
expansions | Merged in:
Keywords: asymptotics | Reviewers: Benjamin Hackl,
Authors: Daniel Krenn | Clemens Heuberger
Report Upstream: N/A | Work issues:
Branch: u/dkrenn/asy | Commit:
/mutable-poset | 3c69f6be24c5776593d3e067d8c723cd5c192e8e
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by dkrenn):
Replying to [comment:36 cheuberg]:
> I read the documentation and the code. I pushed a few reviewer commits.
Cross-reviewed. One commit added.
> I have a number of rather minor issues with the documentation which I
ask you to fix in order facilitate future maintainance of the code. In
three instances, I propose alternative implementations, which might be
more readable or slightly more efficient.
Thanks; see my comments below.
> 1. Please add `.. seealso::` blocks between corresponding methods of
shell and poset as well as between the accessor methods (keys, elements,
shells)
Done.
> 2. there is an empty "Introduction" section at the beginning of the
module documentation, the next heading "Example" is on the same level.
Deleted.
> 3. this module was written as part of the asymptotic expansion effort.
In contrast to the asymptotic expansion, it does not have the
"experimental" decorator. I'd feel more comfortable having it, at least
until a larger portion of the asymptotic expansions have been merged.
Activated it; it seems (for some (to me) unknown reason) the warning
appears now in every doctest and not only once in the file. Thus,
deactivated it again; and I am for keeping it this way.
> 4. `MutablePoset.__init__` accepts a list of elements. This could be
used in several doctests (in particular, in the set operations) as an
abbreviation.
Good idea. Done.
> 5. `MutablePosetShell.__init__`: shall we check that `element is not
None`? Otherwise, handling of special elements would probably be affected.
MutablePosetShell is typically used by the MutablePoset; and there, adding
a `None`-element is forbidden (see :meth:`add`).
> 6. `MutablePosetShell.key`: I do not understand the sentence "The
element is converted by the poset to the key".
Rewritten.
> 7. `MutablePosetShell.key`: I am surprised that the key is not cached. I
imagine that many comparisons will be needed in the lifetime of a
`MutablePoset`, and in every case, the property key has to be resolved,
which calls the property poset, which calls `get_key` of the poset.
Now it is cached (see also follow up ticket #19281).
> 8. `MutablePosetShell.__repr__`: The note box in the docstring is
surprising at this point: reading the source file from the top, this is
the first point where the representation of the data is explained, after
guessing it from `is_special`, `is_oo`, `is_null` above. I think that it
would be better to document these conventions closer to the top, perhaps
in the `__init__` method or perhaps only as a comment in the source code.
Added a note in the class description.
> 9. `MutablePosetShell.__repr__`: The code replicates the behaviour of
`is_null` and `is_oo`. As the `__repr__` method is hardly time critical,
I'd prefer using `is_null` and `is_oo`, here and thus hiding the internal
convention.
Rewritten.
> 10. `MutablePosetShell.le`: the note box could be simplified by
suppressing implementation details and speaking about the special
elements.
Done.
> 11. `MutablePosetShell.le`: `right <= left`: neither `right` nor `left`
are defined here.
Rewritten.
> 12. `MutablePosetShell.le`: the part `if other.element is None` could be
simplified to `return not other.successors()` as `self` is already known
not to be special here.
True; rewritten.
> 13. `MutablePosetShell.le`: If this is time critical,
`self._predecessors_` could be used instead of `self.predecessors()`.
Changed.
> 14. `MutablePosetShell.eq`: note box, see above.
Simplified.
> 15. `MutablePosetShell.eq`: emphasize that elements with equal keys are
considered equal? Currently, this information is somewhat hidden in the
note box which at first glance only seems to explain handling of special
elements.
Rewritten note box.
> 16. `MutablePosetShell._copy_all_linked_`: Short description: "Return a
copy of all shells" does not correspond to the actual return value, which
is only the copy of this shell.
Rewritten.
> 17. `MutablePosetShell._copy_all_linked_`: the interplay between this
method and `MutablePoset._copy_shells_` is not well documented: in
particular, `poset` in `_copy_all_linked_` is ''only'' used for setting
the containing poset, but not for actual inserting into this poset.
Extended description of parameter `poset`.
> 18. `MutablePosetShell._copy_all_linked_`: I do not understand why you
test `oo == P.oo`: I think that `oo` is an element of the new poset `Q`.
`oo == P.oo` tests that `Q.oo` is mapped to ``P.oo``.
> So `oo is Q.oo` would be more interesting?
`oo is Q.oo` is `False` since `oo` is not in `Q`, but just a copy of the
`oo` in `P` with parent-poset `Q`. Inserting this into `Q` is done in
`_copy_shells_`.
> The current test demonstrates that the poset is not used in comparison,
so that would rather belong to `.eq`?
I do not understand what you mean (but it is already late...).
> 19. `MutablePosetShell._search_covers_`: what is the role of `self` in
this method? It trivially influences the return value, but what else?
`_search_covers_` does not exist anymore (see 27).
> 20. `MutablePosetShell._search_covers_`: The explanation of the return
value is unclear to me. Is the sentence "Note that..." meant to be a
complete description? Does it change if `reverse` is set?
`_search_covers_` does not exist anymore (see 27).
> 21. `MutablePosetShell._search_covers_`: I think that the notions of
"upper cover" and "lower cover" need a brief definition; I did not find
them in Wikipedia and
`sage.combinat.posets.posets.FinitePoset.upper_covers` defines the notion.
`_search_covers_` does not exist anymore (see 27). Incooperated in
`covers`.
> 22. `MutablePosetShell._search_covers_`: According to Wikipedia, a cover
is what is called an upper cover here. This is in contrast to the default
behaviour here.
`_search_covers_` does not exist anymore (see 27).
> 23. `MutablePosetShell._search_covers_`: what is the difference between
this method and `.predecessors`? Is the shell necessarily an element of
the poset? If not, then there should be a doctest covering this case.
`_search_covers_` does not exist anymore (see 27). Incooperated in
`covers`.
> 24. `MutablePosetShell.covers`: "originate" is somewhat foreign to the
description of the poset.
Rewritten.
> 25. `MutablePosetShell.covers`: "which are at most the given shell":
should that be "which are less than the given shell"?
Rewritten.
> 26. `MutablePosetShell.covers` see comments on
`MutablePosetShell._search_covers_`.
Rewritten.
> 27. `MutablePosetShell.covers`: I think that the following would be an
equivalent implementation of this method, which does not need a helper
function with side effects.
> {{{
> if self == shell:
> return set()
> covers = set().union(*(e.covers(shell, reverse)
> for e in self.successors(reverse)
> if e.le(shell, reverse)))
> if covers:
> return covers
> else:
> return set([self])
> }}}
> (pushed as branch `u/cheuberg/asy/mutable-poset-cover`)
Merged and minor simplification.
> 28. `MutablePosetShell._iter_depth_first_visit_`: document the role of
self in this method (only shells `>=` this shell are visited).
Documented.
> 29. `MutablePosetShell.iter_depth_first`: document the role of self in
this method (only shells `>=` this shell are visited).
Documented.
> 30. `MutablePosetShell._iter_topological_visit_`: document the role of
self in this method (only shells `<=` this shell are visited, emphasize
the contrast to depth first.).
Documented.
> 31. `MutablePosetShell.iter_topological_first`: document the role of
self in this method (only shells `<=` this shell are visited, emphasize
the contrast to depth first.).
Documented.
> 32. `MutablePosetShell.iter_topological_sort`, last example: function
`C` is defined, but not used.
Deleted.
> 33. `MutablePosetShell.merge`: explain what merge is, in particular,
that this is defined when constructing the poset.
Documented.
> 34. `MutablePosetShell.merge`: I am surprised that `check=True` leads to
a silent failure instead of an exception and that `poset._merge_ is None`
does not raise an exception. Document and test this behaviour?
Behavior changed.
> 35. `MutablePosetShell.merge`: what is the difference between
`poset.remove` and `poset.discard`?
See Python's set.
> 36. `MutablePosetShell.merge`: document that the merge function
resulting in `None` leads to deletion of the element.
Done.
> 37. `MutablePosetShell.merge`: document that the merge function must not
change the position of the element in the poset.
Mentioned this more explicitly in docs
> 38. `MutablePoset.__init__`: Clarify the role of `key`: in particular,
`key` does not only influence sorting, but that no two elements are
allowed to have the same key.
Done.
> 39. `MutablePoset.__len__`: Clarify that `null` and `oo` are not
counted.
Done.
> 40. `MutablePoset.shells_topological`: The sentence "If this is None, no
sorting according to the representation string occurs." is unclear to me,
in particular the role of the representation string.
Rewritten.
> 41. `MutablePoset.keys_topological`: Due to the chosen key, some of the
elements added to the poset are ignored. I do not know why this is
demonstrated here.
Removed.
> 42. `MutablePoset.repr`: INPUT section is incomplete.
Completed.
> 43. `MutablePoset.repr_full`: INPUT section is incomplete.
Completed.
> 44. `MutablePoset.add`: the loop `for reverse in (False, True)`
simplifies in the second iteration: as all pairs of elements `(s, l)` with
`new` covering `s` and `l` covering `new` have already been broken up
while `reverse=False`. Thus it might be more straightforward to do it only
once, not using `reverse` at all and saving a few intersections:
> {{{
> new._predecessors_ = self.null.covers(new, reverse=False)
> new._successors_ = self.oo.covers(new, reverse=True)
>
> for s in new.predecessors():
> for l in s.successors().intersection(new.successors()):
> l.predecessors().remove(s)
> s.successors().remove(l)
> s.successors().add(new)
> for l in new.successors():
> l.predecessors().add(new)
> }}}
> (pushed as branch `u/cheuberg/asy/mutable-poset-add`)
Merged and cross-reviewed....ok.
> 45. `MutablePoset.remove`: the loop over all (not necessarily direct)
successors via the depth first search iterator seems to be rather
inefficient, especially if the poset is large. I propose an alternative
based on the order relation and not based on the data structure:
> {{{
> for upper in shell.successors():
> upper.predecessors().remove(shell)
>
> for lower in shell.predecessors():
> lower.successors().remove(shell)
> for upper in shell.successors():
> if not any(s <= upper
> for s in lower.successors()):
> lower.successors().add(upper)
> upper.predecessors().add(lower)
> }}}
> (pushed as branch `u/cheuberg/asy/mutable-poset-remove`)
This needs comparisons of the elements, but one of the main ideas of this
data structure is that comparisions are only needed for inserting an
element into the poset and none needed once it is inside. Thus I am for
keeping the current solution. However, I am fine with introducing (now or
at any point later) an algorithm option which makes it possible to select
different removing algorithms depending on the situation.
> 46. `MutablePoset.remove`, `MutablePoset.discard`: add "see also
blocks", but also an explanation of the difference between `discard` and
`remove`. I guess that both methods are available due to some
compatibility concern (in that case, please add a remark in the code or
the docstring). Otherwise, I'd suggest removing `discard`, removing the
parameter `raise_key_error` and let the user catch the exception.
Python's set has both, `remove` and `discard`. Thus this mutable poset
should have it as well.
Note-block added. Seealso added.
> 47. `MutablePoset.pop`: remove `key=lambda c: -c` from this example as
it is not pertinent to `pop`.
Done.
> 48. `MutablePoset.pop`: mention that special elements cannot be popped.
Done.
> 49. `MutablePoset.pop`: IMHO you can remove the first four line (the
`try:` block deleting `kwargs['include_special']`) because setting
`kwargs['include_special'] = False` should result in the same result.
Deleted.
> 50. `MutablePoset.union`: The doctest `P.union(P, Q, Q, P)` neither fits
the description "a poset" or "an iterable of future elements".
Rewritten INPUT-block
> 51. `MutablePoset.union`: the word "union" sounds symmetric, however,
due to keys and merge functions, it might not be commutative. The note box
is not helpful for me.
Note added/changed.
> 52. `MutablePoset.union`: the TODO box from `union_update` also applies
here.
Copied.
> 53. `MutablePoset.union_update`: why is the semantics of `other`
different w.r.t `union`, but has the same description? It would seem more
logical to me if `union` would simply call copy and then pass its argument
to `update_union` and let the latter function sort out the iterators?
Indeed. Code rewritten.
> 54. `MutablePoset.difference` and `MutablePoset.difference_update`: see
comments on `union` and `union_update`
Done.
> 55. `MutablePoset.intersection` and `MutablePoset.intersection_update`:
see comments on `union` and `union_update`
Done.
> 56. `MutablePoset.intersection_update`: how can the `AttributeError`
occur? After all, `self` is a `MutablePoset`, so the method `keys` will be
available unless something very strange happens ...
True. Code simplified.
> 57. `MutablePoset.merge`: documentation of `reverse`: what is the
default direction?
Documented.
> 58. `MutablePoset.merge`: add doctest for `RuntimeError`.
Added.
> 59. `MutablePoset.merge`: document that `can_merge` is applied in the
sense of the condition of depth first iteration, i.e., once `can_merge`
fails, the successors are no longer tested. This is some kind of
monotonicity condition on `can_merge`.
Added note.
> 60. `MutablePoset.merge`: it should be mentioned somewhere that this (at
first sight strange) merge magic is motivated by asymptotic expansions.
Mentioned.
> 61. `MutablePoset.map`: IMHO the example does alter the keys, because
the key was the identity map here.
Example changed.
> 62. `MutablePoset.mapping`: does the map have to be key preserving as in
the method `map`? Is this method actually needed, see also the recent
discussion on inplace vs. non-inplace operations on sage-devel?
Added a note on key-order preservation.
I think having `MutablePoset.mapping` is useful (from a ui point of view)
since one would not naturally thinks that the `copy` method has a
parameter for applying a mapping function.
--
Ticket URL: <http://trac.sagemath.org/ticket/17693#comment:39>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
