8 ms·

A Brief Guide to a Few Algebraic Structures

266 points by edgarvm 7y ago

JoelMcCracken 7y ago
Oh wow, this looks great. I had started working on my own FP glossary, but this has a ton of information and is clear enough that I'm sure many will find it very very helpful.
- GrumpyNl 7y ago
  It is very clearly written. Never really done algebra, but after this , it start to make sense.
nilkn 7y ago
> Rng I really think names without a fairly obvious way of saying them out-loud should just be avoided/deprecated. I can't pronounce this as "ring" (because then you'd think I was referring to a ring, not a rng). Do I just spell it out? R-N-G? I'd rather just call it a non-unital ring. That involves more letters but is much more descriptive (to a mathematician, anyway).
- msclrhd 7y ago
  I pronounce it /r@N/ -- i.e. like 'ring' but with the 'a' in comma, or the o in button. Although if it was a Rng formed by a pseudo-random sequence, then R-N-G would be apt ;).
  - pvg 7y ago
    If you want to use them, HN will take most funny squiggles: \ˈrəŋ\. It draws the line at emojis.
- Koshkin 7y ago
  To be fair, the author has already made this point.
- dramaqueen 7y ago
  You pronounce it as "rung".
- jaddood 7y ago
  As mentioned, it should be pronounced "rung," but in any case, removing the i and suddenly making it a word and pronouncing it in a very unexpected way is really pretty stupid. I think, if one's really insisting on using "ring" but without the i, at least call it "rung" not "rng" so that its pronounciation is clear. If it's so important to have a "rng" instead of a "ring" then using its name in some example of its usage should probably be better.
  - dramaqueen 7y ago
    Well, words, terms, notations and conventions come super cheap in math. You can call/denote "rng" anything you want. You just have to let your readers/interlocutors know about your conventions at the outset which is a standard practice in math anyway. For another thing, "r(u)ng" to me it's no different from writing "colonel" and reading it "kernel" (historical accident aside) :) There's also "lieutenant" which is pronounced " leftenant" in UK.
    - mangamadaiyan 7y ago
      Lieutenant is "Leftenant" in other parts of the world (those with a British connection, of course) as well.
- mlevental 7y ago
  it's a ring without (i)dentity. makes perfect sense to me. Besides this is a mathematical object not a programming thing - math has its own culture and conventions and pronunciation isn't a cultural value.
  - dllthomas 7y ago
    At least, not pronunciation that's unambiguous whilst you're not also writing on a blackboard.
- amatecha 7y ago
  Yeh, she calls it out right in the definition: "If we may speak frankly, the rig and rng nomenclatures are abominations. Nevertheless, you may see them sometimes, but we will speak of them no more." :)
  - nilkn 7y ago
    Sure, but I also wanted to suggest a simple descriptive name that sidesteps the problem.
- lonelappde 7y ago
  It's "ring without i". i is of course "identity", which is conventionally denoted e, because i is usually the square root of unity. This works pretty well if you pronounce i as in French so it's a homophonic with English e. Isn't math a wonderful language of use for computer programming? It's so international, breaking the hegemony of English.
- JadeNB 7y ago
  > I really think names without a fairly obvious way of saying them out-loud should just be avoided/deprecated. I can't pronounce this as "ring" (because then you'd think I was referring to a ring, not a rng). But 'nearring' doesn't bother you? If I'm at a talk on rngs where the distinction from rings is important, then I'll know that's the kind of talk that I'm attending, and hear accordingly; or else the speaker will make a huge deal of it (and then probably not use the word).
wsxcde 7y ago
Is there a good textbook that covers these? I am primarily interested in a computer science perspective to these algebraic structures.
- earthicus 7y ago
  Many of them feature prominently in Stepanov's books, Elements of Programming and From Mathematics to Generic Programming. 'Elements' is a technical monograph, while the other is a more lightweight read, halfway between semi-pop-science and a textbook. There's also an old textbook by Birkhoff & Bartee called 'Modern Applied Algebra' that i like. It's not super duper computer science-y but might be worth browsing through the table of contents at least. Edit: I snapped some photos of the table of contents since you can't see it on the amazon page: https://imgur.com/a/RFIf4CD https://imgur.com/a/RFIf4CD
