functional-programmingalgebraic-data-typesfortressabstract-algebra

Is there any algebraic structures used in functional programming other then monoid?


I recently getting to know about functional programming (in Haskell and Scala). It's capabilities and elegance is quite charming.

But when I met Monads, which makes use of an algebraic structure named Monoid, I was surprised and glad to see the theoretic knowledge I have been learning from Mathematics is made use of in programming.

This observation brought a question into my mind: Can Groups, Fields or Rings (see Algebraic Structures for others) be used in programming for more abstraction and code reuse purposes and achieving mathematic-alike programming?

As I know, the language named Fortress (which I would surely prefer over any language once when its compiler is completed) defines these structure in its library code. But only uses I saw so far was for numeric types, which we already familiar with. Could there be any other uses of them?

Best regards, ciun


Solution

  • You can model many structures. Here's a group:

    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)
    

    Now, you can write mult (Dual CAB, 5) (Dual CBA, 1) and get a result. This will be a computation in group S3* ⨯ Z. You can add other groups, combine them in any possible way and do computations with them.

    Similar things can be done with rings, fields, orderings, vector spaces, categories etc. Haskell's numeric hierarchy is unfortunately badly modeled, but there's numeric prelude that attempts to fix that. Also there's DoCon that takes it to extreme. For a tour of type classes (mainly motivated by category theory), there's Typeclassopedia which has a large list of examples and applications.