球拍/計劃拼合說明

Question

有人可以幫助我準確地分解下列版本拼合的執行順序嗎？我正在使用Racket。

版本1，是來自球拍本身，而版本2更常見？實現。現在

(define (flatten1 list) 
    (let loop ([l list] [acc null]) 
    (printf "l = ~a acc = ~a\n" l acc) 
    (cond [(null? l) acc] 
      [(pair? l) (loop (car l) (loop (cdr l) acc))] 
      [else (cons l acc)]))) 

(define (flatten2 l) 
    (printf "l = ~a\n" l) 
    (cond [(null? l) null] 
     [(atom? l) (list l)] 
     [else (append (flatten2 (car l)) (flatten2 (cdr l)))])) 

，運行與第一實施例「（1 2 3）生產：

l = (1 2 3) acc =() 
l = (2 3) acc =() 
l = (3) acc =() 
l =() acc =() 
l = 3 acc =() 
l = 2 acc = (3) 
l = 1 acc = (2 3) 
'(1 2 3) 

而第二生產：

l = (1 2 3) 
l = 1 
l = (2 3) 
l = 2 
l = (3) 
l = 3 
l =() 
'(1 2 3) 

執行的順序似乎不同。在第一個示例中，它看起來像第二個循環(loop (cdr l) acc)在'（2 3）'正在立即打印之後在第一個循環之前觸發。而在第二個例子中，在'（2 3）之前打印1，這看起來是第一個要在append內部變平的調用，首先進行評估。

我正在通過Little Schemer，但這些都是比較困難的例子，我真的可以使用一些幫助。

非常感謝。

Answer 1

的主要區別是這樣的：

• flatten1作品（從cdr側第一，然後從car側）存儲輸出元件到蓄電池。這是有效的，因爲列表是從右到左構建的，所以首先在cdr一側工作是正確的。
• flatten2通過遞歸地將car和cdr兩側展平，然後append將它們一起工作。

flatten1比較快，特別是如果樹是在car側重：利用蓄能意味着沒有多餘的列表複製，不管是什麼。而append調用flatten2會導致append的左側被複制，這意味着如果car側的樹很重，則會有大量額外的列表複製。

所以總的來說，我會考慮flatten2一個初學者實施扁平化，並且flatten1一個更加精美的專業版本。另請參閱my implementation of flatten，其使用與flatten1相同的原則工作，但使用左側摺疊而不是flatten1使用的右側摺疊。 （左邊的解決方案使用更少的堆棧空間，但可能會有更多的堆空間，右邊的解決方案使用更多的堆棧並且通常堆少，儘管快速閱讀flatten1表明在這種情況下，堆使用率大約是與我的實施相同。）

Answer 2

不是你的問題的答案（克里斯提供了一個很好的答案！），但爲了完整性這裏是另一種方式來實現flatten，類似於flatten2但有點更簡潔：

(define (atom? x) 
    (and (not (null? x)) 
     (not (pair? x)))) 

(define (flatten lst) 
    (if (atom? lst) 
     (list lst) 
     (apply append (map flatten lst)))) 

而另一種方式來實現左倍版本（與更多的共同點，以flatten1）使用標準球拍程序：

(define (flatten lst) 
    (define (loop lst acc) 
    (if (atom? lst) 
     (cons lst acc) 
     (foldl loop acc lst))) 
    (reverse (loop lst '())))