>> algebraic structure I talk about the most passionately is the monoid
Can you ELI5 monoid? what problem does it solve which isn't easy in other languages without it?
edit: thx everyone.
Can you ELI5 monoid? what problem does it solve which isn't easy in other languages without it?
edit: thx everyone.
In code:
smash :: Monoid a => a -> a -> a
empty :: Monoid a => a
instance Monoid Int where
smash 25 x = x
smash x 25 = x
smash x y = 2*x^2 - 3*x*y
empty = 25
empty `smash` x = x -- left identity
x `smash` empty = x -- right identity
(x `smash` y) `smash` z = x `smash` (y `smash` z) -- associativity
---
> That is usually a terrible idea.
Not at all. Think about the structure of a proof of negation. You make a “silly” assumption and “play along” until you reach a contradiction.
Function of arity-2 (possibly expressed as an infix operator)
Which is closed over the set of values that are its arguments/parameters
For a domain (set of input values) which contains a value that converts the function into an identity function when used.
E.g. -
Addition over real numbers (or integers...), becomes an identity function when one arg is 0
Multiplication over real numbers (or integers...), becomes an identity function when one arg is 1
Something along that line?
I guess that makes it useful for a fold/reduce type function where the final result is the same type as the input stream, and the initial value can be identified as a known default.
Lists under concatenation Booleans under AND Booleans under OR Numbers under max Numbers under min
Anything you describe as a monoid has to have three properties: you can add them together, there's an "empty" or "zero" value, and (a + b) + c = a + (b + c).
For example, strings with concatenation are a monoid, because you can use an empty string and the string + operator.
For example, integers with addition are a monoid, because you can use 0 and the integer + operator.
For example, sets are a monoid, because you can use the empty set and the union operator.
For example, a "Picture" data type could be a monoid, because you could have a fully-transparent picture and use an "overlay" operator to put one picture on top of another.
Why do you care? Well, for one thing, it just makes it easy to find the function or operator you want to use: as the OP said, if I feel like my data type should have a concat or append operator but I don't know what it's called, I just use mappend / mempty / mconcat.
But, as another practical example: "sum" in Python works for numbers, but I've seen folks assume that it works for anything that you can use + on, and so try and use strings with it. But, because "sum" isn't a general purpose tool, that doesn't work! In Haskell, on the other hand, the equivalent -- mconcat -- will work on anything that is a monoid. (And can be specialized to work faster for specific data structures.)
Other languages also have monoids. If someone tells you Haskell has monoids and other languages don't, what they really mean is, Haskell makes explicit the monoid pattern / interface, where other languages have it implicitly for different data types. Talking about the pattern explicitly isn't revolutionary, but it can be pretty useful for discoverability and writing "general" algorithms.
Instead of calling data structures monoids, you'd get the same effect if, as a programming language community, you decided that as many types as possible should support "+", and that every data type that can should have a makeEmptyThing() method, and that it would be weird and not ok if x + makeEmptyThing() didn't equal x and if (x + y) + z didn't equal x + (y + z), and then subtly shamed any libraries that defined makeEmptyThing() and + in ways that didn't follow that pattern. But if your programming language community did this (for consistency) you'd probably want to come up with a name for it -- "Addable", "Concatable", etc -- and the Haskell community chose "Monoid" (because of relationships to theory etc etc).
A monoid isn't just a data type. Mathematically, it's a set ("data type" is plenty close enough, in this context) and an operation. Integers with addition are a monoid. But so are integers with multiplication. And these are two different monoids. Haskell confuses this issue a bit - they way the Haskell libraries are set up you can only name one Monoid instance per type, and so types that form monoids in several interesting ways get wrapped in "new types" so you can name each of the several. This mostly works fine, but is a bit hacky from a math POV, and I think doesn't lead as well as it might to a more general understanding.
It's worth noting, too, that some of the Haskell libraries - particularly those from the early days - make some unfortunate decisions about what instances to bless. I often complain about the Monoid instance for Map. Map forms a monoid under union so long as we combine values (on collision) associatively. Unfortunately, the library doesn't let us pick how they are combined, it just takes the left one. That's usually not what I want, and it's particularly painful when I've been combining Sets with monoid operations and now realize they need to carry some extra info.
... and then of course there's floating point, which probably shouldn't even be Num.
> But if your programming language community did this (for consistency) you'd probably want to come up with a name for it -- "Addable", "Concatable", etc -- and the Haskell community chose "Monoid" (because of relationships to theory etc etc).
There are two things I really like about using the name Monoid, compared to the others.
First, it's much clearer what the rules are. We aren't stuck wondering whether strings or products are "really" "Addable", whether functions of the form (a -> a) are "really" "Concatable" (... and what about nonempty strings? you can concatenate them, but they have no identity object...).
Clarity in an interface means I know what properties I can rely on. You can define those properties precisely with "more intuitive" names, but then the actual interface doesn't match the intuition and people won't realize it, which is worse. You could get precise and intuitive by adding verbosity - "AssociativeOperationWithIdentity". My principle objection there is readability and aesthetics, but if that's what a community wants to go with okay... "Monoid" is short and unambiguous and well established in related fields.
That last point touches on the other thing I like. There are mathematical results that can be useful to programmers. Reducing the translation needed helps make those more accessible. And everyone could do with knowing just a bit more algebra :-P
I don't know python very well, but aren't string special cased? It does work with lists.
sum([[1,2,3],[4,5,6]], [])The same thing does not work for a sequence of strings and an empty string.
sum(["abc","def"], "")
[0] https://github.com/python/cpython/blob/5837d0418f47933b2e3c1...
A monoid is a set and an binary operation on the elements of that set with the following properties:
1.The operation acts on two elements of the set to produce another elemenent of that set(closure).
Examples:
You have a set od natural numbers {0,1,2,3..} with standard addition. Whichever two natural numbers you choose to add you will get a natural number back.
A set of MxN matrices and matrix addition. If A and B are two MxN matrices A+B is a MxN matrix.
2.The order in which the operations are performed does not matter(associativity). So for all elements of our set a,b and c and the operation +:
a+(b+c)=(a+b)+c
must be valid.
Examples:
Let L be a set of strings and + concatenation. "Just"+(" an "+ "example")=("Just"+" an ")+"example"
Vector addition over vectors of same dimension.
3.There is an element(unique!) in the set which when applied to any element of the set returns that element(identity, neutral element).
e+a=a+e=a
e is identity
Examples:
0 is identity for standard addition: 0+1=1, 4+0=4
1 is identity for standard multplication: 1*7=7
""(empty string) is identity for string concatenation
It also comes with a contract, like the contracts of "equals", "hashCode" or Comparable in Java. The contract says that the operation must be associative, and that the element you produce out of thin air must be neutral: when you combine it with another element it leaves the other element unchanged.
One benefit of having such general interfaces is that you can reuse code across a wide range of domains. For example: the Comparator interface in Java can be seen as a monoid, with the "thenComparing" function as the combination operation: https://docs.oracle.com/javase/8/docs/api/java/util/Comparat... You could build a list of comparators and concatenate it, map a function that produces a comparator over a list and concatenate it, and so on.
Another benefit is that you can be quite general when specifying requirements for your functions. In Haskell, the Writer monad only requires the type of the accumulator to be an instance of Monoid. So you can user regular lists, difference lists, or the integers under addition.
Also in Haskell some composite types automatically satisfy an interface if their components do, saving you work. For example, a tuple of monoids is automatically a monoid. Any function that returns a monoid is itself a monoid as well. (Functions that begin and end in the same type can be monoids in a different way: the neutral element is the identity function and the combination operation is composition.)
Obviously, you can do that in any untyped language, too, but explicitly defining these contracts makes code easy to manage and understand. And the compiler will tell you if/how you're doing something wrong.
And there I was, thinking that this only applied to monads :)