Talk:Free monoid

Cheers for tidying this up a bit, but one comment. I deliberately avoided saying alphabet in the first paragraph since this wod is usually reserved for finite sets, while free semigroups and monoids are defined over sets of arbitrary cardinality - compare with the last paragraph. If you don't disagree I'll remove the reference from the first paragraph. Best wishes, Cambyses 16:10, 13 Mar 2004 (UTC)

It now mentions alphabet and words only for finite ground sets, but still mentions strings and string concatenation in the leading paragraph. Is this as it should be? Rp (talk) 18:05, 14 August 2009 (UTC)[reply]

Comparison with lists

This is misleading: lists have a head and tail operation, not usually a concatenation operation. A better comparison is with strings. Rp (talk) 18:05, 14 August 2009 (UTC)[reply]

You can't define concatenation on lists? And what is a list abstractly if not a string of elements of some other data type? The alphabet need not be characters. The article on list was wrong. I've fixed it. Pcap ping 18:49, 14 August 2009 (UTC)[reply]

P.S. The error in the list article was [introduced two weeks ago]. Pcap ping 18:57, 14 August 2009 (UTC)[reply]

Misleading

There's another problem in that section though. The foldl functional can take more than a binary operation as argument, i.e. its type is foldl :: (a -> b -> a) -> a -> [b] -> a. So the function passed to foldl is a semigroup action, not necessarily the semigroup operation itself. Pcap ping 19:21, 14 August 2009 (UTC)[reply]

This article correctly describes the case of foldl1 (same link above), which is a particular case of foldl with type (a -> a -> a) -> [a] -> a. Pcap ping 19:26, 14 August 2009 (UTC)[reply]

A further problem is that foldl/foldr and foldl1/foldr1 do not really require an associative operation; otherwise you don't really need the left and right variants, in particular foldl1/foldr1, which have the same signature, but implement different algorithms. So saying that folding requires a homomorphism is quite misleading. Pcap ping 19:32, 14 August 2009 (UTC)[reply]

The article never said that folding requires a homomorphism. I've restored the deleted section. The interpretation of lists as free monoids is important in computer science in that the algebraic structure gives a set of list operations which are, in a sense, "natural." Folding an associative operator has several advantages over foldl/foldr: an associative fold can be parallelised. -- Radagast3 (talk) 14:19, 8 April 2010 (UTC)[reply]

Is this not a contradiction

If the first line is correct in it being all the finite sequences then the free monoid must be finite. How then can the natural numbers under addition be a free monoid as the set of natural numbers is not finite. — Preceding unsigned comment added by 80.229.45.38 (talk) 10:18, 28 October 2020 (UTC)[reply]

Each individual natural number is finite. It is not true that a collection of finite things must itself be finite. —David Eppstein (talk) 16:58, 28 October 2020 (UTC)[reply]

Characterization of free submonoids

Planetmath has some material, on the characterization of free submonoids, that we could copy over. Link: https://planetmath.org/characterizationoffreesubmonoids Thatsme314 (talk) 08:43, 12 July 2022 (UTC)[reply]

"Sturmian morphism" listed at Redirects for discussion

The redirect Sturmian morphism has been listed at redirects for discussion to determine whether its use and function meets the redirect guidelines. Readers of this page are welcome to comment on this redirect at Wikipedia:Redirects for discussion/Log/2024 August 17 § Sturmian morphism until a consensus is reached. 1234qwer 1234qwer 4 14:42, 17 August 2024 (UTC)[reply]