Scheme - Appending to the end of a list

user_10934224 0
Viewed 605

I'm very sorry for such a simple question. It's so trivial, I haven't been able to find someone online with this problem. So I'd appreciate some help.

I want to write a very simple function that takes a list and an item, and appends that item to the end of the list.

The function I wrote recursively goes to the end of the list and returns the new item. It's so frustrating that this isn't working. It's the simplest function I've ever seen

(define (my-append lst item)
  (if (null? lst)
    item
    (cons (car lst) (my-append (cdr lst) item))))

(display (my-append (list 1 2 3 4) 5))

This displays

(1 2 3 4 . 5)

I don't know why that dot is there, and it's extremely frustrating. I haven't come across it in any previous SO questions.

I just want to see 

(1 2 3 4 5)

I would really really appreciate some help, because I'm extremely frustrated with this. If it helps, I'm running this code using an online compiler https://repl.it/languages/scheme

append scheme lisp list
2 Answers

You just need to end the recursion with a list, not an item. Instead of this:

(if (null? lst)
    item

Do this:

(if (null? lst)
    (list item)

To clarify - a list in Scheme must end in the empty list '(). If your recursion ends with an item, you'll get something like this in the end:

(cons 4 5)
=> '(4 . 5)

That's a cons pair. A proper list ends in the empty list:

(cons 4 (cons 5 '()))
=> '(4 5)

Which is the same as:

(cons 4 (list 5))
=> '(4 5)

By the way, this is the idiomatic way to append an item at the end:

(define (my-append lst item)
  (append lst (list item)))
user_2013590

The . is there because the last pair in your resulting list doesn't have its cdr pointing to an empty list. A proper list is a chain of pairs where the last cdr in the chain points to an empty list. E.g.

(list 1 2 3 4 5)
# is equivalent to
(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 '()))))

But the list you're creating is

(cons 1 (cons 2 (cons 3 (cons 4 5)))

You get a . in the list for the same reason that (cons 4 5) prints as (4 . 5).

When writing a recursive function, you need to think the following way:

  1. What is the base case of input?
  2. What should the function return for that input?
  3. In non-base cases, how do I simplify the input to get closer to the base?
  4. How do I combine the result of the recursive call with the input?

You got this all right except for step 2.

Consider the base case:

(my-append '() 5)

This should return (5), right? But your function will just return 5. This means that you need to wrap item in a list in the base case.

(define (my-append lst item)
  (if (null? lst)
    (list item)
    (cons (car lst) (my-append (cdr lst) item))))

Note that the built-in append procedure is for appending two lists, not appending a list and a single item. Your function is the correct way to define that function.

user_14918950
Related