- gtycomb 7y ago
  'Topics In Algebra' by I.N.Herstein. Back in college years this was my first book. Despite many other books (which might look easier) I always came back here because of the care it takes to walk through well crafted progression of concepts. (Not a 'computer science' book but you will need something like this for the Algebra part)
- nandemo 7y ago
  My favourite abstract algebra textbook is Fraleigh's A First Course in Abstract Algebra. Unlike the article here, which just dumps you a bunch of definitions, the book introduces each structure with proper motivation. It's not a CS approach though. https://www.amazon.com/First-Course-Abstract-Algebra-7th/dp/0201763907 https://www.amazon.com/First-Course-Abstract-Algebra-7th/dp/... (the 1-star reviews apply to the Kindle version, not the contents. Just get the paperback and you'll be fine) If you want a CS approach I suggest learning basic Haskell then tackling the fantastic Typeclassopedia. The downside is you'll be missing on structures/theorems that are super useful in math but not that useful in programming. https://wiki.haskell.org/Typeclassopedia https://wiki.haskell.org/Typeclassopedia
  - commandlinefan 7y ago
SAI_Peregrinus 7y ago
The Wikipedia page on Algebraic structures is rather more detail than I usually want, but the page "Outline of algebraic structures"[1] is a great quick reference. [1] https://en.wikipedia.org/wiki/Outline_of_algebraic_structures https://en.wikipedia.org/wiki/Outline_of_algebraic_structure...
_hardwaregeek 7y ago
Interesting seeing this defined from a functional programming/category theory perspective. Personally I like examples for my algebraic structures along with some simple proofs why they're that structure. What was extremely useful for my Algebra class was a Wikipedia note detailing the hierarchy of rings via set inclusion: commutative rings ⊃ integral domains ⊃ integrally closed domains ⊃ GCD domains ⊃ unique factorization domains ⊃ principal ideal domains ⊃ Euclidean domains ⊃ fields ⊃ finite fields Found here: https://en.wikipedia.org/wiki/Integral_domain https://en.wikipedia.org/wiki/Integral_domain
crimsonalucard 7y ago
I'm learning category theory to understand haskell better. I'm finding category theory to be almost a theory about program structure in the context of composition. It's giving me a whole new perspective on one of the least concrete things about programming namely design. How relevant is abstract algebra to programming? Will it change my perspective on everything related to programming? How much of a mind bender is it compared to category theory?
- hamdshah 7y ago
  Any references you would like to share ?
  - louthy 7y ago
    Not the OP, but this is a great book to get started: https://github.com/hmemcpy/milewski-ctfp-pdf https://github.com/hmemcpy/milewski-ctfp-pdf
