compute DOL languages

[videlec]

With the patch

sage: s = WordMorphism({0: [0,1], 1:[0]})
sage: %time L = s.language(10000)
CPU times: user 221 ms, sys: 10.3 ms, total: 231 ms
Wall time: 221 ms
sage: len(L)
10001

CC: @staroste @seblabbe

Component: combinatorics

Author: Vincent Delecroix

Branch/Commit: 431bee7

Reviewer: Sébastien Labbé

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

[videlec]

Branch: u/vdelecroix/26307

[videlec]

Commit: 4036c1c

[videlec]

New commits:

f144c02	26307: DOL languages
4036c1c	26307: more naive (and faster) powering of morphisms

[seblabbe]

comment:2

This is great! I remember almost 10 years ago, I suggested to write such a function and I remember you said it was not a good idea :P

I would ask that you add an INPUT block for both language and _language_naive methods that explains both inputs n and u and also what happens when u=None. After this is done, it will be good to go for me (if all tests pass which I didn't check yet).

[seblabbe]

comment:3

I obtain two failing doctests (also reported by the patchbot report) :

sage -t --long src/sage/combinat/words/morphism.py  # 2 doctests failed

[videlec]

comment:4

I am not 100% convinced that this patch is a good idea. The problem is that you might expect sigma.language() to return an object for the set of factors, because for example you want to access the words of length {100, 101, 102, 103} and for that purpose it make no sense to call three times s.language(n) four times. We can still make that happen in the future without breaking backward compatibility.

[sagetrac-git]

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

eddab47	26307: fix doctests
1c7bc62	26307: INPUT sections

[sagetrac-git]

Changed commit from 4036c1c to 1c7bc62

[seblabbe]

comment:7

I will be pickky, but can you use double -- where needed please to conform with the developer manual:

- - ``n`` - non-negative inte
+ - ``n`` -- non-negative inte

[seblabbe]

comment:8

One other comment, I think language should return a set instead of a list. It is better to let the translation from set to list be done by the user if he needs to.

- return list(L)
+ return L

Often, one wants to test containment and it will be stupid that the user have to do set(m.language(1000)).

[seblabbe]

Reviewer: Sébastien Labbé

[videlec]

comment:10

Replying to @seblabbe:

One other comment, I think language should return a set instead of a list. It is better to let the translation from set to list be done by the user if he needs to.

- return list(L)
+ return L

Often, one wants to test containment and it will be stupid that the user have to do set(m.language(1000)).

Agreed. Though w.factor_set() returns a "Sage set" and not a Python set... this is not so nice.

[sagetrac-git]

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

a4f0cd4	26307: conform docstring
431bee7	26307: return set

[sagetrac-git]

Changed commit from 1c7bc62 to 431bee7

[videlec]

comment:14

Thanks Sebastien!

[vbraun]

Changed branch from u/vdelecroix/26307 to 431bee7