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

Jay Sulzberger jays at panix.com
Sat Dec 9 03:05:19 UTC 2017


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
> Subject: [Haskell-beginners] Addendum: Monoid algebra
> 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
   "kinds" of Haskell.)

   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
         Emacs with quack loaded"
   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.

I remain, as ever, your fellow student of Haskell and Haskell blog posts,
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
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> _______________________________________________ Beginners
> mailing list Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


More information about the Beginners mailing list