Talk:Free monoid

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

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[edit]

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[edit]

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[edit]

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[edit]

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]