Zipping (computer science)

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 ${\displaystyle \ell }$ denote the length of the longest word, i.e. the maximum of |x|, |y|, |z|, ... .

The zip of these words is a finite sequence of n-tuples of elements of (Σ ∪ {#}), i.e. an element of ${\displaystyle ((\mathrm{\Sigma }\cup \{\mathrm{\#}\}{)}^n{)}^{\ast }}$:

${\displaystyle (x_1,y_1,\dots )(x_2,y_2,\dots )\dots (x_{\ell },y_{\ell },\dots )}$,

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

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

The inverse to zip is sometimes denoted unzip.

A variation of the zip operation is defined by:

${\displaystyle (x_1,y_1,\dots )(x_2,y_2,\dots )\dots (x_{\underset{\_}{\ell }},y_{\underset{\_}{\ell }},\dots )}$

where ${\displaystyle \underset{\_}{\ell }}$ is the minimum length of the input words. It avoids the use of an adjoined element ${\displaystyle \mathrm{\#}}$, but destroys information about elements of the input sequences beyond ${\displaystyle \underset{\_}{\ell }}$.

In programming languages

Zip 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:

<span id="mwgg"></span><span class="c1" id="mwgw">;; `nums' contains an infinite list of numbers (0 1 2 3 ...)</span> <span class="p" id="mwhA">(</span><span class="k" id="mwhQ">def </span><span class="nv" id="mwhg">nums</span><span class="w" id="mwhw"> </span><span class="p" id="mwiA">(</span><span class="nf" id="mwiQ">range</span><span class="p" id="mwig">))</span> <span class="p" id="mwiw">(</span><span class="k" id="mwjA">def </span><span class="nv" id="mwjQ">tens</span><span class="w" id="mwjg"> </span><span class="p" id="mwjw">[</span><span class="mi" id="mwkA">10</span><span class="w" id="mwkQ"> </span><span class="mi" id="mwkg">20</span><span class="w" id="mwkw"> </span><span class="mi" id="mwlA">30</span><span class="p" id="mwlQ">])</span> <span class="p" id="mwlg">(</span><span class="k" id="mwlw">def </span><span class="nv" id="mwmA">firstname</span><span class="w" id="mwmQ"> </span><span class="s" id="mwmg">"Alice"</span><span class="p" id="mwmw">)</span> <span class="c1" id="mwnA">;; To zip (0 1 2 3 ...) and [10 20 30] into a vector, invoke `map vector' on them; same with list</span> <span class="p" id="mwnQ">(</span><span class="nb" id="mwng">map vector </span><span class="nv" id="mwnw">nums</span><span class="w" id="mwoA"> </span><span class="nv" id="mwoQ">tens</span><span class="p" id="mwog">)</span><span class="w" id="mwow"> </span><span class="c1" id="mwpA">; ⇒ ([0 10] [1 20] [2 30])</span> <span class="p" id="mwpQ">(</span><span class="nb" id="mwpg">map list </span><span class="nv" id="mwpw">nums</span><span class="w" id="mwqA"> </span><span class="nv" id="mwqQ">tens</span><span class="p" id="mwqg">)</span><span class="w" id="mwqw"> </span><span class="c1" id="mwrA">; ⇒ ((0 10) (1 20) (2 30))</span> <span class="p" id="mwrQ">(</span><span class="nb" id="mwrg">map str </span><span class="nv" id="mwrw">nums</span><span class="w" id="mwsA"> </span><span class="nv" id="mwsQ">tens</span><span class="p" id="mwsg">)</span><span class="w" id="mwsw"> </span><span class="c1" id="mwtA">; ⇒ ("010" "120" "230")</span> <span class="c1" id="mwtQ">;; `map' truncates to the shortest sequence; note missing \c and \e from "Alice"</span> <span class="p" id="mwtg">(</span><span class="nb" id="mwtw">map vector </span><span class="nv" id="mwuA">nums</span><span class="w" id="mwuQ"> </span><span class="nv" id="mwug">tens</span><span class="w" id="mwuw"> </span><span class="nv" id="mwvA">firstname</span><span class="p" id="mwvQ">)</span><span class="w" id="mwvg"> </span><span class="c1" id="mwvw">; ⇒ ([0 10 \A] [1 20 \l] [2 30 \i])</span> <span class="p" id="mwwA">(</span><span class="nb" id="mwwQ">map str </span><span class="nv" id="mwwg">nums</span><span class="w" id="mwww"> </span><span class="nv" id="mwxA">tens</span><span class="w" id="mwxQ"> </span><span class="nv" id="mwxg">firstname</span><span class="p" id="mwxw">)</span><span class="w" id="mwyA"> </span><span class="c1" id="mwyQ">; ⇒ ("010A" "120l" "230i")</span> <span class="c1" id="mwyg">;; To unzip, apply `map vector' or `map list'</span> <span class="p" id="mwyw">(</span><span class="nb" id="mwzA">apply map list </span><span class="p" id="mwzQ">(</span><span class="nb" id="mwzg">map vector </span><span class="nv" id="mwzw">nums</span><span class="w" id="mw0A"> </span><span class="nv" id="mw0Q">tens</span><span class="w" id="mw0g"> </span><span class="nv" id="mw0w">firstname</span><span class="p" id="mw1A">))</span> <span class="c1" id="mw1Q">;; ⇒ ((0 1 2) (10 20 30) (\A \l \i))</span>

In Common Lisp:

<span id="mw2g"></span><span class="p" id="mw2w">(</span><span class="nb" id="mw3A">defparameter</span><span class="w" id="mw3Q"> </span><span class="nv" id="mw3g">nums</span><span class="w" id="mw3w"> </span><span class="o" id="mw4A">'</span><span class="p" id="mw4Q">(</span><span class="mi" id="mw4g">1</span><span class="w" id="mw4w"> </span><span class="mi" id="mw5A">2</span><span class="w" id="mw5Q"> </span><span class="mi" id="mw5g">3</span><span class="p" id="mw5w">))</span> <span class="p" id="mw6A">(</span><span class="nb" id="mw6Q">defparameter</span><span class="w" id="mw6g"> </span><span class="nv" id="mw6w">tens</span><span class="w" id="mw7A"> </span><span class="o" id="mw7Q">'</span><span class="p" id="mw7g">(</span><span class="mi" id="mw7w">10</span><span class="w" id="mw8A"> </span><span class="mi" id="mw8Q">20</span><span class="w" id="mw8g"> </span><span class="mi" id="mw8w">30</span><span class="p" id="mw9A">))</span> <span class="p" id="mw9Q">(</span><span class="nb" id="mw9g">defparameter</span><span class="w" id="mw9w"> </span><span class="nv" id="mw-A">firstname</span><span class="w" id="mw-Q"> </span><span class="s" id="mw-g">"Alice"</span><span class="p" id="mw-w">)</span> <span class="p" id="mw_A">(</span><span class="nb" id="mw_Q">mapcar</span><span class="w" id="mw_g"> </span><span class="nf" id="mw_w">#'</span><span class="nb" id="mwAQA">list</span><span class="w" id="mwAQE"> </span><span class="nv" id="mwAQI">nums</span><span class="w" id="mwAQM"> </span><span class="nv" id="mwAQQ">tens</span><span class="p" id="mwAQU">)</span> <span class="c1" id="mwAQY">;; ⇒ ((1 10) (2 20) (3 30))</span> <span class="p" id="mwAQc">(</span><span class="nb" id="mwAQg">mapcar</span><span class="w" id="mwAQk"> </span><span class="nf" id="mwAQo">#'</span><span class="nb" id="mwAQs">list</span><span class="w" id="mwAQw"> </span><span class="nv" id="mwAQ0">nums</span><span class="w" id="mwAQ4"> </span><span class="nv" id="mwAQ8">tens</span><span class="w" id="mwARA"> </span><span class="p" id="mwARE">(</span><span class="nb" id="mwARI">coerce</span><span class="w" id="mwARM"> </span><span class="nv" id="mwARQ">firstname</span><span class="w" id="mwARU"> </span><span class="ss" id="mwARY">'list</span><span class="p" id="mwARc">))</span> <span class="c1" id="mwARg">;; ⇒ ((1 10 #\A) (2 20 #\l) (3 30 #\i)) — truncates on shortest list</span> <span class="c1" id="mwARk">;; Unzips</span> <span class="p" id="mwARo">(</span><span class="nb" id="mwARs">apply</span><span class="w" id="mwARw"> </span><span class="nf" id="mwAR0">#'</span><span class="nb" id="mwAR4">mapcar</span><span class="w" id="mwAR8"> </span><span class="nf" id="mwASA">#'</span><span class="nb" id="mwASE">list</span><span class="w" id="mwASI"> </span><span class="p" id="mwASM">(</span><span class="nb" id="mwASQ">mapcar</span><span class="w" id="mwASU"> </span><span class="nf" id="mwASY">#'</span><span class="nb" id="mwASc">list</span><span class="w" id="mwASg"> </span><span class="nv" id="mwASk">nums</span><span class="w" id="mwASo"> </span><span class="nv" id="mwASs">tens</span><span class="w" id="mwASw"> </span><span class="p" id="mwAS0">(</span><span class="nb" id="mwAS4">coerce</span><span class="w" id="mwAS8"> </span><span class="nv" id="mwATA">firstname</span><span class="w" id="mwATE"> </span><span class="ss" id="mwATI">'list</span><span class="p" id="mwATM">)))</span> <span class="c1" id="mwATQ">;; ⇒ ((1 2 3) (10 20 30) (#\A #\l #\i))</span>

Languages such as Python provide a zip() function. zip() in conjunction with the * operator unzips a list:

<span id="mwAUM"></span><span class="gp" id="mwAUQ">>>> </span><span class="n" id="mwAUU">nums</span> <span class="o" id="mwAUY">=</span> <span class="p" id="mwAUc">[</span><span class="mi" id="mwAUg">1</span><span class="p" id="mwAUk">,</span> <span class="mi" id="mwAUo">2</span><span class="p" id="mwAUs">,</span> <span class="mi" id="mwAUw">3</span><span class="p" id="mwAU0">]</span> <span class="gp" id="mwAU4">>>> </span><span class="n" id="mwAU8">tens</span> <span class="o" id="mwAVA">=</span> <span class="p" id="mwAVE">[</span><span class="mi" id="mwAVI">10</span><span class="p" id="mwAVM">,</span> <span class="mi" id="mwAVQ">20</span><span class="p" id="mwAVU">,</span> <span class="mi" id="mwAVY">30</span><span class="p" id="mwAVc">]</span> <span class="gp" id="mwAVg">>>> </span><span class="n" id="mwAVk">firstname</span> <span class="o" id="mwAVo">=</span> <span class="s1" id="mwAVs">'Alice'</span> <span class="gp" id="mwAVw">>>> </span><span class="n" id="mwAV0">zipped</span> <span class="o" id="mwAV4">=</span> <span class="nb" id="mwAV8">list</span><span class="p" id="mwAWA">(</span><span class="nb" id="mwAWE">zip</span><span class="p" id="mwAWI">(</span><span class="n" id="mwAWM">nums</span><span class="p" id="mwAWQ">,</span> <span class="n" id="mwAWU">tens</span><span class="p" id="mwAWY">))</span> <span class="gp" id="mwAWc">>>> </span><span class="n" id="mwAWg">zipped</span> <span class="go" id="mwAWk">[(1, 10), (2, 20), (3, 30)]</span> <span class="gp" id="mwAWo">>>> </span><span class="nb" id="mwAWs">list</span><span class="p" id="mwAWw">(</span><span class="nb" id="mwAW0">zip</span><span class="p" id="mwAW4">(</span><span class="o" id="mwAW8">*</span><span class="n" id="mwAXA">zipped</span><span class="p" id="mwAXE">))</span> <span class="c1" id="mwAXI"># unzip</span> <span class="go" id="mwAXM">[(1, 2, 3), (10, 20, 30)]</span> <span class="gp" id="mwAXQ">>>> </span><span class="n" id="mwAXU">zipped2</span> <span class="o" id="mwAXY">=</span> <span class="nb" id="mwAXc">list</span><span class="p" id="mwAXg">(</span><span class="nb" id="mwAXk">zip</span><span class="p" id="mwAXo">(</span><span class="n" id="mwAXs">nums</span><span class="p" id="mwAXw">,</span> <span class="n" id="mwAX0">tens</span><span class="p" id="mwAX4">,</span> <span class="nb" id="mwAX8">list</span><span class="p" id="mwAYA">(</span><span class="n" id="mwAYE">firstname</span><span class="p" id="mwAYI">)))</span> <span class="gp" id="mwAYM">>>> </span><span class="n" id="mwAYQ">zipped2</span> <span class="c1" id="mwAYU"># zip, truncates on shortest</span> <span class="go" id="mwAYY">[(1, 10, 'A'), (2, 20, 'l'), (3, 30, 'i')] </span> <span class="gp" id="mwAYc">>>> </span><span class="nb" id="mwAYg">list</span><span class="p" id="mwAYk">(</span><span class="nb" id="mwAYo">zip</span><span class="p" id="mwAYs">(</span><span class="o" id="mwAYw">*</span><span class="n" id="mwAY0">zipped2</span><span class="p" id="mwAY4">))</span> <span class="c1" id="mwAY8"># unzip</span> <span class="go" id="mwAZA">[(1, 2, 3), (10, 20, 30), ('A', 'l', 'i')]</span>

Haskell has a method of zipping 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:

<span id="mwAaA"></span><span class="c1" id="mwAaE">-- nums contains an infinite list of numbers [1, 2, 3, ...] </span> <span class="nf" id="mwAaI">nums</span><span class="w" id="mwAaM"> </span><span class="ow" id="mwAaQ">=</span><span class="w" id="mwAaU"> </span><span class="p" id="mwAaY">[</span><span class="mi" id="mwAac">1</span><span class="o" id="mwAag">..</span><span class="p" id="mwAak">]</span> <span class="nf" id="mwAao">tens</span><span class="w" id="mwAas"> </span><span class="ow" id="mwAaw">=</span><span class="w" id="mwAa0"> </span><span class="p" id="mwAa4">[</span><span class="mi" id="mwAa8">10</span><span class="p" id="mwAbA">,</span><span class="w" id="mwAbE"> </span><span class="mi" id="mwAbI">20</span><span class="p" id="mwAbM">,</span><span class="w" id="mwAbQ"> </span><span class="mi" id="mwAbU">30</span><span class="p" id="mwAbY">]</span> <span class="nf" id="mwAbc">firstname</span><span class="w" id="mwAbg"> </span><span class="ow" id="mwAbk">=</span><span class="w" id="mwAbo"> </span><span class="s" id="mwAbs">"Alice"</span> <span class="nf" id="mwAbw">zip</span><span class="w" id="mwAb0"> </span><span class="n" id="mwAb4">nums</span><span class="w" id="mwAb8"> </span><span class="n" id="mwAcA">tens</span> <span class="c1" id="mwAcE">-- ⇒ [(1,10), (2,20), (3,30)] — zip, truncates infinite list</span> <span class="nf" id="mwAcI">unzip</span><span class="w" id="mwAcM"> </span><span class="o" id="mwAcQ">$</span><span class="w" id="mwAcU"> </span><span class="n" id="mwAcY">zip</span><span class="w" id="mwAcc"> </span><span class="n" id="mwAcg">nums</span><span class="w" id="mwAck"> </span><span class="n" id="mwAco">tens</span> <span class="c1" id="mwAcs">-- ⇒ ([1,2,3], [10,20,30]) — unzip</span> <span class="nf" id="mwAcw">zip3</span><span class="w" id="mwAc0"> </span><span class="n" id="mwAc4">nums</span><span class="w" id="mwAc8"> </span><span class="n" id="mwAdA">tens</span><span class="w" id="mwAdE"> </span><span class="n" id="mwAdI">firstname</span> <span class="c1" id="mwAdM">-- ⇒ [(1,10,'A'), (2,20,'l'), (3,30,'i')] — zip, truncates</span> <span class="nf" id="mwAdQ">unzip3</span><span class="w" id="mwAdU"> </span><span class="o" id="mwAdY">$</span><span class="w" id="mwAdc"> </span><span class="n" id="mwAdg">zip3</span><span class="w" id="mwAdk"> </span><span class="n" id="mwAdo">nums</span><span class="w" id="mwAds"> </span><span class="n" id="mwAdw">tens</span><span class="w" id="mwAd0"> </span><span class="n" id="mwAd4">firstname</span> <span class="c1" id="mwAd8">-- ⇒ ([1,2,3], [10,20,30], "Ali") — unzip</span>

Language comparison

List of languages by support of zip: