Free monoids and free monads

[runarorama]

This issue is reserved for comments on the blog post Free monoids and free monads. Leave a comment below and it will show up on the blog post's Web page. Thanks!

[Blaisorblade]

a value of type Free[F,A] is either an A or a product of F[_] and Free[F,_]

Sorry for the stupid question, but I can't kind-check that sentence. I assume the "either" refers to a coproduct of objects, that is, type constructors, but A isn't one. Could that be a typo for:

a value of type Free[F,A] is either an Id[_] or a product of F[_] and Free[F,_]

given type Id[A] = A? That would work if the product in question is :*:[F[_],Free[F, _]]#λ — is it?

[runarorama]

Yeah, that's a bit more precise.

[edmondop]

Can you please explain what do you intend with

List[A] has exactly enough structure so that it is a monoid for any given A, and it has no further structure.

Maybe including a link about what does it mean to have enough structure? And also the implication

This also means that for any given monoid B, there must exist a transformation, a monoid homomorphism

Thank you

[runarorama]

To have enough structure to be a monoid is to have an associative operation with a unit. List provides exactly this structure. The associative operation is list concatenation and the unit is the empty list. This is not just one aspect of lists, it is precisely what a list is.

On the implication. Let's say that you wanted to represent an expression in some monoid, as a first-class object. Say, the expression 1 + 2 + 3. You could use the integer 6, but that's a normalized representation. You want 1 + 2 + 3. The most straightforward embedding is: List(1,2,3) with the understanding that there is a + between list elements. In fact, if there exists a mapping A => Int, then you can represent an expression in the integer addition monoid with List[A], no matter what A is. And this is a general thing. If there exists a mapping A => B then List[A] can represent an expression in the monoid B. The "interpreter" for such an expression is foldMap. It is a monoid homomorphism in the sense that given two lists xs and ys, (xs ++ ys).foldMap(f) is the same as xs.foldMap(f) |+| ys.foldMap(f).

[edmondop]

Thank you. I understood the implication.

However I do not understand out of the first part why do you say that List has "no further structure". List is not only a monoid but also a monad, for example .. so it has more structure than just a monoid no?

Thanks

[runarorama]

List is specifically the monad for monoids. Any individual monoid is an algebra for List, and you can say that the List monad is the algebraic theory that the monoids all model.

So it's not so much that List is "also" a monad. It's a monad in a way that is implied by the monoid structure.

[runarorama]

See here for more about the relationship between lists, monoids, and monads.

http://apocalisp.wordpress.com/2010/07/21/more-on-monoids-and-monads/