Zipping (computer Science)

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,\#)(\#,h,\#)$

where ''#'' is a symbol not in the original alphabet. In Haskell this truncates to the shortest sequence $\underline$, where $\underline = 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 , 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 , 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,\ldots)(x_2,y_2,\ldots)\ldots(x_,y_,\ldots)$

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

In programming languages

Zip functions are often available in programming languages, often referred to as . In Lisp-dialects one can simply the desired function over the desired lists, 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 0 20 30
(def firstname "Alice")

;; To zip (0 1 2 3 ...) and 0 20 30into a vector, invoke `map vector' on them; same with list
(map vector nums tens) ; ⇒ ( 10 20 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) ; ⇒ ( 10 \A 20 \l 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 function, older version (Python 2.*) allowed mapping over lists to get a similar effect.map(function, iterable, ...)
from section Built-in Functions from Python v2.7.2 documentation in conjunction with the operator unzips a list:

>>> nums = , 2, 3>>> tens = 0, 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 zipping sequences but requires a specific function for each arity ( for two sequences, for three etc.),zip :: [a
-> [b">">zip :: [a
-> [b-> [(a, b)"><_a><br>->_[b.html" ;"title="">zip :: [a
-> [b">">zip :: [a
-> [b-> [(a, b)/nowiki>] from Prelude, Basic libraries similarly the functions and are available for unzipping:

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

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

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

Language comparison

List of languages by support of zip:

{, class="wikitable"
, + Unzip in various languages
, -
! scope="col" , Language
! scope="col" , Unzip
! scope="col" , Unzip 3 tuples
! scope="col" , Unzip ''n'' tuples
! scope="col" , Notes
, -
! scope="row" , Clojure
,
,
,
,
, -
! scope="row" , Common Lisp
,
,
,
,
, -
! scope="row" , F#
,


,


,
,
, -
! scope="row" , Haskell
,
,
,
, for ''n'' > 3 is available in the module
, -
! scope="row" , Python
,
,
, {{mono, zip(*''zipvlist'')
,

See also

* Map (higher-order function)

References

Articles with example Haskell code
Articles with example Lisp (programming language) code
Articles with example Clojure code
Articles with example Python (programming language) code