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

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: @article{Wadler1987ACO, title={A critique of Abelson and Sussman or why calculating is better than scheming}, author={Philip Wadler}, journal={SIGPLAN Notices}, year={1987}, volume={22}, pages={83-94} } which today is at https://www.cs.kent.ac.uk/people/staff/dat/miranda/wadler87.pdf ---------------end new material------------------------------------------------- On Fri, 8 Dec 2017, Jay Sulzberger wrote:

On Fri, 8 Dec 2017, Manny Romero 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" To: beginners@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 # (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" To: beginners@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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners _______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners