How to write unzip using foldr in scheme?

Question

This is the code for unzip function coded in Scheme

(define (unzip lst)
  (define (firsts lst)
    (if (null? lst)
        '()
        (cons (caar lst)
              (firsts (cdr lst)))))
  (define (seconds lst)
    (if (null? lst)
        '()
        (cons (cdar lst)
              (seconds (cdr lst)))))
  (list (firsts lst) (seconds lst)))

will give us output like this:

(unzip '((1 . 2) (3 . 4) (5 . 6))) => '((1 3 5) (2 4 6))'

But I'm curious that how could I implement the same function unzip using Scheme foldr function, anyone could help ? Really thanks in advance.

Answer 1

Building on Leif's answer, Racket has more forms like for/fold that handle some parts of accumulation for you. For example:

#lang racket

(define (unzip lst)
  (for/lists (firsts seconds #:result (list firsts seconds))
             ([pr (in-list lst)])
    (values (car pr) (cdr pr))))

(unzip '((1 . 2) (3 . 4) (5 . 6)))

Answer 2

This simple implementation doesn't use fold*, map, reverse, flatten, or append - and it uses a tail call

(define (unzip xs (return list))
  (if (empty? xs)
      (return empty empty)
      (unzip (cdr xs)
             (lambda (l r)
               (return (cons (caar xs) l)
                       (cons (cdar xs) r))))))

(unzip '((1 . 2) (3 . 4) (5 . 6)))
;; '((1 3 5) (2 4 6))

Answer 3

Most beautiful solution - but without foldr/l

(define (unzip al) (list (map car al) (map cdr al)))

Solution 1 - with foldr

(define (unzip lst)
  (foldr (lambda (next-pair acc) (list (cons (car next-pair)
                                             (car acc))
                                       (cons (cdr next-pair) 
                                             (cadr acc))))
         '(() ())
         lst))

Note: In foldr - although not intuitive - The second argument (and not the first) is the accumulated result (thus now renamed to acc) - which is the first and second list in a final-result's list - and p is the next pair in the list. So the first in the result list is (car acc) and the second is (cadr acc). I misunderstood it myself before - by naming the arguments of the lambda function p1 and p2 thinking that foldr acts on the first and last pair of the lst. So by solving your question I gained some better understanding of what the two arguments in the inner lambda function of of foldr actually mean - one is the accumulated result and the other is the next element in the input-list. However, now tried foldl: The inner lambda's arguments are in the same order like in foldr - first the next-pair and then the accumulated result.

A solution with foldl

(define (unzip lst)
  (foldl (lambda (p acc) (list (append (car acc) (list (car p)))
                               (append (cadr acc) (list (cdr p)))))
         '(() ())
         lst))

An slightly more efficient foldl solution

(define (unzip lst)
  (let ((res (foldl (lambda (p acc) (list (cons (car p) (car acc))
                                          (cons (cdr p) (cadr acc))))
                    '(() ())
                    lst)))
    (map reverse res)))

Instead of append, conssing the result and at the end reverseing the resulting inner lists.

Solution 2 - with foldr

Not efficient, but helped to get to solution 1 (flatten (list x y)) -> (cons x y):

(define (unzip lst)
  (foldr (lambda (next acc) (list (flatten (list (car next)
                                              (car acc)))
                               (flatten (list (cdr next) 
                                              (cdr acc)))))
         '(() ())
         lst))

Solution 3 - with foldr

Even more unefficient - but helped to get to solution 2 (append (list x) (list y)) -> (list x y):

(define (unzip lst)
  (foldr (lambda (next acc) (list (flatten (append (list (car next)) 
                                                (list (car acc))))
                               (flatten (append (list (cdr next)
                                                      (cdr acc))))))
         '(() ())
         lst))

A tail-recursive solution without foldr/l

(define (unzip alist)    
    (define (.unzip l acc) ; even numbered l as a given
      (cond ((null? l) (map reverse acc)) ; reverse both inner lists
            (else (.unzip (cddr l) (list (cons (car l) (car acc))
                                         (cons (cadr l) (cadr acc)))))))
    (.unzip (flatten alist) '(() ())))

All give:

> (unzip '((1 . 2) (3 . 4) (5 . 6))) 
'((1 3 5) (2 4 6))

Answer 4

Since you used the racket tag, I'll give an answer using for/fold, which has much nicer syntax than foldr or foldl.¹

The syntax for for/fold is roughly:

(for/fold <accumulators>
          <iterators>
  <body>)

We can use two accumulators ret1 and ret2 to store each of the two lists, and then put them together in the accumulators #:result form:

([ret1 '()]
 [ret2 '()]
 #:result (list (reverse ret1) (reverse ret2)))

The iterators are fairly straightforward:

 ([i (in-list lst)])

And finally, the body just needs to break apart each pair, and append it to the accumulator:

(values (cons (car i) ret1)
        (cons (cdr i) ret2))

So putting it all together gives:

(define (unzip lst)
  (for/fold ([ret1 '()]
             [ret2 '()]
             #:result (list (reverse ret1) (reverse ret2)))
            ([i (in-list lst)])
    (values (cons (car i) ret1)
            (cons (cdr i) ret2))))

As expected:

> (unzip '((1 . 2) (3 . 4) (5 . 6))) 
'((1 3 5) (2 4 6))

_{¹At least in my opinion, these things are always a bit subjective.}