Exercise 2.17 asks us to define a procedure
last-pair that returns a list that contains only the last element of a given (non-empty) list.Earlier in SICP section 2.2.1 we saw that a list is represented in Scheme as a chain of pairs.
Our new procedure needs to return a list, so we need to be careful not to simply return the last value in the list, or even the last pair.
There are several correct ways to do this, but here's a recursive solution (based on the
length example from the text) that uses the method of "cdring down" the list.(define (last-pair items)
(if (null? (cdr items))
(list (car items))
(last-pair (cdr items))))
The first line checks to see if the
cdr of the list of items passed in is nil. If it is, the second line creates a new list from the car of the items. If not, the last line makes a recursive call to last-pair with the remaining items in the list.We can verify that it works by testing it with several of the example lists from the chapter.
> (last-pair (list 1 2 3 4))
(4)
> (last-pair (list 1 4 9 16 25))
(25)
> (last-pair (list 1 3 5 7))
(7)
> (last-pair (list 23 72 149 34))
(34)
Related:
For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.
3 comments:
You can return items rather than (list (car items)) because items itself is a list
bakerba,
You're right, but it wasn't immediately obvious why. I was wrapping (car items) in list because the car is just one element. But once you've determined that the cdr is null in the step before, then the entire list must just have one element (or none, or it's not a list at all).
Thanks a lot for pointing that out.
Another way to do this is:
(define (last-pair items)
(list (list-ref items (- (length items) 1))))
However, this is inefficient as this traverses the list many times.
Post a Comment