Exercise 2.18 asks us to define a procedure
reverse that takes a list as its argument and returns a list with the same elements in reverse order.We'll be using the
append procedure given in the text which takes two lists and appends the second list to the end of the first:(define (append list1 list2)
(if (null? list1)
list2
(cons (car list1) (append (cdr list1) list2))))
We can reverse a list by appending the
car of the list to the reverse of the cdr of the list. (See how easy it is to start thinking in Scheme?) In other words, we just move the first item to the end of the list after reversing the remaining items. This means reverse will make a recursive call to itself, so we also need a base case to make the recursion stop. We can just stop when we reach an empty list.(define (reverse items)
(if (null? items)
items
(append (reverse (cdr items)) (list (car items)))))
Once again, we can test it out with a few example lists from the text.
> (reverse (list 1 2 3 4))
(4 3 2 1)
> (reverse (list 1 4 9 16 25))
(25 16 9 4 1)
> (reverse (list 1 3 5 7))
(7 5 3 1)
> (reverse (list 23 72 149 34))
(34 149 72 23)
Related:
For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.
5 comments:
Hi, Bill! FYI, these posts on SICP are incredibly helpful - thanks for taking the time to do this.
This was my solution to the exersize:
(define (reverse l)
(define (iter a r)
(if (null? a)
r
(iter (cdr a)
(cons (car a)
r))))
(iter l '()))
I never thought to use APPEND - I have become too accustomed to the 'hints' in the exersizes.
I couldnt do reverse list when I was reading SICP text and attempted the exercise, then I started reading the book 'The little schemer' and after chapter two, knew cons enough superficially to produce the exact logic as M.
M's solution is actually more efficient than Bill's one, since the complexity of the former is O(N) whereas the complexity of the latter is O(N^2). The APPEND procedure is O(N) (where N is the first list's length), and Bill's solution uses it O(N) times.
In JavaScript:
function reverse(ls) {
return is_null(tail(ls))
? ls
: append(reverse(tail(ls)), list(head(ls)));
}
Without append i've got this:
(define (rev l)
(define (recur count)
(if (or (null? l) (< count 0))
'()
(cons (list-ref l count)
(recur (- count 1)))))
(recur (- (length l) 1)))
Post a Comment