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

Question

Я читаю раздел 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. (без использования функции сгиба)?

Answer 1

В принципе, как работает процедура выглядит так:

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