# [Haskell-beginners] Clarification (last one!): Monoid algebra

Jay Sulzberger jays at panix.com
Sat Dec 9 04:55:19 UTC 2017

```Ah, please forgive my skipping over an important part of the
standard rant "what is an algebra?".  In the earlier post, which
appears below the cut line, we define a particular algebra X, of
algebra kind K, where Kind K is specified by an NNO K-NNO (we
wrongly ignore identities, relations, and such like) as a triple:

X is given by (we here repeat, up to names, a paragraph of earlier post)
as an algebra of Kind K,

1. a non-empty set |X|

2. the set TK(|X|) of terms with K-NNO as names of operators

3. the evaluation map of Kind K, for X, that is, this eval depends
on X the actual "concrete algebra":

eval: TK(|X|) -> |X|

But the above is not Garrett Birkhoff's definition of an algebra
of Kind K.  Let us look at the Wikipedia article

https://en.wikipedia.org/wiki/Universal_algebra
[page was last edited on 7 December 2017, at 19:18]

Here the concrete algebra X of Kind K is given by

1. a non-empty set |X|

2. for each ('op, op-arity) in K-NNO, same K-NNO as above,
a map

op: |X|^op-arity -> |X|

and nothing more.  No collection of terms in sight.  Note that
'op is not the same as op.  'op is, to use Lisp terminology, just
a symbol.  op is a function with op-arity inputs and one output.
op is everywhere defined and everywhere single-valued.  In Lisp
terms op is the value of 'op.  Op is the value of 'op for the
particular concrete algebra X.  For a different concrete algebra,
say Y, of Kind K, we will in general get a different op as the
value of 'op.

This second definition is the earlier definition.  The two
definitions give a cryptomorphism.  From the first definition,
using eval, for the concrete algebra X, we can get a definition,
using the second definition, that is, using a list of named
operations, of a type-theoretically different object, call it X2,
which are however, for many purposes, but not all, really in some
sense the same object.  That is, X and X2 are cryptomorphic.  Now
I found last week a fine presentation of this by a distinguished
type theorist, and, I will send the reference when, Heaven
forwarding I find it again.

Dear Beginners, Good Night and Happy Hacking!

oo--JS.

PS. Here is Philip Wadler's beautiful article on tick marks:

title={A critique of Abelson and Sussman or why calculating is better than scheming},
journal={SIGPLAN Notices},
year={1987},
volume={22},
pages={83-94}
}

which today is at

---------------end new material-------------------------------------------------

On Fri, 8 Dec 2017, Jay Sulzberger wrote:

>
> On Fri, 8 Dec 2017, Manny Romero <mannyromero at mail.com> wrote:
>
>>   ***I meant the *unit* of the monoid free-forgetful monad, of course.
>> Sent: Friday, December 08, 2017 at 8:32 AM From: "Manny Romero"
>> <mannyromero at mail.com> To: beginners at haskell.org
>> Clarification: I see now that an algebra is not, in fact, a natural
>> transformation, but rather a single morphism from an object's endofunctor
>> image back to the object itself. But my puzzlement still remains! If X =
>> {a, b, c}, then the monoid free-forgetful monad*** will map X to T X =
>> {[], [a], [b], [c], [a, a], [a,b], ... } in precisely the following way:
>> {a -> [a], b -> [b], c -> [c]}. How might a monoid algebra map TX back to
>> X ?   Sent: Friday, December 08, 2017 at 8:07 AM From: "Manny Romero"
>
> Suppose we have a monoid X.  The notation "X" is shorthand for the
> following set theoretic "struct":
>
>  We have a set |X| called the carrier of X.  For now suppose
>  that |X| is always non-empty.  We also have a collection of
>  "terms", call them T(|X|), terms over |X|.  The terms of X are
>  specified by a collection of "names of operations".  Let us
>  call this collection NOO.  Every kind of algebra, we are in the
>  traditional Garrett Birkhoff setup, has its own NOO.  So groups
>  have this NOO
>
>  { * of arity 2, ^-1 of arity 1, 1 of arity 0}
>
>  Monoids have this NOO:
>
>  { * of arity 2, 1 of arity 0}
>
>  Rings have this NOO:
>
>  { * of arity 2, 1 of arity 0, 0 of arity 0, + of arity 2, - of arity 1 }
>
>  Note that the elements of any NOO are pairs of the form (name,
>  non-negative integer).  It is required of an NNO that every
>  name appear exactly once in the NNO as the first element of the
>  pair.  The set of all such names is the set of names of
>  "operations" of the algebra.  These names are not, here type
>  theory comes in, are not the actual operations of any
>  particular algebra of our kind.  (These "kinds" are not the
>
>  OK, Let us now consider a particular algebra X.  Assume X is of
>  the kind Ring.  Now what specifies X?  X is specified by giving
>  a map from the "terms of Ring kind over X" to |X|.  OK, what is
>  the "terms of Ring kind over |X|"?  It is the smallest set,
>  call it TR(|X|), which satisfies
>
>  1. Every element x of |X| is an element of TR(|X|).
>
>  2. If, for example, '+ is the name of the two place operation
>     plus of the ring X, and a is an element of TR(|X|), and
>     b is an element of TR(|X|), then so is the triple
>     ('+, a, b).
>
>  2bis. Same for '0, '1, '*, '-.
>
>  3. To repeat, no other things are in TR(|X|), except as required
>     by 1, 2, 2bis.
>
> Example: Let X be the ring of integers.  Then the number 6, and
> the number 13, and the number minus2 are all in |X|.  Here, using
> something like the usual high school notation, is an element of
> TR(|X|):
>
>   ((- minus2) + (6 * ((13 + 13) + minus2)))
>
> which in the superior notation of Lisp is
>
>   '(+ (- minus2) (* 6 (+ (+ 13 13) minus2)))
>
> The tick mark in front enforces that the thing is an actual term,
> and not the result of "evaluating" the term.  Again, here is an
> ur example of real type theory: An un-evaluated term is an
> entirely different thing from the result of completely evaluating
> the term. It is also entirely different form the process of
> evaluating the term.  Part of what makes learning the category
> theory somehow enturbulated with Haskell, is that one must first
> get such seemingly subtle and pointless distinctions clear.  Of
> course programmers have an advantage over most students of
> mathematics: programmers can distinguish a file of code from the
> result of running the code, and also from the process of running
> the code.  One lesson of category theory is that one can, if one
> has enough attachment points, one can attach many things.  Every
> ridiculous distinction makes a crevice, which may be used as a
> line of attachment points.  Higher order category theory admits
> the third and higher dimensions, Oi, my brain has been softened
> by reading too many "Introduction to Higher Category Theory, with
> Particular Attention to Haskell, BASIC, and absolute binary"s.
> IGNORE PREVIOUS SENTENCE.
>
> OK, so now let us explain what our example is, that is what
> further we need to define the ring X, let us now call it its
> usual name, namely "Z".  Z has an underlying set, |Z|, some of
> whose members are
>
>  minus117, 26, 403, 55, 403, 666, 2, minus2
>
> Now the structure of Z as a ring is fully specified, once we have
> |Z|, and then TR(|Z|), by the most famous map in all of
> Lisp^WHaskell, the evaluation map, let us call it eval.  Here is
> the type, ordinary ur sense, of eval for the ring Z:
>
>   eval: TR(|Z|) -> |Z|
>
> That is, eval runs from the set of all ring terms over |Z| to |Z|
> its own self.
>
> Let is evaluate our example term:
>
> <blockquote
>  what="example term evaluated using Aubrey Jaffer's scm,
>        with Jay Sulzberger's prelude, running atop
>  date="Friday  8 December 2017 21:46:01 -0500">
>
>  > eval
>  #<CLOSURE <anon> "/usr/lib/scm/Init5f2.scm": (x) (#@@eval (#@@copy-tree
> #@x))>
>  > (define minus2 -2)
>  #<unspecified>
>  > '(+ (- minus2) (* 6 (+ (+ 13 13) minus2)))
>  (+ (- minus2) (* 6 (+ (+ 13 13) minus2)))
>  > (eval '(+ (- minus2) (* 6 (+ (+ 13 13) minus2))))
>  146
>  > (quit)
>
>  Process scheme finished
>
> </blockquote>
>
> Please forgive incomprehensible details, which appear due to
> traditional arrangements of the usual sort of Lisp repl.
>
> Let us repeat what we claim:
>
>  The ring Z can be specified by giving its carrier |Z|, which is just
>  the set of integers, and the set of ring terms TR(|Z|), and the map
>  eval: TR(|Z|) -> |Z|.
>
> Now, because I realize that what I intended to write requires a
> few more pages, I break for now.  What more is needed at this
> juncture is the structure of the "free ring on generators G",
> where G is just a set, and not the underlying set of any ring.
>
> One more remark: A ring is not any old X, with arbitrary |X|, and
> arbitrary eval: TR(|Z|) -> |Z|.  A ring is required to obey
> "universal equations", also called "identities".  Here is one ring identity:
>
>  for any term t
>
>  eval((* 1 t)) = eval t
>
> Oi, surface notation/syntax!, we have left out perhaps one, two,
> three maybe more tick marks, or not, oi.  OK, this must be done
> better, but in high school notation^Wrhetoric the identity reads
>
>  forall x (1 * x = x)
>
> Here implicitly the "variable x" ranges over all elements of |Z|,
> that is, the set of integers.
>
> Please forgive incomprehensibility, by reason of compression, of
> this squib!
>
> Perhaps more in a bit, perhaps just some pointers to stuff
> published on the Net.
>
> Jay Sulzberger
>
>
>
>>       Sent: Friday, December 08, 2017 at 8:07 AM From: "Manny
>> Romero" <mannyromero at mail.com> To: beginners at haskell.org
>> Subject: [Haskell-beginners] Monoid algebra I'm having trouble
>> understanding the idea of an algebra using everybody's favorite
>> example, the monoid. What I want, to clarify, is to get some
>> intuition on characterizing the algebra of the free-forgetful
>> monoid adjunction.  If F is the free monoid functor, and G is
>> its right adjoint, then G . F is our monad on SET; and its unit
>> eta is a natural transformation taking every set X to the set
>> (G . F) X ("set of words on the alphabet X") in such a way that
>> every element x in X is mapped to its "singleton word"
>> [x]. "Insertion of generators."  I'm having trouble, on the
>> other hand, understanding how an algebra could establish a
>> natural transformation between the set (G . F) X for any set X,
>> back to X itself. How would those morphisms map the elements of
>> (G . F) X ? Aren't these algebras supposed to "represent" the
>> various monoids on X? But it isn't generally true that a monoid
>> operation maps back to the set of *generators*. I know I'm
>> missing something here, but what is it?  Clarify these natural
>> transformations for me, in "mundane" "baby" monoid-describing
>> language!  _______________________________________________
>> Beginners mailing list Beginners at haskell.org