Opened 5 months ago

Closed 3 months ago

#16291 closed defect (fixed)

Fixing associativity of FormalCompositeMap

Reported by: sbesnier Owned by: sbesnier
Priority: major Milestone: sage-6.3
Component: categories Keywords: associativity FormalCompositeMap
Cc: defeo Merged in:
Authors: Sébastien Besnier Reviewers: Peter Bruin
Report Upstream: N/A Work issues:
Branch: f099e83 (Commits) Commit: f099e83eee9d96d4a4e0e3b4293b24450afba292
Dependencies: Stopgaps:

Description

This ticket follows discussions in #16245, comments 4 and 5. This discussion raised a break of associativity in FormalCompositeMap?.

Currently, the FormalCompositeMap only stores "first" and "second" map. Hence (f*g)*h builds a tree like:

|\
| \
|\ h 
f g

whereas f*(g*h) builds a tree like:

|\
f \
  |\
  g h

As a result, map composition is not associative:

sage: from sage.categories.map import Map
sage: f=Map(ZZ,ZZ)
sage: (f*f)*f==f*(f*f)
False

I think this class should contain a list of several Map. I've made a draft of it, the only doctest I had to change was those involving FormalCompositeMap string representation. Indeed, this representation was treelike and is now linear.

Change History (16)

comment:1 Changed 5 months ago by sbesnier

  • Branch set to u/sbesnier/ticket/16291
  • Commit set to 757c611bd82b40c8d8581e3e3e7547157b1e0f0d
  • Status changed from new to needs_review

I've commented the "first" and "second" methods since it is not used in another place in sage. Should I keep them for backward compatibility?


New commits:

757c611Fix associativity failing in FormalCompositeMap
Last edited 5 months ago by sbesnier (previous) (diff)

comment:2 Changed 5 months ago by git

  • Commit changed from 757c611bd82b40c8d8581e3e3e7547157b1e0f0d to b9355939dca87f7c362abfdc0998566417b7d5be

Branch pushed to git repo; I updated commit sha1. New commits:

b935593Correct the previous commit

comment:3 Changed 5 months ago by git

  • Commit changed from b9355939dca87f7c362abfdc0998566417b7d5be to 4e90074d27dcb6a6f0f67a8f67c387b75aa6a0cc

Branch pushed to git repo; I updated commit sha1. New commits:

4e90074Replace :meth:`list` by :meth:`__getitem__` in FormalCompositeMap

comment:4 Changed 5 months ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:5 Changed 4 months ago by sbesnier

  • Summary changed from FormalCompositeMap should contain list of Map to Fixing associativity of FormalCompositeMap

comment:6 Changed 4 months ago by pbruin

Is this still meant as a draft as stated in the ticket description? I think it looks good in general, but maybe you could improve the formatting of the code and try to conform to the Python style guide and docstring conventions.

In particular:

  • use consistent spacing (including spaces after punctuation marks and no spaces before them)
  • do not put if foo: bar on a single line unless foo and bar are very short
  • docstrings should start with a single line, or two if really necessary; four, as in __getitem__(), is definitely too many

Also, I recommend keeping the first() and second() methods, since they are public and existing user code may depend on them.

comment:7 Changed 4 months ago by git

  • Commit changed from 4e90074d27dcb6a6f0f67a8f67c387b75aa6a0cc to 198085bda26743ebcb442f3b70698c3055395cd1

Branch pushed to git repo; I updated commit sha1. New commits:

198085bDepreciate first and second methods.

comment:8 follow-up: Changed 4 months ago by pbruin

Sorry for being annoying, but I'm afraid you partially misunderstood my request about punctuation... By punctuation marks I meant one of . , ; : ? !, not equality signs or operators. (See the section "Whitespace in Expressions and Statements" on the first linked page in comment:6.)

What is the reasoning behind head() and tail()? If you think of morphisms as arrows, then composing two morphisms, say by putting f first and g second, gives

   f      g
* ---> * ---> *

In this picture it would be visually suggestive to call g the head and f the tail! Why not keep first() as it is, implementing a method last() and making second() a deprecated alias for either last() or __getitem__(1)?

