  Convolution is a broadly useful operation with applications including signal
processing, machine learning, probability, optics, polynomial multiplication,
and efficient parsing. Usually, however, this operation is understood and
implemented in more specialized forms, hiding commonalities and limiting
usefulness. This paper formulates convolution in the common algebraic framework
of semirings and semimodules and populates that framework with various
representation types. One of those types is the grand abstract template and
itself generalizes to the free semimodule monad. Other representations serve
varied uses and performance trade-offs, with implementations calculated from
simple and regular specifications.
  Of particular interest is Brzozowski's method for regular expression
matching. Uncovering the method's essence frees it from syntactic
manipulations, while generalizing from boolean to weighted membership (such as
multisets and probability distributions) and from sets to n-ary relations. The
classic trie data structure then provides an elegant and efficient alternative
to syntax.
  Pleasantly, polynomial arithmetic requires no additional implementation
effort, works correctly with a variety of representations, and handles
multivariate polynomials and power series with ease. Image convolution also
falls out as a special case.
