19

Just reading through category theory book, and decided to apply it to haskell.

The author defines Monoid as:

Monoid is a set L equipped with a binary operation *:LxL->L and a distinguished unit element u in L such that etc...

Taking a "List" structure as a monoid, it is clear that binary operation is concat and unit is [].

But what is the set M here? I tried L = {set of all lists} but I think that leads me into trouble with "is L in L?" question, which seems to be the same problem as sets have.

Or am I thinking of something incorrectly?

EDIT: As pointed out by @applicative, Haskell's lists are monoids called the Free monoids!

Roman Cheplyaka
  • 37,738
  • 7
  • 72
  • 121
Andriy Drozdyuk
  • 58,435
  • 50
  • 171
  • 272
  • 2
    In mathematics the trick to avoid "L in L" problems you switch from normal set theory (zermelo-fraenkel) to a distinction between sets and classes and then you can speak of the class of all sets, or the class of all lists. In addition I think you're referring to the Russel paradox, which is about the `{set of all sets that *don't* contain itself}`. – epsilonhalbe Oct 17 '12 at 07:16
  • 4
    Note that "the set of all lists" is not itself a list, so it doesn't immediately run into contradictions analogous to those found in naive set theory. – Ben Oct 17 '12 at 07:52
  • Do you mean `concat :: [[a]] -> [a]` for your binary operation, or `(++) :: [a] -> [a] -> [a]`? There actually *is* a way in which the former is a monoidal operation, but it's quite an obscure one... – Ben Millwood Oct 25 '12 at 15:23
  • @BenMillwood Could you explain a little bit how `concat :: [[a]] -> [a]` could be a monoidal operation ? – baxbaxwalanuksiwe Jul 10 '17 at 11:15
  • Given that I made that comment five years ago, I can offer you only guesses :) my best guess is that I was referring to the idea that `concat` is the list monad's `join` operation, which is in a certain sense a monoidal operation transforming the functor `List . List` into the functor `List`. – Ben Millwood Jul 17 '17 at 14:58

2 Answers2

29

Instead of saying "List is a Monoid", it would be more accurate to say "For all types a, the type [a] is a Monoid". So for any particular type a, your L will be L = {set of all lists of as}. And with that definition, L can of course not contain itself.

sepp2k
  • 363,768
  • 54
  • 674
  • 675
  • So... the set will always contain one element? What if we concat two lists, how will that Monoid look? E.g. [a] concat [a]... – Andriy Drozdyuk Oct 17 '12 at 04:38
  • 1
    @drozzy I was talking about the type `[a]` (as in "a list of `a`s"), not the value `[a]` (as in "a list containing a single element called `a`"). – sepp2k Oct 17 '12 at 04:40
  • Oh, got it! So isn't that just equivalent to a regular ol' mathematical set with a union operation and an empty set? – Andriy Drozdyuk Oct 17 '12 at 04:45
  • Oh, wait, I guess order matters... and repetition is allowed. – Andriy Drozdyuk Oct 17 '12 at 04:46
  • @drozzy: It's equivalent to a string like you would see in an automata course, if that helps at all. Usually written like `〈abc〉`. – Tikhon Jelvis Oct 17 '12 at 04:47
  • I see. So what would be the definition of a Haskell "List" in math world? I mean there are no "types" etc... – Andriy Drozdyuk Oct 17 '12 at 04:52
  • 9
    I like this answer because it's a fairly direct translation from Haskell. `instance Monoid [a]` uses a universally quantified `a`, so it's really `forall a. instance Monoid [a]`. Which, with a little reordering, is quite close to "for all types `a`, the type `[a]` is a Monoid". – John L Oct 17 '12 at 05:24
4

For any type t you can have that 

L = all elements of the type [t]

then L is a monoid in the trivial way using ++. In fact, we formalize this in Haskell

class Monoid m where
   mempty  :: m
   mappend :: m -> m -> m

this is a "class" of types that have the requisite operations to form a monoid, so

instance Monoid [a] where
   mempty = []
   mappend a b = a ++ b

in fact, this is known as the "free monoid on a"

AndrewC
  • 32,300
  • 7
  • 79
  • 115
Philip JF
  • 28,199
  • 5
  • 70
  • 77
  • When you say `all elements of [t]` do you mean, `L={t1, t2, ...}` or `L={ {t1}, {t1, t2},...}`? (where `t1,t2..` are of type `t`) – Andriy Drozdyuk Oct 17 '12 at 04:50
  • @drozzy: Let's say `t = Bool`, then `L = { [], [False], [True], [False, False], [False, True], [True, False], [True, True], ... }`. (Though strictly speaking you might want to include bottoms as well). – hammar Oct 17 '12 at 05:04
  • @hammar and `[True, True, False]` etc... Just clarifying it can be more than two elements, as long as it is "finite" (which is rather weird definition, as I can potentially come up with an infinite set like this - I guess can think of memory limit on computers as a bounding criteria!) – Andriy Drozdyuk Oct 17 '12 at 05:06
  • @drozzy - it doesn't even need to be finite. `mappend (repeat True) (repeat False)` is perfectly legitimate, for example. – John L Oct 17 '12 at 05:31
  • @JohnL I guess I was going by the definition of the Free monoid: "free monoid on a set A is the monoid whose elements are all the finite sequences", which I understand is what Haskell list is. So then Haskell lists are more than just Free monoids? – Andriy Drozdyuk Oct 18 '12 at 01:11
  • @drozzy sorry but I don't know the answer to that. – John L Oct 18 '12 at 06:16
  • @drozzy You are right, Haskell lists are only free monoids if you only consider finite and total lists (those without bottoms). – danr Oct 18 '12 at 11:01
  • @danr Thanks. What are "total lists" - like injections? And "bottoms"? – Andriy Drozdyuk Oct 18 '12 at 15:07
  • @drozzy: A lot can be said about it, have a look at [HaskellWiki](http://www.haskell.org/haskellwiki/Bottom), and this [SO](http://stackoverflow.com/questions/6379458/the-concept-of-bottom-in-haskell) question. "Total" simply means "without bottoms". Good luck! – danr Oct 18 '12 at 17:03
  • @danr you sure? I'm pretty sure you still get the appropriate adjunction even with infinite lists and bottoms (we are working with the category of pointer partial orders, not set), but I am not positive. – Philip JF Oct 18 '12 at 22:03