A Brief Guide to a Few Algebraic Structures • Hacker News Board

Re: A Brief Guide to a Few Algebraic Structures

#21

Post by jvvw » Thu, Aug 01, 2019, 9:24 AM UTC

wsxcde wrote: post #13

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

Just as a warning most maths algebra beginner textbooks will focus on groups, rings and fields and not talk about most of the other structures mentioned (including Fragleigh and Herstein recommended by others - they are incredibly different styles, and although I have extremely fond memories of Herstein, there are better books than those two especially if you aren't actually doing a maths degree, but my knowledge of textbooks is 20 years out of date). On the other hand once you have a good grasp of a few structures, learning about and understanding others becomes much easier. I guess it all depends on why you want to learn about them and what you want to do with them

Re: A Brief Guide to a Few Algebraic Structures

#22

Post by crimsonalucard » Thu, Aug 01, 2019, 9:34 AM UTC

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?

Re: A Brief Guide to a Few Algebraic Structures

#23

Post by hamdshah » Thu, Aug 01, 2019, 9:47 AM UTC

crimsonalucard wrote: post #22

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…

Any references you would like to share ?

Re: A Brief Guide to a Few Algebraic Structures

#24

Post by quickthrower2 » Thu, Aug 01, 2019, 10:23 AM UTC

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).

Re: A Brief Guide to a Few Algebraic Structures

#25

Post by amelius » Thu, Aug 01, 2019, 10:57 AM UTC

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?

Re: A Brief Guide to a Few Algebraic Structures

#26

Post by sa1 » Thu, Aug 01, 2019, 10:59 AM UTC

amelius wrote: post #25

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, f…

It's called a hyperoperation: https://en.wikipedia.org/wiki/Hyperoperation, and it's defined only for natural numbers, so op0.5 would still be undefined.

Re: A Brief Guide to a Few Algebraic Structures

#27

Post by n4r9 » Thu, Aug 01, 2019, 11:00 AM UTC

amelius wrote: post #25

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, f…

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

[1] https://en.wikipedia.org/wiki/Graham%27s_number

Re: A Brief Guide to a Few Algebraic Structures

#28

Post by hackernews7899 » Thu, Aug 01, 2019, 11:01 AM UTC

wsxcde wrote: post #13

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

Check out “Seven Sketches in Compositionality“ by Spivak and Fong. You can find a free copy provided by the authors online. It is an introductory book to applied category theory.

Re: A Brief Guide to a Few Algebraic Structures

#29

Post by soVeryTired » Thu, Aug 01, 2019, 11:20 AM UTC

amelius wrote: post #25

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, f…

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.

Re: A Brief Guide to a Few Algebraic Structures

#30

Post by merijnv » Thu, Aug 01, 2019, 11:20 AM UTC

crimsonalucard wrote: post #22

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…

> 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/) - 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.37...) - The Typeclassopedia (which talks about how various CT inspired classes relate to each other and their laws: 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...