- merijnv 7y ago
  > I'm learning category theory to understand haskell better. I would consider myself a fairly expert Haskell programmer and I have (for fun/curiousity) spend some time reading up on/studying category theory and I can say, without a doubt or hesitation that if your goal is to either 1) understand Haskell better and/or 2) become better at writing Haskell, then studying category is a MAJOR waste of your time. I would advise you to spend that time instead on reading up on the lambda calculus, type theory, and some basic algebra (like this post). Haskell is not/has never been based on category theory (and I keep being baffled by how many people on social media will claim that it is, given how well documented it's origins are) and the common terminology of Functor/Monad that have been pilfered from CT via Wadler have only a passing resemblance/relation to their CT friends. Some things that I instead would recommend reading up on are: - Type theory (Benjamin Pierce's "Types and Programming Languages" is the de facto introduction to this. It covers everything from untyped lambda calculus to things way more complex than standard Haskell, including example implementations of type checker, etc.) - Computer assisted proofs/formal verification of programs (the Software Foundations book series, co-authored by Pierce are a good (and free!) intro: https://softwarefoundations.cis.upenn.edu/ https://softwarefoundations.cis.upenn.edu/) - The Spineless Tagless G-machine (if you are a more low level/C minded person, this talks about how we compile a lazy functiona language like Haskell to an Intel CPU: http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.3729 http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.37...) - The Typeclassopedia (which talks about how various CT inspired classes relate to each other and their laws: https://wiki.haskell.org/Typeclassopedia https://wiki.haskell.org/Typeclassopedia) EDIT: All of the above is not to say that you shouldn't learn category theory, but that you should have realistic reasons/expectations (even if that reason is just "I'm curious and it's cool"). I just hate seeing people get burned out trying to "get" category theory and (as a result) deciding Haskell must not be for them...
quickthrower2 7y ago
That is beautifully written and a nice recap on those things having studied maths a long long time ago. The Heything Algebra is quite interesting. I learned about that more recently on some lectures about logic and category theory online (I forgot the location now).
amelius 7y ago
I was wondering about something. If I have the sum x+x+x...+x (n times), then that is the same as x * n. If I have the product x * x * x ... * x (n times) then that is the same as x ^ n. What is it called when this is generalized? E.g. call + op1, call * op2, call ^ op3. What would op0 be? And what would op0.5 be? How does the unit element for these operations behave? And the rules for associativity, commutativity, for increasing order of the operation?
- sa1 7y ago
  It's called a hyperoperation: https://en.wikipedia.org/wiki/Hyperoperation https://en.wikipedia.org/wiki/Hyperoperation, and it's defined only for natural numbers, so op0.5 would still be undefined.
- n4r9 7y ago
  The generalisation that you're hinting at is known as Knuth's up-arrow notation [0]. There's a number known as Graham's number [1] which is defined in terms of up-arrow notation and was for a while the largest specific positive integer to have been used in a mathematical proof. [0] https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation [1] https://en.wikipedia.org/wiki/Graham%27s_number https://en.wikipedia.org/wiki/Graham%27s_number
- soVeryTired 7y ago
  The operation beyond exponentiation is known as tetration: towers of exponentials. It's not associative, and therefore it's difficult to work with and hasn't received much interest from the mathematical community at large. This might sound harsh, but unfortunately it does tend to attract 'cranks'. I think the reason for this is that there's a clear pattern (as you picked up on), that doesn't require formal mathematical training to spot. Amateurs get excited about the prospect of discovering something `new', without realising how hard it is to say anything deep about the topic.
mcphage 7y ago
I really like this, but one change I'd like to see: given how many structures are defined in terms of simpler structures (which are defined in terms of yet simpler ones), it would be nice if a structure listed all of the laws, not just the ones that simpler structures don't. That way, you would have to jump around the page to get a complete picture of a single structure. Maybe have them be a different color, so you can see what is new vs. what is inherited?
- joker3 7y ago
  It's somewhat confusing to see it this way the first time, but it's absolutely the right way to think about these structures. It's better to do the work to get used to it early on.
  - mcphage 7y ago
    It's the right way to think about the structures, sure. But when you want to look up the laws for what makes something a Ring, for instance, having them all in 1 place instead of having to jump between: Monoid, Semigroup, Group, Abelian Group, Quasiring, Nearring, and Ring. (And some of those laws occur twice, for different operators) makes it a lot more useful as a reference document.
    - BoiledCabbage 7y ago
      That's like saying when implementing a function you shouldn't call another fn, you should copy and paste its implementation so you don't have to flip to another location in the code. The right way is to learn what the function means so you can set see calls to it and know what it does.
      - mcphage 7y ago
        The purpose of the site is to be: > So, that’s the intent of this post – to be that fast reference to the kinds of algebraic structures I care about. I learned these structures in the early 90s; I don’t need to be told the right way to learn them. However, a “fast reference” would be useful.
7373737373 7y ago
A lambda-cube like visualization with the various properties (associativity etc.) as the axes could be helpful.

266 points by edgarvm 7y ago

Oh wow, this looks great. I had started working on my own FP glossary, but this has a ton of information and is clear enough that I'm sure many will find it very very helpful.

GrumpyNl 7y ago
It is very clearly written. Never really done algebra, but after this , it start to make sense.

nilkn 7y ago

> Rng I really think names without a fairly obvious way of saying them out-loud should just be avoided/deprecated. I can't pronounce this as "ring" (because then you'd think I was referring to a ring, not a rng). Do I just spell it out? R-N-G? I'd rather just call it a non-unital ring. That involves more letters but is much more descriptive (to a mathematician, anyway).

