Convolution (computer science)

Example

Given the three words and, fish and be where |and| is 3, |fish| is 4 and |be| is 2. Let ℓ denote the longest word which is fish; ℓ = 4 . The convolution of and, fish, be is then 4 tuples of elements:

where # is a symbol not in the original alphabet. In Haskell this truncates to shortest sequence ℓ _ , where ℓ _ = 2 :

Definition

Let Σ be an alphabet, # a symbol not in Σ.

Let x₁x₂... x_|x|, y₁y₂... y_|y|, z₁z₂... z_|z|, ... be n words (i.e. finite sequences) of elements of Σ. Let ℓ denote the length of the longest word, i.e. the maximum of |x|, |y|, |z|, ... .

The convolution of these words is a finite sequence of n-tuples of elements of (Σ ∪ {#}), i.e. an element of ( ( Σ ∪ { # } ) n ) ∗ :

where for any index i > |w|, the w_i is #.

The convolution of x, y, z, ... is denoted conv( x, y, z, ...), zip( x, y, z, ...) or x ⋆ y ⋆ z ⋆ ...

The inverse to convolution is sometimes denoted unzip.

A variation of the convolution operation is defined by:

where ℓ _ is the minimum length of the input words. It avoids the use of an adjoined element # , but destroys information about elements of the input sequences beyond ℓ _ .

In programming languages

Convolution functions are often available in programming languages, often referred to as zip. In Lisp-dialects one can simply map the desired function over the desired lists, map is variadic in Lisp so it can take an arbitrary amount of lists as argument. An example from Clojure:

In Common Lisp:

Languages such as Python provide a zip() function, older version (Python 2.*) allowed mapping None over lists to get a similar effect. zip() in conjunction with the * operator unzips a list:

Haskell has a method of convolving sequences but requires a specific function for each arity (zip for two sequences, zip3 for three etc.), similarly the functions unzip and unzip3 are available for unzipping:

Language comparison

List of languages by support of convolution: