In mathematics, an action of a semigroup on a set is an operation that associates each element of the semigroup is with a transformation on the set. See Wikipedia articles on semigroup action and group action.
This package complements and depends on semigroups.
Similarly to semigroups, semigroup (or monoid) actions arise almost everywhere (if you look for them).
Natural numbers acting on monoids
The multiplication monoid of natural numbers acts on any other monoid:
n `act` x = x <> ... <> x -- x appears n-times
0 `act` x == mempty,
3 `act` x == x <> x <> x etc.
<> is associative, such an action can be computed very efficiently
with only O(log n) operations using
This is expressed by
newtype Repeat and instance
instance (Monoid w, Whole n) => SemigroupAct (Product n) (Repeat w) where
Many different concepts can be expressed using such an action, including
repeating a list
compose a function
n-times, commonly denoted as fⁿ in mathematics:
(Repeat (Endo fⁿ)) = (Product n) `act` (Repeat (Endo f))
Any semigroup (or monoid) can be viewed as acting on itself. In this case,
act simply becomes
<>. This is expressed by the
newtype SelfAct a = SelfAct a instance Semigroup g => Semigroup (SelfAct g) where (SelfAct x) <> (SelfAct y) = SelfAct $ x <> y
Matrices acting on vectors
Matrices with multiplication can be viewed as a group acting on vectors.
Copyright 2012, Petr Pudlák
Contact: petr.pudlak.name or through github.