Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

How does this differ from a one-dimensional array?


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.


Thank you. In ten+ years, I think this is the simplest and clearest explanation I've read.


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.


Fortran is literally a language designed to work with (multi-dimensional) arrays as a whole.


Ummm...no.

Fortran was originally designed as a language that made dealing with numbers in arrays easy, but the arrays themselves were containers that had a fundamentally different type than numbers. In a true array language like APL there's no difference.

Modern versions of Fortran have blurred the distinction somewhat but in older Fortran arrays were very different from numbers. Arrays couldn't even be dynamically allocated or resized back in the day much less "added together," whatever that might mean.

An analogy: Fortran has arrays like C has functions. But that doesn't make Fortran an array language any more than C is a functional language.

APL is an array language like Haskell is a functional language.

In Fortran, numbers are the fundamental data type. Arrays are just collections of numbers. In APL, arrays are fundamental. A number in APL is just a lonely array.


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




Consider applying for YC's Summer 2026 batch! Applications are open till May 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: