3 ms·

No need for category theory (although that might be interesting in its own right, later) or Haskell (ditto). I might start with https://en.wikipedia.org/wiki/M

No need for category theory (although that might be interesting in its own right, later) or Haskell (ditto). I might start with https://en.wikipedia.org/wiki/Monoid#Definition https://en.wikipedia.org/wiki/Monoid#Definition or pp17-20 of https://www.cs.utoronto.ca/~hehner/aPToP/aPToP.pdf https://www.cs.utoronto.ca/~hehner/aPToP/aPToP.pdf Monoid is a greek-derived name, but the structure itself is very simple: as the name implies, it's completely one-dimensional (aka linear: you can think of them as being like those whiteboard pens that snap together). If I have a monoid y, I can prepend x to it to get (x;y), or I can append z to it to get (y;z), or I can do both, in either order, to get (x;y;z). You are certainly familiar with this behaviour for addition: 1+(2+3) == (1+2)+3, and may be familiar with matrix multiplication, which differs from elementary school multiplication in that A*B is no longer necessarily equal to B*A, but it is still always true that A*(B*C) == (A*B)*C. This is distinct from the behaviour of lists, where one order will produce [x [y z]] and the other order will produce [[x y] z] — despite having the same leaves, they are different lists, with distinct nesting patterns. Finally, what distinguishes monoids from semigroups is that they have an identity: if we call it ∊, then we have that ∊;y == y == y;∊ (in practice this is not a big distinction, because even without a natural identity one can almost always add a formal identity) Note that you probably are already very familiar with identities in various contexts: 0+2 == 2 == 2+0, 1*3 == 3 == 3*1, and ""++"foo" == "foo" == "foo"++"", etc. (and you may be familiar with the difference between finite automata which allow identity transitions —easy to build, not so efficient to use— and those which do not —efficient to use, not so easy to build—). Does any of that make sense?

maxk42 3y ago
How does this differ from a one-dimensional array?
- selecsosi 3y ago
  As part of the definition of the monad it includes "applying" computation on the underlying dataset (wrapping and then applying a function is defined). The mondad also defines the resultant type of the operation (unwrapping) and so in another language, something like mapping a function over a dataset is a built in "consequence" of the definition. This makes it natural to express a program as a pipeline of operations over a variety of dataset inputs by wrapping, mapping, and unwrapping operations. An example is something like the IO monad in haskell allows a programmer to incorporate non-functional (side-effect) computations (e.g. writing to disk or to console) naturally where as a 1d list (more like a buffer) doesn't naturally express the same semantics
- 082349872349872 3y ago
  It depends upon what you mean by "a one-dimensional array". In the C or Fortran sense, it's easy to work with individual elements of the array, but not so much the array as a whole. (in the example above, both y and x;y;z are values in the monoid, conceptually at the same level, like "f" and "foo" are both strings despite one being length-1, and like 5 and 60 are both numbers despite one being prime) In more recent, but still algol-like, languages, it's possible to work with slices of arrays as well as individual elements, but often these slices are views backed by physical arrays, so slices and arrays are similar but still not equivalent. In array languages (the APL family), there is very little difference, as it is perfectly natural to treat entire arrays (or parts of them) as values and prepend or append them to each other. (pedantry: these languages go well beyond the 1D model and allow N-dimensional cubical structures; after they started to allow ragged structures as well they came much closer to the tree-orientation of LISP-likes) As stated earlier, I think of whiteboard pens (snapping top to bottom, resulting in something equally snappable), or the bytestreams that flow through Unix pipes, where there is always a before and an after but nesting isn't part of the basic deal. I believe many things in CS are best treated (involved fewer arbitrary decisions) as monoids and semilattices and interactions between these structures, but because of tradition we try to attack them with lists and sets, then wind up mired in accidental complexity trying to remove layers of nesting that would never have occurred had we started with simpler representations. (eg if you feel the need to invent a "programmable semicolon" to ensure that all your lists get flattened as-you-go or the need to make "samefringe" break free of normal stack discipline, you may well make great strides in implementing Haskell or Go, but you may also be doing work which could have been completely avoided [ok, at least abstracted away] by a different choice of representation) Finally, note that this whole digression was due to the (in my view "accidental") problem of unquote-splicing: using monoids (a) removes the need for two unquote forms, but (b) doesn't prevent anyone from expressing their computed SGML fragments via a monoid of tree values; a "forest" if you will.
  - fooker 3y ago
    Fortran is literally a language designed to work with (multi-dimensional) arrays as a whole.
