Scheme add element to the end of list

Question

How can you add an element to the end of a list (before the empty) when only cons, first, rest, empty? and cond recursions can be used

Solution 1

Think about how you would implement append (or, more generally, think about how you would implement a right-fold). Now, if you append a list to a singleton list containing your element-to-add, you've basically appended your element.

(Obviously, this is O(n), so don't add elements individually this way.)

---

Here's a solution using a right-fold:

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

and a solution using append:

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

So if you can implement either foldr or append yourself, using the operations you've listed (it's easy! try it), you're good to go.

P.S. In fact, you can implement append using a right-fold:

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

but that still leaves you to implement foldr yourself. ;-) (Hint: it's easy. Look at my implementation of left-fold for starting ideas.)

Solution 2

This looks like homework, so I'll give you some pointers to get you right on track, fill-in the blanks:

(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

The above can be implemented in terms of cons, first, rest, empty? and cond, no other procedures are needed.