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

Question

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

Milstone

This is not exactly what you're looking for, but the article The Typeclassopedia in issue 13 of The Monad.Reader might still be of interest: It's a detailed explanation of several type classes (Functor, Applicative, Monoid, Monad, Arrow, etc.) from the Haskell Prelude. – Injunction

Answer 1

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 S₃* ⨯ 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.

Commissar

Answer 2

Haskell's Arrows are a generalisation of monads and probably are relevant.

Earphone

Answer 3

I'd recommend Edward Kmett's very readable blog and related category extras package. Should keep you busy for years.

Atahualpa