implement substitute for monoids

[was]

On 9/5/07, Joel B. Mohler <joel@kiwistrawberry.us> wrote:
\> Yes, so I found FreeMonoid after sending my first e-mail and was testing it
> out.  I think I may have found something that is not implemented:
> 
> sage: a=FreeMonoid(1,'a').0
> sage: a*a
> a^2
> sage: a.substitute(5)
> a  # should be 5?
> sage: a.substitute(a=5)
> a  # should be 5?
> 
> I would have expected those last two results to be 5 -- am I missing
> something? 

The whole "substitute" architecture was implemented in SAGE
long after monoids were implemented.  So you'll have to implement
monoid substitution. 

> I guess substituting isn't an entirely common operation for free
> monoids, but it seems to be a sensibly defined operation.  Then again, maybe
> not:
> 
> sage: M.<x,y> = FreeMonoid(2)
> sage: (x*y).substitute(x=1)
> x*y  # I would think that this is 1*y
> 



> I find that result unsatisfactory as well, but I sure don't have a good idea
> about what ring (?) the result '1*y' would be a part of.

Just do the arithmetic.    All monoids have a 1 by definition, so 1*y is just "y"
in that monoid.

William

[zimmerma]

A positive review for me.

Note: I did all doctests, and got exactly 22 Segfaults, as with vanilla 4.3.3 (see #7773). Thus if a new failure occurred within one of those 22 doctests, I couldn't see it.

[jhpalmieri]

Merged in 4.4.alpha0.