Estructura y programación algebraica

Question

¿Alguien me puede dar un ejemplo de cómo podemos mejorar la reutilización de nuestros códigos utilizando estructuras algebraicas como grupos, monoides y anillos? (o cómo puedo utilizar este tipo de estructuras en la programación, sabiendo al menos que no aprendí toda esa teoría en el instituto por nada).

Escuché que esto es posible, pero no puedo encontrar una manera de aplicarlos en la programación y aplicar genéricamente las matemáticas difíciles en la programación.

Answer 1

No es realmente el material matemático lo que ayuda como es el pensamiento matemático. La abstracción es la clave en la programación. Transformar conceptos reales en números y relaciones es lo que hacemos todos los días. El álgebra es la madre de todos, el álgebra es el conjunto de reglas que define la corrección, es el nivel más alto de abstracción, por lo tanto, comprender el álgebra significa que puedes pensar más claro, más rápido, más eficiente. Comenzando desde la teoría de conjuntos hasta la teoría de categorías, la teoría de dominios, etc., todo proviene de desafíos prácticos, abstracción y requisitos de generalización. En la práctica común no será necesario que los conozca realmente, aunque si está pensando en desarrollar elementos como los Agentes de IA, los lenguajes de programación, los conceptos fundamentales y las herramientas, entonces son obligatorios.

Answer 2

Como no tenía idea de esto existía en el mundo de la informática, no tenga en cuenta esta respuesta;)

---

no creo que los dos campos (sin doble sentido) tener ningún solapamiento. Los anillos/campos/grupos se ocupan de objetos matemáticos. Considere una parte de la definición de un campo:

Por cada a en F, existe un elemento -a en F, tal que a + (-a) = 0. De manera similar, para cualquier a en F otro que 0, existe un elemento a^-1 en F, tal que a · a^-1 = 1. (Los elementos a + (-b) y a · b^-1 también se denotan a - b y a/b, respectivamente.) En otras palabras, existen operaciones de resta y división.

¿Qué significa esto en términos de programación? Seguramente no puedo tener un inverso aditivo de un objeto list en Python (bueno, podría destruir el objeto, pero eso es como el multiplicativo inverso. Creo que podrías llegar a algún lado tratando de definir un anillo de Python, pero simplemente no funcionará al final). ni siquiera piensan de dividir lists ...

En cuanto a la legibilidad del código, no tengo la menor idea de cómo esto se puede aplicar incluso, por lo que esta aplicación es irrelevante.

Esta es mi interpretación, pero ser estudiante de matemáticas probablemente me haga cegar a otra terminología de diferentes campos (ya sabes de cuál me refiero).

Answer 3

En la programación funcional, esp. Haskell, es común estructurar programas que transforman estados como mónadas. Hacerlo significa que puede reutilizar algoritmos genéricos en mónadas en programas muy diferentes.

La biblioteca de plantillas estándar de C++ presenta el concepto de monoid. La idea es nuevamente que los algoritmos genéricos pueden requerir una operación que satisfaga los axiomas de los monoides para su corrección.

P. ej., Si podemos probar el tipo T en el que estamos trabajando (números, cadenas, lo que sea) que se cierra con la operación, sabemos que no tendremos que verificar ciertos errores; siempre obtenemos un válido atrás. Si podemos probar que la operación es asociativa (x * (y * z) = (x * y) * z), podemos reutilizar la arquitectura fork-join; una forma simple pero a la vez de programación paralela implementada en varias bibliotecas.

Answer 4

La ciencia de la informática parece obtener una gran cantidad de kilometraje de category theory en estos días. Obtiene mónadas, monoides, funtores: un bestiario completo de entidades matemáticas que se utilizan para mejorar la reutilización del código, aprovechando la abstracción de las matemáticas abstractas.

Answer 5

Las listas son monoides libres con un generador, los binarios son grupos. Tienes la variante finita o infinita.

puntos de partida:

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

Es posible que desee aprender la teoría de categorías, y la teoría de las categorías manera se aproxima a las estructuras algebraicas: es exactamente la forma los lenguajes de programación funcionales se aproximan a las estructuras de datos, al menos en forma.

Ejemplo: el tipo de árbol A es

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

redactada en la existencia de un isomorfismo (*) (I puse G = Tree A)

1 + G + G x G -> G 

que es la misma que una estructura de grupo

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

de hecho, los árboles binarios pueden representar expresiones y formar una estructura algebraica ure. Un elemento de G se lee como la identidad, un inverso de un elemento o el producto de dos elementos. Un árbol binario es una hoja, un árbol o un par de árboles. Tenga en cuenta la similitud en la forma.

(*), así como una propiedad universal, pero son dos de ellos (árboles finitos o árboles perezosos infinitos) así que no voy a profundizar en los detalles.

Answer 6

Los monoides son omnipresentes en la programación. En algunos lenguajes de programación, ej. Haskell, podemos hacer que los monoides sean explícitos http://blog.sigfpe.com/2009/01/haskell-monoids-and-their-uses.html