Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Scheme append procedure

Tags:

append

scheme

I'm having trouble appending a list to another list. Below is my code. When I run (append '(1 2) '(3 4)) I get '(1 3 2 4).

I want the output to be '(1 2 3 4)

(define (append l m)
 (if (null? l) '()
  (cons (car l) (append m (cdr l)))))

Thanks

like image 825
Chris McKnight Avatar asked Dec 04 '10 22:12

Chris McKnight


People also ask

What are the differences between cons list and append?

In terms of big O notation, cons usages are generally O(1) while append is O(n) where n is the length of the list you are dealing with. While (append (list first_elem) existing_list) technically has the same big O with (cons first_elem existing_list), the latter is more concise and faster.

What is member in Scheme?

member is a function that treats a list as a set. It returns true if the item is found in the list, and false otherwise.

How do I check if a list is empty in Scheme?

Scheme provides a procedure, null? to check whether a value is (a pointer to) the empty list, i.e., a null pointer. For example, (null? foo) returns #t if the value of the variable foo is the empty list, and #f otherwise.

How does reverse work in Scheme?

reverse returns a reversed copy of a list. There's an easy (but slow) way to define reverse in terms of append . We just take the first element off the list, reverse the rest of the list, and append the first element to the end of the list.


1 Answers

Well by switching the two lists around like that (switching the position of m and l when calling append recursively), you'll get the first item of the first list followed by the first item of the second list etc.

If you don't want that, you should keep l as the first argument and m as the second. So you get:

(define (append l m)
 (if (null? l) '()
  (cons (car l) (append (cdr l) m))))

Of course this doesn't work as wanted either, because now you only get the first list back and nothing is appended at all. What you need to do is, once the first list is fully appended (i.e. once l is empty), you need to return the second one as the tail, like this:

(define (append l m)
 (if (null? l) m
  (cons (car l) (append (cdr l) m))))
like image 111
sepp2k Avatar answered Oct 01 '22 04:10

sepp2k