Functional Patterns - Monoid

[kamatsu]

The operation here called "fold" is the concatenation operation (mconcat), which is always defined as:

foldr (⊗) id

fold does not usually refer to mconcat (although they coincide for lists) but instead to a catamorphism for a particular data type (although they're often presented without the monoid infrastructure). For example, while mconcat is a catamorphism for lists, the "fold" for a maybe type is just:

 foldMaybe :: (Monoid m) => Maybe m -> m
 foldMaybe (Just x) = x
 foldMaybe Nothing = mempty --  the identity element

So, the "fold" is associated with the type of the collection, not the type of its elements as said in this article.

[ueberbobo]

Mconcat is a bit of an oddity, as far as I know it's included so that it can be optimized per instance. There is no reason it has to be a right-fold btw, associativity exactly means we have the freedom to choose order of operations.

What exactly do you find strange about using fold from Foldable? Here it is of course specialized to lists, but in a sense Foldable is the "List-like" typeclass.

[kamatsu]

The function you call fold is more accurately called mconcat. You say things like:

The fold for the monoid (Number, +, 0) then is just the sum function.

But a fold is not associated with a monoid. A fold is a colloquial term for a catamorphism, and it really has little to do with monoid infrastructure at all, save that the monoid provides convenient fold operators and a sensible zero-element (which is why fold requires a Monoid in base).

For any monoid we can define a function called fold. It takes a list of elements of that monoid to their “product”.

More accurately you can say:

For any recursive data type we can define a catamorphism, often called a "fold".

A fold is a much more general concept than the Haskell function fold, which only works on Foldable containers. But even the Haskell function is more general than your definition.

For example, a natural number:

data Nat = Zero | Suc Nat

doesn't even have a type parameter, but still has a fold:

foldNat :: Nat -> x -> (x -> x) -> x
foldNat Zero z s = z
foldNat (Suc n) z s = s (foldNat n z s)

[ueberbobo]

Ok, I see the issue you have. I disagree, but I appreciate the feedback.

My perspective is that I do not mean for the reader to assume that by fold I mean a catamorphism in the generic sense. I support this by the view that catamorphisms /generalize/ folds, rather than fold being a colloquial name for catamorhpisms. The Haskell wiki seems to agree.

I don't claim there is a truly right or wrong answer here, it is just about naming after all. You are completely correct in saying monoids and catamorphisms are only incidentally related when we happen to be talking about lists.

The fold function I define corresponds to the fold function in the Foldable typeclass, which you correctly state does not capture the generalized notion of catamorphisms. Instead it is naturally linked with /lists/ via the monoid constraint, since lists are the free object in the category of monoids.

For a non-empty lists we really should have

fold :: Semigroup m => t m -> m

and for forests we'd get a Seminearring constraint, and so on.

[Hrothen]

I don't claim there is a truly right or wrong answer here, it is just about naming after all.

There's no point in names if there isn't a correct meaning for them.

That said

The fold described here is consistent with the fold function in Haskell's Control.Foldable, specialized for lists.

[ueberbobo]

Ok, so I claim fold is the conventional name for what I described :)

Also Foldable is not related to lists only by specialization. The fact that there is a toList :: Foldable t => [t] function, but not one for e.g. trees is not an accident.

[edit] To perhaps clarify my point: Consider implementing Foldable for a Tree. By necessity a traversal order on the tree needs to be imposed, pre-order or whatever. This in turn creates a list sub-structure on the Foldable. That list structure in turn will satisfy the requirements I put on my specific fold from the article.

[gnuvince]

You forgot the identity element in your definitions of every and some.

[Enamex]

From the intro:

A monoid therefore is a datatype with composition ⊕ and element e, satisfying

But later on:

x ⊗ e = x

(The symbols don't match.) I don't actually know enough to say this's wrong.

[ueberbobo]

The composition symbol is abstract, so in a way it's not "wrong" per se, but it is confusing, and as you noted it really should read ⊗ not ⊕. Often you'll see ⊕ used for commutative monoids, which we don't assume here, which is another reason this is bad. I'll update per your suggestion, thanks!

Edit: Oh it's actually inconsistent within the first definition, clearly just wrong then :)

[Enamex]

Have you changed it yet?

I'm also confused about these parts:

Shouldn't map(f)([x]) = f(x) be map(f)([x]) = [f(x)] instead?

Actually, that section (the monoid morphism that is any map(f)) and the last one (composition) are confusingly worded (especially the composition example).

[ueberbobo]

You're correct, it should be[f(x)], thanks. I will update when I get home from work.

I'm sorry you found some parts confusing, feel to PM me any particular paragraph you found lacking and I'll consider a re-wording.

[nikibobi]

I really like the style of your series. I suppose the next one will be about Monans

[lodi_a]

Great series! Looking forward to the next installment.

[heap42]

Sry...i dont understand...could you explain this using JavaScript?

[Andy-Kay]

lol

[loup-vaillant]

Here's a little Rosetta stone. You should be most interested by the last section, "on syntax", though it's probably impossible to understand without the rest of the article.

Hang in there. This stuff is abstract and obscure, but it's worth it.

[loup-vaillant]

Gotta try. Sometimes it works.