Переставить список кортежей, заполненных пустыми списками

Я новичок в Scheme и пытаюсь написать процедуру, которая объединяет список n в список кортежей n. Если списки имеют разный размер, кортежи должны содержать пустой список (), когда в соответствующем списке заканчиваются элементы.

Моя текущая реализация следующая:

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

Однако эта программа не создает другой кортеж, если в списке больше нет элементов для объединения. Например, (comb '(1 2 3 ) '(3 4)) производит только ((1 3) (2 4))

Как мне это решить?


list scheme racket mit-scheme
person Raj    schedule 04.10.2015    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Это немного сложно, и я считаю, что это не подходящее упражнение для тех, кто только изучает основы языка. В любом случае, вот мое предлагаемое решение с точки зрения процедур более высокого порядка:

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

Уловка заключалась в том, чтобы найти максимальную длину списков, а затем построить новые списки этой длины, заполнив их '() в конце. После этого нужно просто построить ответ, взяв по одному элементу из каждого подсписка. Работает как положено:

(list-tuples '((m n o) (1) (x y)))
=> '((m 1 x) (n () y) (o () ()))
person Óscar López    schedule 04.10.2015

arrow_upward
0
arrow_downward

Вам нужно специально разобраться с ситуацией, когда один из списков пуст. Следующее делает то, что я думаю, вы хотите с двумя списками.

 (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))))))))
person Penguino    schedule 04.10.2015

arrow_upward
0
arrow_downward

Разобьем задачу на 2 части.

Сначала предположим, что процедура принимает список и возвращает следующие результаты:

  1. список, содержащий первые элементы каждого подсписка
  2. список, содержащий остаток от каждого подсписка
  3. количество обнаруженных непустых списков

Пример реализации может быть:

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

Тестирование:

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

Теперь, используя эту процедуру, мы создаем основную процедуру, которая будет просто зацикливаться, пока все подсписки не станут пустыми:

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

Тестирование:

> (list-tuples '((m n o) (1) (x y)))
'((m 1 x) (n () y) (o () ()))
> (list-tuples '())
'()
person uselpa    schedule 06.10.2015