Scheme將元素添加到列表的末尾

Question

如何在只有cons，first，rest和empty時將元素添加到列表末尾（空之前） ？並且可以使用cond遞歸

Answer 1

想想你將如何實現append（或者更一般地說，考慮如何實現一個正確的摺疊）。現在，如果您將一個列表附加到包含要添加元素的單例列表中，那麼您基本上已添加了您的元素。

（很顯然，這是O（n），所以不要添加元素逐一這種方式。）

---

下面是一個使用對摺的解決方案：

(define (append-element lst elem) 
    (foldr cons (list elem) lst)) 

和解決方案使用append：

(define (append-element lst elem) 
    (append lst (list elem))) 

因此，如果您可以實現foldr或append自己，使用你列出的操作（很簡單！嘗試它），你很好去。

P.S.事實上，你可以使用對摺執行append：

(define (append lst1 lst2) 
    (foldr cons lst2 lst1)) 

但仍然讓你實現自己foldr。 ;-)（提示：它很容易看my implementation of left-fold開始的想法。）

Answer 2

這看起來像功課，所以我給你一些指點，讓你步入正軌，填充了空白：

(define (add-last lst ele) 
    (cond ((empty? lst) ; if the list is empty 
     <???>)   ; create a one-element list with `ele` 
     (else   ; if the list is non-empty 
     (cons <???>  ; cons the first element in the list 
       <???>)))) ; with the result of advancing the recursion 

以上可以在cons，first，rest，empty?和cond方面來實現，無需其它程序。