объединение и извлечение списков - PullRequest
Новая
       0

объединение и извлечение списков

3 голосов
/ 23 февраля 2012

Я пишу функцию, которая объединяет два списка.Если один из элементов списка является списком, мне нужно извлечь его тоже. 

list1:'(1 (2 3 4) 5 6)) 

list2: '(7 (8 9) 10 (11))

output: (1 2 3 4 5 6 7 8 9 10 11)

Я пытался решить его с помощью своего кода, не работает.В чем проблема? 

(define (merge lis1 lis2)
    (define (combine lis fine)
        (cond
            ((null? lis) lis)
            ((list? lis) (combine (car lis) fine) (combine (cdr lis) fine))
            (else  (cons lis fine))))

        (cond
            (combine (cons lis2 lis1) '())))

1 Ответ

10 голосов
/ 23 февраля 2012

Самый простой способ - просто использовать библиотечную функцию flatten. 

(define (merge lis1 lis2)
  (flatten (cons lis1 lis2)))

flatten берет список, который может содержать списки (который, в свою очередь, может содержать больше списков, ...) исводит результат в список не-списков, что, похоже, пытается сделать ваша функция объединения.

(flatten '(1 2 (3 (4 5) 6))) возвращает '(1 2 3 4 5 6)

Если эта библиотечная функция отключенаваш код на самом деле очень близок к правильному.

Первая проблема в строке ((list? lis) (combine (car lis) fine) (combine (cdr lis) fine) ).fine никогда не изменяется, поэтому код оценивает (combine (car lis) fine) и затем возвращает (combine (cdr lis) fine), где fine во втором выражении является исходным значением fine.Эта строка - то же самое, что ((list? lis) (combine (cdr lis) fine) ), что явно не то, что мы хотим.Вместо этого мы должны использовать первое выражение внутри второго выражения ((list? lis) (combine (cdr lis) (combine (car lis) fine))).

Вторая проблема заключается в том, что в комбинате, когда lis равен нулю, нам нужно вернуть fine, а не lis.

Следующая проблема заключается в том, что этот код проходитсписок, берет первый элемент lis и помещает его в начало fine, а затем передает вновь созданный список и использует его для следующей итерации функции, где он принимает второе значение в lis ивставляет его перед новым fine, перед первым значением lis.Результаты в порядке возврата значения fine - (merge '(1 2 (3)) '(4 (5 6))) вернет (6 5 4 3 2 1).У нас есть два варианта: мы можем вызвать reverse при возврате из combine в теле merge или инвертировать строку, которую мы изменили выше, и сделать ее ((list? lis) (combine (car lis) (combine (cdr lis) fine))).Это означает, что мы добавили бы остальную часть списка к fine перед добавлением текущего элемента, чего мы и хотим.

Другая проблема заключается в том, что нам нужно использовать минусы lis1 до lis2, а ненаоборот.

Последняя проблема в том, что cond в теле merge не нужно - мы можем удалить его.

Как примечание стороны, это обычноСчитается, что лучше не давать закрывающим скобкам новую строку и делать отступ для тела define или cond всего двумя пробелами.

Со всеми этими изменениями окончательный код будет: 

(define (merge lis1 lis2)
  (define (combine lis fine)
    (cond
      ((null? lis) fine)
      ((list? lis) (combine (car lis)
                            (combine (cdr lis) fine)))
      (else  (cons lis fine))))

  (combine (cons lis1 lis2) '()))
...