Improving word construction

[seblabbe]

Improve the creation of a word from a word when the parent changes :

BEFORE:

sage: w = Word('abab')
sage: P = WordPaths('abcd')
sage: P(w)
word: abab
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_str'>
sage: type(P(w))
<class 'sage.combinat.words.word.FiniteWord_str'>

AFTER:

sage: w = Word('abab')
sage: P = WordPaths('abcd')
sage: P(w)
Path: abab
sage: type(w)
<class 'sage.combinat.words.word.FiniteWord_str'>
sage: type(P(w))
<class 'sage.combinat.words.paths.FiniteWordPath_square_grid_str'>

The following construction gets also faster with the patch applied :

BEFORE:

sage: w = Word([0,1]*10000)
sage: %timeit z = Words([2,0,1])(w)
1000 loops, best of 3: 586 µs per loop

AFTER:

sage: w = Word([0,1]*10000)
sage: %timeit z = Words([2,0,1])(w)
1000 loops, best of 3: 343 µs per loop

CC: @saliola

Component: combinatorics

Author: Sébastien Labbé

Reviewer: Franco Saliola

Merged: sage-4.3.4.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/7520

[seblabbe]

comment:1

Will post a patch soon...

[seblabbe]

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-The `_check` function of the Combinatorial class of all words (checking that the 40 first letters of the word are in the parent) is called for each word created by the user ....and by any other function. It would be good to add a check parameter (True or False) whether to do the checking. For example, for internal function, it could be turned off. Here is a example of what can be gained from this modification when generating all words of a given length :
+(1) The `_check` function of the Combinatorial class of all words (checking that the 40 first letters of the word are in the parent) is called for each word created by the user ....and by any other function. It would be good to add a check parameter (True or False) whether to do the checking. For example, for internal function, it could be turned off. Here is a example of what can be gained from this modification when generating all words of a given length :
 
 BEFORE:
 
@@ -19,7 +19,7 @@
 ```
 
 
-Creation of a word from a word when the parent changes doesn't work well :
+(2) Creation of a word from a word when the parent changes doesn't work well :
 
 ```
 sage: w = Word('abab')
@@ -32,12 +32,3 @@
 <class 'sage.combinat.words.word.FiniteWord_str'>
 ```
 
-Creation of a word represented by list from a word represented as str doesn't work well and could work easily:
-
-```
-sage: w = Word('aababababab')
-sage: Word(w, datatype='list')
-word: aababababab
-sage: type(_)
-<class 'sage.combinat.words.word.FiniteWord_str'>
-```

[seblabbe]

comment:3

My patch needs work:

sage: P = WordPaths([0,1,2,3])
sage: P
Word Paths on the square grid
sage: w = words.ChristoffelWord(5,8)
sage: P(w)
Traceback (most recent call last):
...
AttributeError: 'LowerChristoffelWord' object has no attribute '_class_str'

I must admit my patch was not that clean and it now shows its limits. The problem concerns the creation of a word from a word especially when the parent changes. Should we try to use some sort of shorcut (like simply change some important attributes like __class__) or not? I have an idea of something better which doesn't use any shortcut. For example, if the input word is a FiniteWord_list, we could simply restore the list and pass through the usual steps for when the input is a list. I think this should be more safe. I just have to think for a solution what we do when the word is defined as an iterator. A new patch (with cleaner code) to be posted soon.

Ideas are welcome.

[seblabbe]

comment:4

In the new patch, I made the corrections to words.py which handles in a some better way construction of words from words. There was one single strange doctest failing in word.py involving word morphisms. So, I improved again the __call__ method of WordMorphism which was doing to much useless stuff.