- nyssos 3y ago
  The other replies are massively overcomplicating things. A monoid is - a set `X` - together with an associative binary operation (let's call it `+`) - and an element (`0`) such that `a + 0 = 0 + a = a` for all elements `a` in `X`. Monoids are a class of structures, the collection of all arrays of a given type (with concatenation as the monoid operation, and the empty array as its identity element) is a particular example of a monoid. Other examples include the natural numbers under addition, the integers under multiplication, functions `T => T` under function composition, booleans under and, booleans under or, and strings under concatenation. They're one of the simplest and most common algebraic structures.
  - maxk42 3y ago
    Thank you. In ten+ years, I think this is the simplest and clearest explanation I've read.

maxk42 3y ago

How does this differ from a one-dimensional array?

selecsosi 3y ago
As part of the definition of the monad it includes "applying" computation on the underlying dataset (wrapping and then applying a function is defined). The mondad also defines the resultant type of the operation (unwrapping) and so in another language, something like mapping a function over a dataset is a built in "consequence" of the definition. This makes it natural to express a program as a pipeline of operations over a variety of dataset inputs by wrapping, mapping, and unwrapping operations. An example is something like the IO monad in haskell allows a programmer to incorporate non-functional (side-effect) computations (e.g. writing to disk or to console) naturally where as a 1d list (more like a buffer) doesn't naturally express the same semantics
082349872349872 3y ago
It depends upon what you mean by "a one-dimensional array". In the C or Fortran sense, it's easy to work with individual elements of the array, but not so much the array as a whole. (in the example above, both y and x;y;z are values in the monoid, conceptually at the same level, like "f" and "foo" are both strings despite one being length-1, and like 5 and 60 are both numbers despite one being prime) In more recent, but still algol-like, languages, it's possible to work with slices of arrays as well as individual elements, but often these slices are views backed by physical arrays, so slices and arrays are similar but still not equivalent. In array languages (the APL family), there is very little difference, as it is perfectly natural to treat entire arrays (or parts of them) as values and prepend or append them to each other. (pedantry: these languages go well beyond the 1D model and allow N-dimensional cubical structures; after they started to allow ragged structures as well they came much closer to the tree-orientation of LISP-likes) As stated earlier, I think of whiteboard pens (snapping top to bottom, resulting in something equally snappable), or the bytestreams that flow through Unix pipes, where there is always a before and an after but nesting isn't part of the basic deal. I believe many things in CS are best treated (involved fewer arbitrary decisions) as monoids and semilattices and interactions between these structures, but because of tradition we try to attack them with lists and sets, then wind up mired in accidental complexity trying to remove layers of nesting that would never have occurred had we started with simpler representations. (eg if you feel the need to invent a "programmable semicolon" to ensure that all your lists get flattened as-you-go or the need to make "samefringe" break free of normal stack discipline, you may well make great strides in implementing Haskell or Go, but you may also be doing work which could have been completely avoided [ok, at least abstracted away] by a different choice of representation) Finally, note that this whole digression was due to the (in my view "accidental") problem of unquote-splicing: using monoids (a) removes the need for two unquote forms, but (b) doesn't prevent anyone from expressing their computed SGML fragments via a monoid of tree values; a "forest" if you will.
- fooker 3y ago
  Fortran is literally a language designed to work with (multi-dimensional) arrays as a whole.
nyssos 3y ago
The other replies are massively overcomplicating things. A monoid is - a set `X` - together with an associative binary operation (let's call it `+`) - and an element (`0`) such that `a + 0 = 0 + a = a` for all elements `a` in `X`. Monoids are a class of structures, the collection of all arrays of a given type (with concatenation as the monoid operation, and the empty array as its identity element) is a particular example of a monoid. Other examples include the natural numbers under addition, the integers under multiplication, functions `T => T` under function composition, booleans under and, booleans under or, and strings under concatenation. They're one of the simplest and most common algebraic structures.
- maxk42 3y ago
  Thank you. In ten+ years, I think this is the simplest and clearest explanation I've read.