Esistono strutture algebriche utilizzate nella programmazione funzionale diverse da quelle monoide?

Question

Recentemente ho iniziato a conoscere la programmazione funzionale (in Haskell e Scala). Le sue capacità e l'eleganza sono piuttosto affascinanti.

Ma quando ho incontrato Monads, che utilizza una struttura algebrica di nome Monoid, sono stato sorpreso e felice di vedere che la conoscenza teorica che ho imparato dalla matematica è stata utilizzata nella programmazione.

Questa osservazione mi ha posto una domanda: i gruppi, i campi o gli anelli (vedi Algebraic Structures per altri) possono essere utilizzati in programmazione per ulteriori scopi di astrazione e riutilizzo del codice e per ottenere una programmazione simile allo stesso matematico?

Come noto, la lingua denominata Fortress (che preferirei sicuramente in qualsiasi lingua una volta al completamento del compilatore) definisce questa struttura nel codice della libreria. Ma solo gli usi che ho visto finora erano per i tipi numerici, che abbiamo già familiarità con. Potrebbero esserci altri usi di loro?

Con i migliori saluti, CIUN

Answer 1

È possibile modellare molte strutture. Ecco un gruppo:

class Group a where 
    mult :: a -> a -> a 
    identity :: a 
    inverse :: a -> a 

instance Group Integer where 
    mult = (+) 
    identity = 0 
    inverse = negate 

-- S_3 (group of all bijections of a 3-element set) 
data S3 = ABC | ACB | BAC | BCA | CAB | CBA 
instance Group S3 where 
    mult ABC x = x 
    ... -- some boring code 
    identity = ABC 
    inverse ABC = ABC 
    ... -- remaining cases 

-- Operations on groups. Dual: 
data Dual a = Dual { getDual :: a } 
instance Group a => Group (Dual a) where 
    mult (Dual x) (Dual y) = Dual (mult y x) 
    identity = Dual identity 
    inverse (Dual x) = Dual (inverse x) 

-- Product: 
instance (Group a, Group b) => Group (a,b) where 
    mult (x,y) (z,t) = (x `mult` z, y `mult` t) 
    identity = (identity, identity) 
    inverse (x,y) = (inverse x, inverse y) 

Ora, è possibile scrivere mult (Dual CAB, 5) (Dual CBA, 1) e ottenere un risultato. Questo sarà un calcolo nel gruppo S * ⨯ Z. È possibile aggiungere altri gruppi, combinarli in qualsiasi modo possibile e fare calcoli con essi.

Le cose simili possono essere fatte con anelli, campi, ordinamenti, spazi vettoriali, categorie ecc. La gerarchia numerica di Haskell è sfortunatamente modellata male, ma c'è il numeric prelude che tenta di risolverlo. Inoltre c'è DoCon che lo porta all'estremo. Per un tour di classi di tipi (principalmente motivati ​​dalla teoria delle categorie), c'è lo Typeclassopedia che ha un ampio elenco di esempi e applicazioni.

Answer 2

di Haskell Arrows sono una generalizzazione di monadi e, probabilmente, sono rilevanti.

Answer 3

Suggerirei il molto leggibile blog di Edward Kmett e il relativo pacchetto category extras. Dovresti tenerti occupato per anni.