Transpose list of tuples filling with empty lists

问题:

I'm new to Scheme and I'm trying to write a procedure which combines n list into a list of n-tuples. If the lists are of different size, the tuples should contain the empty list () when the corresponding list ran out of elements.

My current implementation is the following:

(define (comb list1 list2)  
    (cond [(empty? list1) empty]
          [(empty? list2) empty]
          [else (cons (list (first list1) (first list2))
                      (comb (rest list1) (rest list2)))]))

However, this program doesn't produce another tuple when there are no more items in the list to combine. For instance, (comb '(1 2 3 ) '(3 4)) produces only ((1 3) (2 4))

How do I solve it?

回答1:

This is a bit tricky, and I believe it's not an appropriate exercise for someone who is just learning the basics of the language. Anyway, here's my proposed solution, in terms of higher-order procedures:

; helper procedure for filling a list with arbitrary values at the end
(define (fill lst val num)
  (append lst
          (build-list num (const val))))

; helper procedure for transposing a list of lists    
(define (transpose lsts)
  (apply map list lsts))

; main procedure
(define (list-tuples lsts)
  (let* ((lengths    (map length lsts))    ; obtain the length of each sublist
         (max-length (apply max lengths))) ; find out the maximum length
    (transpose                             ; build new sublists element-wise
     (map (lambda (lst len)                ; build sublists of the right length
            (fill lst '() (- max-length len)))  ; fill sublists with '()
          lsts
          lengths))))

The trick was to find the maximum length of the lists and then build new lists with that length, filling them with '() at the end. After that, it's a simple matter of building the answer by taking one element from each sublist. It works as expected:

(list-tuples '((m n o) (1) (x y)))
=> '((m 1 x) (n () y) (o () ()))

回答2:

You need to specifically deal with the situation where one of the lists is empty. The following does what I think you want with two lists.

 (define (comb l1 l2)
   (cond 
     ((empty? l1) 
      (cond
        ((empty? l2) '())
        (else (cons (list '() (car l2)) (comb l1 (cdr l2))))))
     (else
       (cond
         ((empty? l2) (cons (list (car l1) '()) (comb (cdr l1) l2)))
         (else (cons (list (car l1) (car l2)) (comb (cdr l1) (cdr l2))))))))

回答3:

Let's split the problem into 2 parts.

First let's assume a procedure that will take a list, and return the following results:

1. a list containing the first items of each sublist
2. a list containing the remainder of each sublist
3. the number of non-empty lists encountered

An example implementation could be:

(define (split-tuples lst)
  (let loop ((lst lst) (fst null) (rst null) (cnt 0))
    (if (null? lst)
        (values (reverse fst) (reverse rst) cnt)
        (let ((c (car lst)))
          (if (null? c)
              (loop (cdr lst) (cons      c  fst) (cons      c  rst) cnt)
              (loop (cdr lst) (cons (car c) fst) (cons (cdr c) rst) (add1 cnt)))))))

Testing:

> (split-tuples '((m n o) (1) (x y)))
'(m 1 x)
'((n o) () (y))
3
> (split-tuples '((n o) () (y)))
'(n () y)
'((o) () ())
2
> (split-tuples '((o) () ()))
'(o () ())
'(() () ())
1
> (split-tuples '(() () ()))
'(() () ())
'(() () ())
0

Now using this procedure we create the main procedure that will just loop until all sublists are empty:

(define (list-tuples lst)
  (let loop ((lst lst) (res null))
    (let-values (((fst rst cnt) (split-tuples lst)))
      (if (zero? cnt)
          (reverse res)
          (loop rst (cons fst res))))))

Testing:

> (list-tuples '((m n o) (1) (x y)))
'((m 1 x) (n () y) (o () ()))
> (list-tuples '())
'()