msclrhd 7y ago
I pronounce it /r@N/ -- i.e. like 'ring' but with the 'a' in comma, or the o in button. Although if it was a Rng formed by a pseudo-random sequence, then R-N-G would be apt ;).
- pvg 7y ago
  If you want to use them, HN will take most funny squiggles: \ˈrəŋ\. It draws the line at emojis.
Koshkin 7y ago
To be fair, the author has already made this point.
dramaqueen 7y ago
You pronounce it as "rung".
jaddood 7y ago
As mentioned, it should be pronounced "rung," but in any case, removing the i and suddenly making it a word and pronouncing it in a very unexpected way is really pretty stupid. I think, if one's really insisting on using "ring" but without the i, at least call it "rung" not "rng" so that its pronounciation is clear. If it's so important to have a "rng" instead of a "ring" then using its name in some example of its usage should probably be better.
- dramaqueen 7y ago
  Well, words, terms, notations and conventions come super cheap in math. You can call/denote "rng" anything you want. You just have to let your readers/interlocutors know about your conventions at the outset which is a standard practice in math anyway. For another thing, "r(u)ng" to me it's no different from writing "colonel" and reading it "kernel" (historical accident aside) :) There's also "lieutenant" which is pronounced " leftenant" in UK.
  - mangamadaiyan 7y ago
    Lieutenant is "Leftenant" in other parts of the world (those with a British connection, of course) as well.
mlevental 7y ago
it's a ring without (i)dentity. makes perfect sense to me. Besides this is a mathematical object not a programming thing - math has its own culture and conventions and pronunciation isn't a cultural value.
- dllthomas 7y ago
  At least, not pronunciation that's unambiguous whilst you're not also writing on a blackboard.
amatecha 7y ago
Yeh, she calls it out right in the definition: "If we may speak frankly, the rig and rng nomenclatures are abominations. Nevertheless, you may see them sometimes, but we will speak of them no more." :)
- nilkn 7y ago
  Sure, but I also wanted to suggest a simple descriptive name that sidesteps the problem.
lonelappde 7y ago
It's "ring without i". i is of course "identity", which is conventionally denoted e, because i is usually the square root of unity. This works pretty well if you pronounce i as in French so it's a homophonic with English e. Isn't math a wonderful language of use for computer programming? It's so international, breaking the hegemony of English.
JadeNB 7y ago
> I really think names without a fairly obvious way of saying them out-loud should just be avoided/deprecated. I can't pronounce this as "ring" (because then you'd think I was referring to a ring, not a rng). But 'nearring' doesn't bother you? If I'm at a talk on rngs where the distinction from rings is important, then I'll know that's the kind of talk that I'm attending, and hear accordingly; or else the speaker will make a huge deal of it (and then probably not use the word).

wsxcde 7y ago

Is there a good textbook that covers these? I am primarily interested in a computer science perspective to these algebraic structures.

