SCHEME - Writing my own append produces a weird re

问题:

I want to write my own append , for appending an element to an existing list .

I've written the following :

(define (appendElem llist elem)
    (if (null? llist)
        elem
        (cons (car llist) (appendElem (cdr llist) elem))))

But when I do this :

(appendElem (list 1 2 30) 11)

I get :

(1 2 30 . 11)

So the question is , why (1 2 30 . 11) and not (1 2 30 11) ?

Thanks

EDIT:

Fixed :

(define (appendElem llist elem)
    (if (null? llist)
        (list elem)
        (cons (car llist) (appendElem (cdr llist) elem))))

回答1:

Think about what you want your base case to be. Do you want just elem, or do you want a list with the single item elem? There is a difference. If the want the latter, you will need to fix your base case in the code.

In other words, do you want (appendElem '() 42) to return 42, or (42)? Think carefully about the answer to that question, then think about what the consequence of each choice is.

By the way, while you can implement appendElem as a toy, you'll soon realise that that function has O(n) runtime. So do not build lists using this approach! The standard way to build a list is to cons items to it, then reverse the final resulting list.

回答2:

Here is the answer :

(define (appendElem llist elem)
    (if (null? llist)
        (list elem)
        (cons (car llist) (appendElem (cdr llist) elem))))

Thanks to @Chris Jester-Young .

回答3:

Another suggestion for you:

(define (make-dl ls)      ; turn a list into a difference list
  (cons ls (last-pair ls)))

(define (snoc-dl! dl e)   ; snoc ~ appendElem, destructively
  (set-cdr! (cdr dl) (list e))
  (set-cdr! dl (cddr dl)))

(define (dl-list dl)      ; get the list back
  (car dl))

for an O(1) appending at list's end (well, calling make-dl will be O(n), but all the subsequent appends will take O(1) time).