language-agnostic - resueltos - grupo algebra
Ejemplos de monoides/semigrupos en programación. (4)
Es bien sabido que los monoides son increíblemente ubicuos en la programación. Son tan omnipresentes y tan útiles que yo, como ''proyecto de pasatiempo'', estoy trabajando en un sistema que está completamente basado en sus propiedades (agregación de datos distribuidos). Para hacer el sistema útil necesito monoides útiles :)
Ya sé de estos:
- Suma numérica o matricial
- Producto numérico o matricial.
- Mínimo o máximo en un orden total con un elemento superior o inferior (más generalmente, unirse o reunirse en una red acotada, o incluso más generalmente, producto o coproducto en una categoría)
- Establecer union
- Unión de mapas donde se unen valores en conflicto usando un monoide
- Intersección de subconjuntos de un conjunto finito (o simplemente establecer intersección si hablamos de semigrupos)
- Intersección de mapas con un dominio clave acotado (igual aquí)
- Fusión de secuencias ordenadas, tal vez con la unión de valores igual a clave en un monoide / semigroup diferente
- Fusión acotada de listas ordenadas (igual que arriba, pero tomamos la N superior del resultado)
- Producto cartesiano de dos monoides o semigrupos.
- Lista de concatenación
- Endomorfismo de la composición.
Ahora, definamos una cuasi propiedad de una operación como una propiedad que mantiene una relación de equivalencia. Por ejemplo, la concatenación de listas es casi conmutativa si consideramos que las listas de igual longitud o con contenido idéntico hasta la permutación son equivalentes.
Aquí hay algunos cuasimonoides y cuasi mono conmutativos y semigrupos:
- Cualquiera (a + b = a o b, si consideramos que todos los elementos del conjunto de portadores son equivalentes)
- Cualquier predicado satisfactorio (a + b = el de a y b que no es nulo y satisface algún predicado P, si ninguno lo hace, entonces es nulo; si consideramos que todos los elementos satisfacen P equivalente)
- Mezcla limitada de muestras aleatorias (xs + ys = una muestra aleatoria de tamaño N de la concatenación de xs y ys; si consideramos que cualquiera de las dos muestras con la misma distribución que el conjunto de datos completo es equivalente)
- Mezcla acotada de muestras aleatorias ponderadas
- Llamémoslo "fusión topológica": dados dos gráficos de dependencia acíclicos y no contradictorios, un gráfico que contiene todas las dependencias especificadas en ambos. Por ejemplo, la lista "concatenación" que puede producir cualquier permutación en la cual los elementos de cada lista siguen en orden (por ejemplo, 123 + 456 = 142356).
¿Qué otros existen?
Cálculo del valor del número romano de longitud arbitraria. https://gist.github.com/4542999
La biblioteca estándar de Haskell es elogiada y atacada alternativamente por su uso de los términos matemáticos reales para sus clases de tipo. (En mi opinión, es algo bueno, ya que sin él, ¡nunca sabría lo que es un monoide!). En cualquier caso, puede consultar http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Monoid.html para ver algunos ejemplos más:
- el dual de cualquier monoide es un monoide: dado a + b, define una nueva operación ++ con a ++ b = b + a
- conjunción y disyunción de booleanos
- sobre la mónada Maybe (también conocida como "opción" en Ocaml), primera y última. Es decir,
first (Just a) b = Just a first Nothing b = b y lo mismo para el final
Este último es solo la punta del iceberg de toda una familia de monoides relacionados con mónadas y flechas, pero realmente no puedo envolver mi cabeza alrededor de estos (aparte de los endomorfismos simplemente monádicos). Pero una búsqueda de google en monads monoids aparece bastante.
Un ejemplo realmente útil de un monoide conmutativo es la unificación en lenguajes lógicos y de restricción. Consulte la sección 2.8.2.2 de ''Conceptos, técnicas y modelos de programación de computadoras'' para obtener una definición precisa de un posible algoritmo de unificación.
Buena suerte con tu idioma! Estoy haciendo algo similar con un lenguaje paralelo, utilizando monoides para combinar subresultados de cálculos paralelos.
El monoide cociente es otra forma de formar monoides (¿cuasimonoides?): Dado el monoide M y una relación de equivalencia compatible con la multiplicación, proporciona otro monoide. Por ejemplo:
Multisets finitos con unión : si A * es un monoide libre (listas con concatenación), ~ es "una permutación de" relación, entonces A * / ~ es un monoide conmutativo libre.
conjuntos finitos con unión : Si ~ se modifica para ignorar el recuento de elementos (por lo tanto, "aa" ~ "a"), entonces A * / ~ es un monoide idempotente conmutativo libre.
monoide sintáctico : cualquier lenguaje regular da lugar a un monoide sintáctico que es cociente de A * por la relación de "indistinguibilidad por idioma". Here hay una implementación del árbol de dedos de esta idea. Por ejemplo, el lenguaje {a 3n : n natural} tiene Z 3 como el monoide sintáctico.
Los monoides de cociente vienen automáticamente con homomorfismo M -> M / ~ que es sobreyectivo.
Una construcción "dual" son las submonoides. Vienen con homomorfismo A -> M que es inyectivo.
Otra construcción más sobre los monoides es el producto tensorial .
Los monoides permiten la exponencia al cuadrar en O (log n) y el cálculo rápido de sumas de prefijos en paralelo. También se utilizan en la mónada del escritor .