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))

Frederiksberg

What have you tried so far? please post the code! otherwise people will think that you want to get you homework done for free ;) – Magda

Answer 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))

Mimosaceous

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

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

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... ? – Gladisgladney

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. – Mimosaceous

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)) – Imminent

Answer 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))

Thach

Answer 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))
()

Suint

Answer 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))

Aconite

Answer 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))

Quattrocento

Answer 6

Today, I came across the same exercise and did my own implementation which is different from all the ones people posted here. All the other answers are great. I really liked the most voted one from @Alinsoar.

Definitely, the other answers are actually better than my implementation. But I will post it anyway. Maybe, this can help someone trying to learn Racket.

(define (shorter-list xs ys)
  (if (> (length xs) (length ys))
      ys
      xs))

(define (zip xs ys)
  (cond [(null? (shorter-list xs ys)) null]
        [true (cons (list (car xs) (car ys)) (zip (cdr xs) (cdr ys)))]))

Itch