zip function in Racket/Scheme

Question

Given two lists, return a list whose elements are lists of size two, such that for the i-th list, the first element is the i-th element of the first original list, and the second element is the i-th element of the second original list. If one list is smaller than the other, the resulting list is of the smallest size; and so if one of the lists is empty, return an empty list. For example:

> (zip '(1 2) '(3 4))
'((1 3) (2 4))

> (zip '(1 2 3) '())
'()
> (zip '() '(4 5 6))
'()
> (zip '(8 9) '(3 2 1 4))
'((8 3) (9 2))
> (zip '(8 9 1 2) '(3 4))
'((8 3) (9 4))

Solution 1

Try so:

(map cons '(1 2 3) '(a b c))

or so:

(map list '(1 2 3) '(a b c))

---

(define zip (lambda (l1 l2) (map list l1 l2)))

->(zip '(1 2 3) '(x y z))
'((1 x) (2 y) (3 z))

Solution 2

Because you didn't post the code you've written, I'm guessing this is homework. I'll give you some hints to get started, this is the general structure of the solution, fill-in the blanks - it'll be much more fun if you reach the correct answer by your own means!

(define (zip lst1 lst2)
  (cond ((<???> lst1)  ; if the first list is empty
         <???>)        ; then return the empty list 
        ((<???> lst2)  ; if the second list is empty
         <???>)        ; then also return the empty list 
        (else          ; otherwise
         (cons (list   ; cons a list with two elements:
                <???>  ; the first from the first list
                <???>) ; and the first from the second list
               (zip <???> <???>))))) ; advance recursion over both lists

I tested the above implementation with the sample inputs, and the results are as expected:

(zip '(1 2) '(3 4))
=> '((1 3) (2 4))

(zip '(1 2 3) '())
=> '()

(zip '() '(4 5 6))
=> '()

(zip '(8 9) '(3 2 1 4))
=> '((8 3) (9 2))

(zip '(8 9 1 2) '(3 4))
=> '((8 3) (9 4))

Solution 3

If you've solved the problem for the first element then you can recurse on the rest of the list:

(define (zip l1 l2)
  (if (or (null? l1) (null? l2))
      '()
      (cons (list (car l1) (car l2))
            (zip  (cdr l1) (cdr l2)))))

provided you handle the base case where either list is empty.

> (zip '(1 2 3 4) '(a b))
((1 a) (2 b))
> (zip '() '(a b))
()

Solution 4

If your map implementation stops at the shortest list, then zip can be defined with map, Scheme's list procedure and apply. Here's a hint:

(define (zip . lsts)
  (apply <??> <??> lsts))

SRFI-1's map is sufficient. So in Racket you add (require (only-in srfi/1 map))

Solution 5

If we accept Racket functions, and also relax the requirement of returning 2-tuples in favor of a more general zip, then I would check out for/list. Here are examples zipping or interleaving two or three lists, stopping at the shortest list.

(define l1 '(a b c))
(define l2 '(1 2 3))
(define l3 '(true false))

;; → '((a 1 true) (b 2 false))
(for/list ([i l1] [j l2] [k l3])
          (list i j k))

;; → '((a 1) (b 2) (c 3))
(for/list ([i l1] [j l2])
          (list i j))

;; → '()
(for/list ([i l1] [j l2] [k null])
          (list i j k))

View more solutions

Comments

[Sylwester]

(map cons '(1 2 3) '(a b c)) ; ==> ((1 . a) (2 . b) (3 . c)), not the desired result ((1 a) (2 b) (3 c))

[alinsoar]

Any function can be used there, as time as the function has 2 input parameters.

[cat]

Out of curiosity, why the lambda in the zip definition? It seems like (define (zip l1 l2) (map list l1 l2)) would do just as well... ?

[alinsoar]

What you wrote is a syntactic sugar for what I wrote. The form you wrote is expanded in what I wrote during preprocessing. But a better syntactic sugar for composition is present in Haskell under the concept of composition (o operator) or under the concept of section. In that case there is no need to explicitly pass the name of arguments, as haskell does that for you in the preprocessing.

[Abhishek]

I don't think does the right thing in Racket at least - you only tested the condition where the input lengths are equal. Additionally zip is typically understood to work on streams as well so you would for example create an indexed pair with (zip '(1 2 3) (in-naturals))