Zipping (computer science)

Template:Short description Template:About In computer science, zipping 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 inverse function is unzip.

Example

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

$(c,f,b)(a,i,e)(t,s,\mathrm{\#})(\mathrm{\#},h,\mathrm{\#})$

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

zip3 "cat" "fish" "be"
-- [('c','f','b'),('a','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 zip of these words is a finite sequence of n-tuples of elements of Template:Math, i.e. an element of $((\mathrm{\Sigma }\cup \{\mathrm{\#}\}{)}^n{)}^{*}$:

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

where for any index Template:Math, 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:

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

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

In programming languages

Zip functions are often available in programming languages, often referred to as Template:Mono. In Lisp-dialects one can simply Template:Mono the desired function over the desired lists, Template:Mono 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 (0 1 2 3 ...)
(def nums (range))
(def tens [10 20 30])
(def firstname "Alice")

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

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

;; 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 Template:Mono function. Template:Mono in conjunction with the Template:Mono operator unzips a list:

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

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

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

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

Haskell has a method of zipping sequences but requires a specific function for each arity (Template:Mono for two sequences, Template:Mono for three etc.), similarly the functions Template:Mono and Template:Mono 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 zip:

Zip in various languages

Language	Zip	Zip 3 lists	Zip n lists	Notes
Chapel	Template:Mono	Template:Mono	Template:Mono	The shape of each iterator, the rank and the extents in each dimension, must be identical.
Clojure	Template:Mono Template:Mono	Template:Mono Template:Mono	Template:Mono Template:Mono	Stops after the length of the shortest list.
Common Lisp	Template:Codett	Template:Codett	Template:Codett	Stops after the length of the shortest list.
D	Template:Mono Template:Mono	Template:Mono Template:Mono	Template:Mono Template:Mono	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#	Template:Mono Template:Mono Template:Mono	Template:Mono Template:Mono Template:Mono
Haskell	Template:Mono	Template:Mono	Template:Mono	Template:Mono for n > 3 is available in the module Data.List. Stops after the shortest list ends.
Python	Template:Mono	Template:Mono	Template:Mono	Template:Mono and Template:Mono (3.x) stops after the shortest list ends, whereas Template:Mono (2.x) and Template:Mono (3.x) extends the shorter lists with Template:Mono items
Ruby	Template:Mono	Template:Mono	Template:Mono	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
Scala	Template:Mono			If one of the two collections is longer than the other, its remaining elements are ignored.

Unzip in various languages

Language	Unzip	Unzip 3 tuples	Unzip n tuples	Notes
Clojure	Template:Mono	Template:Mono	Template:Mono
Common Lisp	Template:Codett	Template:Codett	Template:Codett
F#	Template:Mono Template:Mono Template:Mono	Template:Mono Template:Mono Template:Mono
Haskell	Template:Mono	Template:Mono	Template:Mono	Template:Mono for n > 3 is available in the module Template:Mono
Python	Template:Mono	Template:Mono	Template:Mono

See also

• Map (higher-order function)