earthicus 7y ago
Many of them feature prominently in Stepanov's books, Elements of Programming and From Mathematics to Generic Programming. 'Elements' is a technical monograph, while the other is a more lightweight read, halfway between semi-pop-science and a textbook. There's also an old textbook by Birkhoff & Bartee called 'Modern Applied Algebra' that i like. It's not super duper computer science-y but might be worth browsing through the table of contents at least. Edit: I snapped some photos of the table of contents since you can't see it on the amazon page: https://imgur.com/a/RFIf4CD https://imgur.com/a/RFIf4CD
gtycomb 7y ago
'Topics In Algebra' by I.N.Herstein. Back in college years this was my first book. Despite many other books (which might look easier) I always came back here because of the care it takes to walk through well crafted progression of concepts. (Not a 'computer science' book but you will need something like this for the Algebra part)
nandemo 7y ago
My favourite abstract algebra textbook is Fraleigh's A First Course in Abstract Algebra. Unlike the article here, which just dumps you a bunch of definitions, the book introduces each structure with proper motivation. It's not a CS approach though. https://www.amazon.com/First-Course-Abstract-Algebra-7th/dp/0201763907 https://www.amazon.com/First-Course-Abstract-Algebra-7th/dp/... (the 1-star reviews apply to the Kindle version, not the contents. Just get the paperback and you'll be fine) If you want a CS approach I suggest learning basic Haskell then tackling the fantastic Typeclassopedia. The downside is you'll be missing on structures/theorems that are super useful in math but not that useful in programming. https://wiki.haskell.org/Typeclassopedia https://wiki.haskell.org/Typeclassopedia
- commandlinefan 7y ago

SAI_Peregrinus 7y ago

The Wikipedia page on Algebraic structures is rather more detail than I usually want, but the page "Outline of algebraic structures"[1] is a great quick reference. [1] https://en.wikipedia.org/wiki/Outline_of_algebraic_structures https://en.wikipedia.org/wiki/Outline_of_algebraic_structure...

_hardwaregeek 7y ago

Interesting seeing this defined from a functional programming/category theory perspective. Personally I like examples for my algebraic structures along with some simple proofs why they're that structure. What was extremely useful for my Algebra class was a Wikipedia note detailing the hierarchy of rings via set inclusion: commutative rings ⊃ integral domains ⊃ integrally closed domains ⊃ GCD domains ⊃ unique factorization domains ⊃ principal ideal domains ⊃ Euclidean domains ⊃ fields ⊃ finite fields Found here: https://en.wikipedia.org/wiki/Integral_domain https://en.wikipedia.org/wiki/Integral_domain

crimsonalucard 7y ago

I'm learning category theory to understand haskell better. I'm finding category theory to be almost a theory about program structure in the context of composition. It's giving me a whole new perspective on one of the least concrete things about programming namely design. How relevant is abstract algebra to programming? Will it change my perspective on everything related to programming? How much of a mind bender is it compared to category theory?

hamdshah 7y ago
Any references you would like to share ?
- louthy 7y ago
  Not the OP, but this is a great book to get started: https://github.com/hmemcpy/milewski-ctfp-pdf https://github.com/hmemcpy/milewski-ctfp-pdf
merijnv 7y ago
> I'm learning category theory to understand haskell better. I would consider myself a fairly expert Haskell programmer and I have (for fun/curiousity) spend some time reading up on/studying category theory and I can say, without a doubt or hesitation that if your goal is to either 1) understand Haskell better and/or 2) become better at writing Haskell, then studying category is a MAJOR waste of your time. I would advise you to spend that time instead on reading up on the lambda calculus, type theory, and some basic algebra (like this post). Haskell is not/has never been based on category theory (and I keep being baffled by how many people on social media will claim that it is, given how well documented it's origins are) and the common terminology of Functor/Monad that have been pilfered from CT via Wadler have only a passing resemblance/relation to their CT friends. Some things that I instead would recommend reading up on are: - Type theory (Benjamin Pierce's "Types and Programming Languages" is the de facto introduction to this. It covers everything from untyped lambda calculus to things way more complex than standard Haskell, including example implementations of type checker, etc.) - Computer assisted proofs/formal verification of programs (the Software Foundations book series, co-authored by Pierce are a good (and free!) intro: https://softwarefoundations.cis.upenn.edu/ https://softwarefoundations.cis.upenn.edu/) - The Spineless Tagless G-machine (if you are a more low level/C minded person, this talks about how we compile a lazy functiona language like Haskell to an Intel CPU: http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.3729 http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.37...) - The Typeclassopedia (which talks about how various CT inspired classes relate to each other and their laws: https://wiki.haskell.org/Typeclassopedia https://wiki.haskell.org/Typeclassopedia) EDIT: All of the above is not to say that you shouldn't learn category theory, but that you should have realistic reasons/expectations (even if that reason is just "I'm curious and it's cool"). I just hate seeing people get burned out trying to "get" category theory and (as a result) deciding Haskell must not be for them...

quickthrower2 7y ago

That is beautifully written and a nice recap on those things having studied maths a long long time ago. The Heything Algebra is quite interesting. I learned about that more recently on some lectures about logic and category theory online (I forgot the location now).

amelius 7y ago

I was wondering about something. If I have the sum x+x+x...+x (n times), then that is the same as x * n. If I have the product x * x * x ... * x (n times) then that is the same as x ^ n. What is it called when this is generalized? E.g. call + op1, call * op2, call ^ op3. What would op0 be? And what would op0.5 be? How does the unit element for these operations behave? And the rules for associativity, commutativity, for increasing order of the operation?

sa1 7y ago
It's called a hyperoperation: https://en.wikipedia.org/wiki/Hyperoperation https://en.wikipedia.org/wiki/Hyperoperation, and it's defined only for natural numbers, so op0.5 would still be undefined.
n4r9 7y ago
The generalisation that you're hinting at is known as Knuth's up-arrow notation [0]. There's a number known as Graham's number [1] which is defined in terms of up-arrow notation and was for a while the largest specific positive integer to have been used in a mathematical proof. [0] https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation [1] https://en.wikipedia.org/wiki/Graham%27s_number https://en.wikipedia.org/wiki/Graham%27s_number
soVeryTired 7y ago
The operation beyond exponentiation is known as tetration: towers of exponentials. It's not associative, and therefore it's difficult to work with and hasn't received much interest from the mathematical community at large. This might sound harsh, but unfortunately it does tend to attract 'cranks'. I think the reason for this is that there's a clear pattern (as you picked up on), that doesn't require formal mathematical training to spot. Amateurs get excited about the prospect of discovering something `new', without realising how hard it is to say anything deep about the topic.

mcphage 7y ago

I really like this, but one change I'd like to see: given how many structures are defined in terms of simpler structures (which are defined in terms of yet simpler ones), it would be nice if a structure listed all of the laws, not just the ones that simpler structures don't. That way, you would have to jump around the page to get a complete picture of a single structure. Maybe have them be a different color, so you can see what is new vs. what is inherited?

joker3 7y ago
It's somewhat confusing to see it this way the first time, but it's absolutely the right way to think about these structures. It's better to do the work to get used to it early on.
- mcphage 7y ago
  It's the right way to think about the structures, sure. But when you want to look up the laws for what makes something a Ring, for instance, having them all in 1 place instead of having to jump between: Monoid, Semigroup, Group, Abelian Group, Quasiring, Nearring, and Ring. (And some of those laws occur twice, for different operators) makes it a lot more useful as a reference document.
  - BoiledCabbage 7y ago
    That's like saying when implementing a function you shouldn't call another fn, you should copy and paste its implementation so you don't have to flip to another location in the code. The right way is to learn what the function means so you can set see calls to it and know what it does.
    - mcphage 7y ago
      The purpose of the site is to be: > So, that’s the intent of this post – to be that fast reference to the kinds of algebraic structures I care about. I learned these structures in the early 90s; I don’t need to be told the right way to learn them. However, a “fast reference” would be useful.

7373737373 7y ago

A lambda-cube like visualization with the various properties (associativity etc.) as the axes could be helpful.