Convolution (computer science)

In computer science, specifically formal languages, convolution (sometimes referred to as zip) is a function which maps a tuple of sequences into a sequence of tuples.

Example

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

(a,f,b)(n,i,e)(d,s,\#)(\#,h,\#)

where # is a symbol not in the original alphabet. In Haskell this truncates to shortest sequence $\underline {\ell }$ , where $\underline {\ell }=2$ :

zip3 "and" "fish" "be"
-- [('a','f','b'),('n','i','e')]

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 $\ell$ 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 $((\Sigma \cup \{\#\})^{n})^{*}$ :

(x_{1},y_{1},\ldots )(x_{2},y_{2},\ldots )\ldots (x_{\ell },y_{\ell },\ldots )

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:

(x_{1},y_{1},\ldots )(x_{2},y_{2},\ldots )\ldots (x_{{\underline {\ell }}},y_{{\underline {\ell }}},\ldots )

where $\underline {\ell }$ 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 $\underline {\ell }$ .

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:^[1]

;; `nums' contains an infinite list of numbers (0 1 2 3 ...)
(def nums (range))
(def tens [10 20 30])
(def firstname "Alice")

;; To convolve (0 1 2 3 ...) and [10 20 30] into a vector, invoke `map vector' on them; same with list
(map vector nums tens)           ; ⇒ ([1 10] [2 20] [3 30])
(map list nums tens)             ; ⇒ ((1 10) (2 20) (3 30))
(map str nums tens)              ; ⇒ ("110" "220" "330")

;; `map' truncates to the shortest sequence; note missing \c and \e from "Alice"
(map vector nums tens firstname) ; ⇒ ([1 10 \A] [2 20 \l] [3 30 \i])
(map str nums tens firstname)    ; ⇒ ("110A" "220l" "330i")

;; To unzip, apply `map vector' or `map list'
(apply map list (map vector nums tens firstname))
;; ⇒ ((0 1 2) (10 20 30) (\A \l \i))

In Common Lisp:

(defparameter nums '(1 2 3))
(defparameter tens '(10 20 30))
(defparameter firstname "Alice")

(mapcar #'list nums tens)
;; ⇒ ((1 10) (2 20) (3 30))

(mapcar #'list nums tens (coerce firstname 'list))
;; ⇒ ((1 10 #\A) (2 20 #\l) (3 30 #\i)) — truncates on shortest list

;; Unzips
(apply #'mapcar #'list (mapcar #'list nums tens (coerce firstname 'list)))
;; ⇒ ((1 2 3) (10 20 30) (#\A #\l #\i))

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

>>> nums = [1, 2, 3]
>>> tens = [10, 20, 30]
>>> firstname = 'Alice'

>>> zipped = zip(nums, tens)
>>> zipped
[(1, 10), (2, 20), (3, 30)] 

>>> zip(*zipped) # unzip
[(1, 2, 3), (10, 20, 30)]

>>> zipped2 = zip(nums, tens, list(firstname))
>>> zipped2 # zip, truncates on shortest
[(1, 10, 'A'), (2, 20, 'l'), (3, 30, 'i')] 
>>> zip(*zipped2) # unzip
[(1, 2, 3), (10, 20, 30), ('A', 'l', 'i')]

>>> # mapping with `None' doesn't truncate; deprecated in Python 3.*
>>> map(None,nums, tens, list(firstname))
[(1, 10, 'A'), (2, 20, 'l'), (3, 30, 'i'), (None, None, 'c'), (None, None, 'e')]

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

-- nums contains an infinite list of numbers [1, 2, 3,...] 
nums = [1..]
tens = [10, 20, 30]
firstname = "Alice"

zip nums tens
-- ⇒ [(1,10),(2,20),(3,30)] — zip, truncates infinite list
unzip $ zip nums tens
-- ⇒ ([1,2,3],[10,20,30]) — unzip

zip3 nums tens firstname
-- ⇒ [(1,10,'A'),(2,20,'l'),(3,30,'i')] — zip, truncates
unzip3 $ zip3 nums tens firstname
-- ⇒ ([1,2,3],[10,20,30],"Ali") — unzip

Language comparison

List of languages by support of convolution:

Zip in various languages
Language	Zip	Zip 3 lists	Zip n lists	Notes
Clojure	`(map list list1 list2) (map vector list1 list2)`	`(map vector list1 list2 list3) (map vector list1 list2 list3)`	`(map list list1 … listn) (map vector list1 … listn)`	Stops after the length of the shortest list.
Common Lisp	`(mapcar #'list list1 list2)`	`(mapcar #'list list1 list2 list3)`	`(mapcar #'list list1 ... listn)`	Stops after the length of the shortest list.
D	`zip(range1,range2) range1.zip(range2)`	`zip(range1,range2,range3) range1.zip(range2,range3)`	`zip(range1,…,rangeN) range1.zip(…,rangeN)`	The stopping policy defaults to shortest and can be optionally provided as shortest, longest, or requiring the same length.^[4] The second form is an example of UFCS.
F#	`List.zip list1 list2 Seq.zip source1 source2 Array.zip array1 array2`	`List.zip3 list1 list2 list3 Seq.zip3 source1 source2 source3 Array.zip3 array1 array2 array3`
Haskell	`zip list1 list2`	`zip3 list1 list2 list3`	`zipn list1 … listn`	`zipn` for n > 3 is available in the module Data.List. Stops after the shortest list ends.
Python	`zip(list1, list2)`	`zip(list1, list2, list3)`	`zip(list1, …, listn)`	`zip()` and `map()` (3.x) stops after the shortest list ends, whereas `map()` (2.x) and `itertools.zip_longest()` (3.x) extends the shorter lists with `None` items
Ruby	`list1.zip(list2)`	`list1.zip(list2, list3)`	`list1.zip(list1, .., listn)`	When the list being executed upon (list1) is shorter than the lists being zipped the resulting list is the length of list1. If list1 is longer nil values are used to fill the missing values^[5]

Unzip in various languages
Language	Unzip	Unzip 3 tuples	Unzip n tuples	Notes
Clojure	`(apply map vector convlist)`	`(apply map vector convlist)`	`(apply map vector convlist)`
Common Lisp	`(apply #'mapcar #'list convlist)`	`(apply #'mapcar #'list convlist)`	`(apply #'mapcar #'list convlist)`
F#	`List.unzip list1 list2 Seq.unzip source1 source2 Array.unzip array1 array2`	`List.unzip3 list1 list2 list3 Seq.unzip3 source1 source2 source3 Array.unzip3 array1 array2 array3`
Haskell	`unzip convlist`	`unzip3 convlist`	`unzipn convlist`	`unzipn` for n > 3 is available in the module `Data.List.`
Python	`zip(*convvlist)`	`zip(*convvlist)`	`zip(*convvlist)`

References

↑ map from ClojureDocs
1 2 map(function, iterable, ...) from section Built-in Functions from Python v2.7.2 documentation
↑ zip :: [a] -> [b] -> [(a, b)] from Prelude, Basic libraries
↑ http://dlang.org/phobos/std_range.html#zip
↑ http://www.ruby-doc.org/core-2.0/Array.html#method-i-zip

This article incorporates material from convolution on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

This article is issued from Wikipedia - version of the 11/25/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.