Algebraic structure and programming

Question

Can someone give me an example of how we can improve code reuse using algebraic structures like groups, monoids and rings? (or how can I use these structures in programming, knowing at least that I did not study all this theory at school for nothing).

I heard that this is possible, but I can’t understand how to use them in programming and genetically apply hardcore math in programming.

Answer 1

In fact, this is not mathematical material that helps, like mathematical thinking. Abstraction is the key to programming. Transforming real living concepts into numbers and relationships is what we do every day. Algebra is the mother of all, algebra is a set of rules that determine correctness, it is the highest level of abstraction, so understanding algebra means that you can think more clearly, faster and more efficiently. Starting with set theory, category theory, domain theory, etc. Everything comes from practical tasks, the requirements of abstraction and generalization. In normal practice, you will not need to know this, although if you are thinking about developing things like AI Agents, programming languages, fundamental concepts and tools, then they are necessary.

Answer 2

As I did not suspect that this material exists in the world of computer science, please do not pay attention to it;)

---

I do not think that the two fields (no pun intended) have any coincidence. Rings / fields / groups belong to mathematical objects. Consider the field definition part:

For every a from F there exists an element -a in F such that a + (-a) = 0. Similarly, for any a from F other than 0, there is an element a ^ -1 in F, so a · a ^ -1 = 1. (Elements a + (-b) and a · b ^ -1 are also denoted by a - b and a / b, respectively.) In other words, subtraction and division operations exist.

What does this mean in terms of programming? I probably can't have the additive inverse of the list object in Python (well, I could just destroy the object, but it seems like a multiplicative inverse. I think you could try to define a Python ring somewhere, but that just won't work at the end ) Don't even think about splitting lists ...

As for the readability of the code, I absolutely do not know how this can be applied, so this application does not matter.

This is my interpretation, but, being a mathematician, it probably makes me blind to different terminology from different areas (you know who I'm talking about).

Answer 3

In functional programming, especially. Haskell, it is common for structural programs that transform states like monads. This means that you can reuse common monad algorithms in very different programs.

The standard C ++ template library contains the concept of monoid . The idea again is that for generic algorithms, an operation may be required to satisfy the axioms of monoids for their correctness.

For example, if we can prove that the type T on which we work (numbers, a string, whatever) is closed during an operation, we know that we will not need to check for certain errors; we always get a valid T back. If we can prove that the operation is associative (x * (y * z) = (x * y) * z) , then we can reuse the fork-join architecture; simple but parallel programming method implemented in various libraries.

Answer 4

Today, computer science seems to be getting a lot of money from category theory . You get monads, monoids, functors - a whole bestiary of mathematical objects that are used to improve code reuse, using abstract mathematics abstraction.

Answer 5

Lists are free monoids with one generator, binary trees are groups. You have either a finite or an endless option.

Starting points:

• http://en.wikipedia.org/wiki/Algebraic_data_type
• http://en.wikipedia.org/wiki/Initial_algebra
• http://en.wikipedia.org/wiki/F-algebra

You might want to study category theory, as well as how category theory approaches algebraic structures: that is how functional programming languages ​​approach data structures, at least in form.

Example: tree tree A

 Tree A = () | Tree A | Tree A * Tree A 

which reads as the existence of an isomorphism (*) (I) G = Tree A )

 1 + G + G x G -> G 

which coincides with the group structure

 phi : 1 + G + G x G -> G () € 1 -> e x € G -> x^(-1) (x, y) € G x G -> x * y 

Indeed, binary trees can represent expressions and form an algebraic structure. The element G is read either as an identity, or the inverse of the element, or the product of two elements. A binary tree is either a leaf, or a single tree, or a pair of trees. Note the similarities in form.

(*), as well as a universal property, but they are two of them (finite trees or infinite lazy trees), so I will not describe the details in detail.

Answer 6

Monoids are ubiquitous in programming. In some programming languages, for example. Haskell, we can make monoids explicit http://blog.sigfpe.com/2009/01/haskell-monoids-and-their-uses.html