在方案中使用兩個遞歸調用函數轉換函數使其成爲尾遞歸

Question

在我開始之前：YES，這是來自大學的作業。在我被告知我是懶惰和邪惡的之前：作業的這一部分是轉換我們已有的兩個功能，這一個是第六個。

(define (flatten-list a-list) 
    (cond ((null? a-list) '()) 
     ((list? (car a-list)) 
     (append (flatten-list (car a-list)) (flatten-list (cdr a-list)))) 
     (else (cons (car a-list) (flatten-list (cdr a-list)))))) 

正如你所猜測的那樣，即使它是嵌套的，該函數也會展平一個列表。我的具體轉換問題出現在（list？（car a-list））條件中，其中我正在執行兩個遞歸調用。我已經做了斐波那契，我可以通過在尾遞歸上只有兩個「acummulators」來做到這一點。但是，我的頭腦沒有接受過這方面的培訓，但卻不知道應該如何去做。

如果給我提示而不是結果，我將不勝感激。謝謝！

Answer 1

這裏是我的解決方案：

(define (flatten-iter a-list) 
    (define (flat-do acc lst-interm lst) 
    (cond 
     ((null? lst) 
     (reverse acc)) 
     ((and (list? lst-interm) (not (null? lst-interm))) 
     (flat-do acc (car lst-interm) (append (cdr lst-interm) lst))) 
     ((not (list? lst-interm)) 
     (flat-do (cons lst-interm acc) empty lst)) 
     ((list? (car lst)) 
     (flat-do acc (car lst) (cdr lst))) 
     (else 
     (flat-do (cons (car lst) acc) empty (cdr lst))))) 
    (flat-do empty empty a-list)) 

(flatten-iter (list 1 (list 2 (list 3 4 (list 5 empty 6))) 7 8)) 
=> (1 2 3 4 5 6 7 8) 

尾recrusive功能要求，他們不會再回來，這樣的話你不能用於存儲程序的狀態使用堆棧。而是使用函數參數在函數調用之間傳遞狀態。因此，我們需要確定如何維持這個狀態。由於我們的功能的結果是list?，所以增加一個empty列表是有意義的;我們正在爲此使用acc。你可以看到它在else分支上面如何工作。但是我們應該能夠處理嵌套列表。而且，當我們進一步深入時，我們應該保留嵌套列表的其餘元素以供進一步處理。示例列表：(list 1 (list 2 3) 4 5)

直到(list 2 3)我們已經將1添加到累加器。由於我們不能使用堆棧，我們需要其他地方來存儲列表的其餘元素。而這個地方是lst的參數，其中包含要扁平化的原始列表的元素。我們只需appendlst其餘元素(cdr (list 2 3))這是(list 3)，並繼續清單的頭，我們無意中扁平化，即我。即（汽車（名單2 3）），這只是2。現在，(and (list? lst-interm) (not (null? lst-interm)))成功，因爲flat-do被稱爲是這樣的：

(flat-do (list 1) (list 2 3) (list 4 5)) 

和條件觸發此代碼：

(flat-do (list 1) (car (list 2 3)) (append (cdr (list 2 3)) (list 4 5))) 

再次flat-do被稱爲是這樣的：（平-DO（表1）2（名單3 4 5））

條件(not (list? 2))現在成功並且代碼(flat-do (cons 2 1) empty (list 3 4 5))進行評價。

其餘處理與else分支做，直到lst是null?和reverse上acc執行。函數然後返回反向累加器。