Existe-t-il des structures algébriques utilisées dans la programmation fonctionnelle autre que monoid?

Question

J'ai récemment appris à connaître la programmation fonctionnelle (dans Haskell et Scala). C'est capacités et élégance est assez charmant. Mais quand j'ai rencontré Monades, qui utilise une structure algébrique appelée Monoid, j'ai été surpris et heureux de voir que les connaissances théoriques que j'ai apprises à partir des mathématiques sont utilisées dans la programmation. Cette observation m'a amené à me poser une question: Est-ce que les groupes, champs ou anneaux (voir Algebraic Structures pour d'autres) peuvent être utilisés dans la programmation pour plus d'abstraction et de réutilisation de code et pour la programmation mathématique? Comme je sais, le langage nommé Fortress (que je préférerais sûrement sur n'importe quelle langue une fois que son compilateur est terminé) définit ces structures dans son code de bibliothèque. Mais seules les utilisations que j'ai vues jusqu'ici étaient pour les types numériques, que nous connaissons déjà. Pourrait-il y avoir d'autres utilisations d'eux?

Meilleures salutations, ciun

Answer 1

Vous pouvez modéliser de nombreuses structures. Voici un groupe:

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) 

Maintenant, vous pouvez écrire mult (Dual CAB, 5) (Dual CBA, 1) et obtenir un résultat. Ce sera un calcul dans le groupe S * ⨯ Z. Vous pouvez ajouter d'autres groupes, les combiner de toutes les manières possibles et faire des calculs avec eux.

Des choses similaires peuvent être faites avec des anneaux, des champs, des ordres, des espaces vectoriels, des catégories, etc. La hiérarchie numérique de Haskell est malheureusement mal modélisée, mais il y a numeric prelude qui tente de résoudre ce problème. En outre, il y a DoCon qui le prend à l'extrême. Pour un tour des classes de type (principalement motivé par la théorie des catégories), il y a Typeclassopedia qui a une grande liste d'exemples et d'applications.

Answer 2

Arrows Haskell sont une généralisation des monades et sont probablement pertinents.

Answer 3

Je recommanderais très lisible blog d'Edward Kmett et connexes category extras paquet. Devrait vous tenir occupé pendant des années.