comment:9 in reply to: ↑ 8 ; follow-up: Changed 4 months ago by defeo

What is the reasoning behind head() and tail()?

That was my suggestion. I find first and second misleading, and think they should be deprecated. head and tail are standard names in functional languages, e.g. caml. Of course, this is standard terminology for lists, where there is little ambiguity on who's the head and who's the tail. As you point out, it is more confusing if you draw arrows, but first and last is no less confusing than first and second in my opinion.

We could keep head and tail, but reverse them to be consistent with arrow diagrams (who says head should be first in applicative order? We are making up the terminology, anyway). Or maybe head and shaft, this is even more figurative! Or, if we want to stick with the applicative order, what about first and then? Whatever we choose, I think we should take names that sound ridiculous enough to force the user to read the docstring, rather than say "I know what that means".

comment:10 in reply to: ↑ 9 Changed 4 months ago by pbruin

Replying to defeo:

What is the reasoning behind head() and tail()?

That was my suggestion. I find first and second misleading, and think they should be deprecated. head and tail are standard names in functional languages, e.g. caml. Of course, this is standard terminology for lists, where there is little ambiguity on who's the head and who's the tail.

Actually, the moment when I read head and tail, I was reminded of car and cdr, so that had the desired effect. 8-)

As you point out, it is more confusing if you draw arrows, but first and last is no less confusing than first and second in my opinion.

Forget what I said about introducing last, I was confused. (Well, we could introduce it anyway, but just as "the last morphism in the composition", not with the current meaning of tail.)

We could keep head and tail, but reverse them to be consistent with arrow diagrams (who says head should be first in applicative order? We are making up the terminology, anyway). Or maybe head and shaft, this is even more figurative!

I think it sounds nice, but shaft might be a bit annoying for people who don't think of morphisms as arrows. And I would expect head to be the last morphism in the composition, not the composition of all except the first.

Or, if we want to stick with the applicative order, what about first and then?

I like this idea, because it is close to the existing terminology and because then is nicely consistent with the way composed morphisms are printed.

Whatever we choose, I think we should take names that sound ridiculous enough to force the user to read the docstring, rather than say "I know what that means".

I don't know, at the same time they should preferably also be of the kind that you remember once you have seen them. And they shouldn't be so ridiculous that they become distracting.

I'm starting to think that altogether first and then suggests itself as the preferred choice.

comment:11 Changed 4 months ago by git

  • Commit changed from 198085bda26743ebcb442f3b70698c3055395cd1 to cbbe0b36056b9eac2f18bad0d7ed582603f7cc06

Branch pushed to git repo; I updated commit sha1. New commits:

cbbe0b3Change `FormalMapComposition.tail` (former `.second`) to `.then`.

comment:12 Changed 3 months ago by pbruin

In the last commit, didn't you want to change head back to first? Now the terminology is asymmetric (head vs. then).

comment:13 Changed 3 months ago by git

  • Commit changed from cbbe0b36056b9eac2f18bad0d7ed582603f7cc06 to 7bcc80d4272fbe8b822524d9362145dda9f2e5da

Branch pushed to git repo; I updated commit sha1. New commits:

7bcc80dModify the name `FormalCompositeMap.head()` to `.first()`.

comment:14 Changed 3 months ago by sbesnier

Ooops!! I'm sorry! Thank you Peter.

comment:15 Changed 3 months ago by pbruin

  • Branch changed from u/sbesnier/ticket/16291 to u/pbruin/16291-formal_composite_map
  • Commit changed from 7bcc80d4272fbe8b822524d9362145dda9f2e5da to f099e83eee9d96d4a4e0e3b4293b24450afba292
  • Reviewers set to Peter Bruin
  • Status changed from needs_review to positive_review

Reviewer patch mostly fixes formatting and whitespace issues. (Also in other parts of map.pyx, now that we're at it.)

comment:16 Changed 3 months ago by vbraun

  • Branch changed from u/pbruin/16291-formal_composite_map to f099e83eee9d96d4a4e0e3b4293b24450afba292
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.