爲什麼這個打印反向？

(define (square-list items) 
    (define (iter things answer) 
    (if (null? things) 
     answer 
     (iter (cdr things) 
       (cons (square (car things)) 
        answer)))) 
    (iter items nil))

當我進入爲什麼這個打印反向？

(square-list (list 1 2 3 4))

返回（16 9 4 1） - 這是爲什麼落後？

來源

2013-02-28 user2036340

您使用尾遞歸構建輸出列表，對於這一點，你在answer通過在追加積累頭目的名單。自然，這將產生一個相反的列表。您有固定這幾個選項，一個是開溝尾遞歸：

(define (square-list items) 
    (if (null? items) 
     nil 
     (cons (square (car items)) 
      (square-list (cdr items)))))

其他，處理之前扭轉名單：

(define (square-list items) 
    (define (iter things answer) 
    (if (null? things) 
     answer 
     (iter (cdr things) 
       (cons (square (car things)) 
        answer)))) 
    (iter (reverse items) nil))

還有另一個選擇：在最後追加的要素，而不是consing他們：

(define (square-list items) 
    (define (iter things answer) 
    (if (null? things) 
     answer 
     (iter (cdr things) 
       (append answer 
         (list (square (car things))))))) 
    (iter items nil))

每個選項都有自己的權衡，雖然：

第一個選項是不是尾遞歸（雖然它是tail-recursive modulo cons）
第二個選項需要一個額外的穿越和一個額外的列表（發生這種情況時，該列表是相反的）
第三個選項是二次的，因爲每個追加操作遍歷列表中添加元素的末尾

所有考慮的事情，最好的尾遞歸選項將是第二個。

來源

2013-02-28 01:29:16

問題是您的cons聲明。

(cons (square (car things)) answer)

要：如果從切換順序

~~(cons answer (square (car things)))~~

你的名單將在您希望的順序出來。

我總覺得這是一個容易得多，這樣寫：

(define (square-list2 items) 
    (square-list-helper items '()) 
) 

(define (square-list-helper items squares) 
    (cond 
    [(empty? items) squares] 
    [else (append 
      squares 
      (square-list-helper (cdr items) (list (square (car items)))))] 
    ) 
)

來源

2013-02-28 01:20:15

不是真的，因爲'answer'是一個列表。如果你這樣做，你需要「附加」而不是「cons」。 – Barmar 2013-02-28 01:21:44

@Barmar我在'append'上收到一條錯誤消息，因爲您建議我使用它。 – 2013-02-28 01:34:19

我不打算簡單地將'cons'改爲'append'，我的意思是你需要正確使用'append'（通過將新元素包裝在列表中）。 – Barmar 2013-02-28 01:36:05

看兩個元素的簡單情況：

(square-list '(2 3))

這導致：

(iter '(3) 
     (cons (square 2) nil))

(iter '(3) '(4))

然後遞歸調用的作用：

(iter '() 
     (cons (square 3) '(4))

(iter '() '(9 4))

這將然後調用的iter基礎情況，這只是返回answer。

所以它是通過加強在前進方向的名單，但因爲每個元素處理的方形被放在answer列表前，所以結果是倒着建。

簡單的修復方法就是改變(cons (square (car things)) answer)到：

(append answer (list (square (car things))))

這使新的結果在最後，而不是開始。但是，這通常被認爲是一種糟糕的做法，因爲它必須每次都重建結果列表，複製O（n）個元素。

來源

2013-02-28 01:30:40 Barmar

你是在錯誤的順序：首先遞歸處理列表的其餘部分，然後處理當前元素的結果。這將在處理它的同時逆轉你的列表。試試這個：

(define (square-list items) 
    (define (iter things answer) 
    (if (null? things) 
     answer 
     (iter (cdr things) 
      (append answer (list (square (car things))))))) 
(iter items (list)))

來源

2013-02-28 01:30:45

爲什麼這個打印反向？

回答

相關問題