Итерационная программа для добавления списков в схему

Я читаю раздел 2.2 в SICP, где в книге представлена ​​процедура добавления двух списков. Я пытаюсь реализовать добавление с помощью итерации.

Это мой код:

(define (append list1 list2)
  (define (append-iter item1 reversed-item1 result)
    (if (null? item1)
      (if (null? reversed-item1)
        result
        (append-iter item1 
                     (cdr reversed-item1) 
                     (cons (car reverse) result)))
      (append-iter (cdr item1) 
                   (cons (car item1) reversed-item1) 
                   result)))
  (append-iter list1 '() list2))

Хотя это работает, но количество итераций вдвое превышает длину list1. Существует ли решение, число итераций которого равно длине list1. (без использования функции складывания)?


linked-list scheme sicp
person Xiaojun Chen    schedule 15.02.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

В основном, как работает ваша процедура, так:

(define (append l1 l2)
  (define (reverse-append rev app)
    (if (null? rev)
        app
        (reverse-append (cdr rev) 
                        (cons (car rev) app))))
  (reverse-append (reverse l1) l2))

Это O (N), но это тратит немного памяти, так как (reverse l1) пространство используется только для итерации. Если вам действительно нужно исправить это, вам нужно использовать мутацию:

(define (append-iter . rest)
  (let ((result (list 1)))
    (let loop ((p result) (lst '()) (rest rest))
      (cond
        ((not (null? lst))
         (set-cdr! p (list (car lst)))
         (loop (cdr p) (cdr lst) rest))
        ((null? rest) (cdr result))
        ((null? (cdr rest))
         (set-cdr! p (car rest))
         (cdr result))
        (else (loop p (car rest) (cdr rest)))))))
person Sylwester    schedule 15.02.2016