Convolution (computer science)
In computer science, specifically formal languages, convolution is a function which maps a tuple of sequences into a sequence of tuples. This name zip derives from the action of a zipper in that it interleaves two formerly disjoint sequences. The reverse function is unzip which performs a deconvolution.
Example
Given the three words cat, fish and be where |cat| is 3, |fish| is 4 and |be| is 2. Let denote the length of the longest word which is fish;. The convolution of cat, 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 :
zip3 "cat" "fish" "be"
--
Definition
Let Σ be an alphabet, # a symbol not in Σ.Let x1x2... x|x|, y1y2... y|y|, z1z2... z|z|,... be n words 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 :
where for any index i > |w|, the wi is #.
The convolution of x, y, z,... is denoted conv, zip 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 number of lists as argument. An example from Clojure:;; `nums' contains an infinite list of numbers
;; To convolve and into a vector, invoke `map vector' on them; same with list
; ⇒
; ⇒ )
; ⇒
;; `map' truncates to the shortest sequence; note missing \c and \e from "Alice"
; ⇒
; ⇒
;; To unzip, apply `map vector' or `map list'
;; ⇒ )
In Common Lisp:
;; ⇒ )
;; ⇒ ) — truncates on shortest list
;; Unzips
;; ⇒ )
Languages such as Python provide a zip function, older version allowed mapping None over lists to get a similar effect. zip in conjunction with the * operator unzips a list:
>>> nums =
>>> tens =
>>> firstname = 'Alice'
>>> zipped = zip
>>> zipped
>>> zip # unzip
>>> zipped2 = zip
>>> zipped2 # zip, truncates on shortest
>>> zip # unzip
>>> # mapping with `None' doesn't truncate; deprecated in Python 3.*
>>> map
Haskell has a method of convolving sequences but requires a specific function for each arity, similarly the functions unzip and unzip3 are available for unzipping:
-- nums contains an infinite list of numbers
nums =
tens =
firstname = "Alice"
zip nums tens
-- ⇒ — zip, truncates infinite list
unzip $ zip nums tens
-- ⇒ — unzip
zip3 nums tens firstname
-- ⇒ — zip, truncates
unzip3 $ zip3 nums tens firstname
-- ⇒ — unzip
Language comparison
List of languages by support of convolution:| Language | Zip | Zip 3 lists | Zip n lists | Notes |
| Clojure | Stops after the length of the shortest list. | |||
| Common Lisp | Stops after the length of the shortest list. | |||
| D | zip range1.zip | zip range1.zip | zip range1.zip | The stopping policy defaults to shortest and can be optionally provided as shortest, longest, or requiring the same length. 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 | zip | zip | zip and map stops after the shortest list ends, whereas map and itertools.zip_longest extends the shorter lists with None items |
| Ruby | list1.zip | list1.zip | list1.zip | When the list being executed upon 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 |
| Scala | list1.zip | If one of the two collections is longer than the other, its remaining elements are ignored. |
| Language | Unzip | Unzip 3 tuples | Unzip n tuples | Notes |
| Clojure | ||||
| Common Lisp | ||||
| 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 | zip | zip |