[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:
@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 <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