Create a new module for morphic words

[jlepsova]

The goal of this ticket is to create a new module for morphic words.

As a consequence, it will improve the following computations which take a lot of time:

sage: m = WordMorphism('a->ab,b->a')
sage: w = m.fixed_point('a')
sage: w
word: abaababaabaababaababaabaababaabaababaaba...
sage: %time w[1000]
CPU times: user 1.45 ms, sys: 0 ns, total: 1.45 ms
Wall time: 1.45 ms
'a'
sage: %time w[10000]
CPU times: user 82.9 ms, sys: 0 ns, total: 82.9 ms
Wall time: 82.1 ms
'a'
sage: %time w[100000]
CPU times: user 5.19 s, sys: 6.26 ms, total: 5.2 s
Wall time: 5.19 s
'b'
sage: %time w[1000000]
CPU times: user 12min 45s, sys: 93.4 ms, total: 12min 45s
Wall time: 12min 45s
'a'

[chapoton]

duplicate of #31370 ?

[slabbe]

Replying to chapoton:

duplicate of #31370 ?

Let's close #31370 and keep this one (Jana is learning how to contribute to Sage).

[slabbe]

I rebased the branch on top of 9.3.beta7. I also added a commit which links the new module added by Jana to the existing sage words library.

---

New commits:

​77c4645	adding more efficient way of stating a letter at an n-th position of a fixed point
​86990a0	linking morphic.py file to the sage words library

[slabbe]

Jana, the next step is to update the examples in the documentation in the morphic.py file.

With the current branch,

$ sage -bt src/sage/combinat/words/morphic.py 

returns

[...]

**********************************************************************
File "src/sage/combinat/words/morphic.py", line 157, in sage.combinat.words.morphic.WordDatatype_morphic.__iter__
Failed example:
    print('update the examples here')
Expected nothing
Got:
    update the examples here
**********************************************************************

[...]

**********************************************************************
3 items had failures:
   1 of   2 in sage.combinat.words.morphic
   1 of   2 in sage.combinat.words.morphic.WordDatatype_morphic.__getitem__
   6 of  13 in sage.combinat.words.morphic.WordDatatype_morphic.__iter__
    [30 tests, 8 failures, 0.02 s]
----------------------------------------------------------------------
sage -t --warn-long 72.7 --random-seed=0 src/sage/combinat/words/morphic.py  # 8 doctests failed
----------------------------------------------------------------------

[jlepsova]

I fixed the doctests in morphic.py.

---

New commits:

​6587375	adding more efficient way of stating a letter at an n-th position of a fixed point
​20ae22e	linking morphic.py file to the sage words library
​a1f4143	31378: incomplete changes
​d4e7081	fixed doctests in morphic.py

[git]

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

​b8690fc

fixing some of the errors in word.py

[mkoeppe]

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.

[slabbe]

New commits:

​76fcfd6	Merge branch 'u/jlepsova/morphic' into 9.3.rc0
​9573c34	31378: fixing doctests in word.py

[slabbe]

I fixed the doctests with respect to saving the objects (loads, dumps, reduce, etc.).

It remains only one issue:

            sage: m = WordMorphism("a->ab,b->")          
            sage: w = m.fixed_point("a")                                      
            sage: w.representation(0)                
            []                                      
            sage: w.representation(1)             
            [1]                         
            sage: w.representation(2)  #infinite loop

Jana: can you take a look at this?

[jlepsova]

New commits:

​cc41397	Merge branch 'u/slabbe/31378' into 9.3.rc3
​ec5d4a7	trying to repair the finite fixed point problem, something changed in word_infinite_datatypes.py, however

[slabbe]

Does the most recent commit also handles the following infinite loop?

sage: m = WordMorphism("a->ab,b->,c->cdab,d->dcab")
sage: w = m.fixed_point("a")
sage: w.representation(2)

What is the remaining problem you mention in the commit message? Can you provide an example?

In the following, the multiplication vMk*M is computed twice. Maybe you want to write vMk1 = vMk*M to represent vM^{k+1} and at the end of the loop, you may do vMk = vMk1.

         while vMk[position] <= n:
+            if vMk == vMk*M:
+                raise ValueError('The morphism has a finite fixed point of length {}.'.format(vMk[position]))
             vMk = vMk*M
             length_of_images.append(vMk)

I would suggest that the error message also include the value of n. Something like IndexError: index (=2) out of range, the fixed point is finite and has length 2.

I think the error should be an IndexError instead of ValueError, as it is for strings:

sage: s = 'ab'                                                                  
sage: s[2]                                                                      
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-2-2d1d9bdb9b26> in <module>
----> 1 s[Integer(2)]

IndexError: string index out of range

[git]

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

​51d4db0

31378: fix comment 13

[jlepsova]

I solved comment 13 with regard to morphic.py but the issue with infinite_datatype remains.

[slabbe]

I fixed the remaining issue. Should be okay now.

I added a reference. I need to learn the new way of adding reference to sage...

---

New commits:

​77a7759	adding more efficient way of stating a letter at an n-th position of a fixed point
​1916606	linking morphic.py file to the sage words library
​2ad57b7	31378: incomplete changes
​bd43972	fixed doctests in morphic.py
​81d0ed8	fixing some of the errors in word.py
​c6dc152	31378: fixing doctests in word.py
​3602aa6	trying to repair the finite fixed point problem, something changed in word_infinite_datatypes.py, however
​97515fd	31378: fix comment 13
​33eb4c1	31378: fixed remaining issue, added doctests

[git]

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

​f1b12db

31378: adding reference in the good place

[slabbe]

Fixed the reference.

Needs review!