reversing a list

Discussion of Scheme and Racket

reversing a list

Postby dsjoka » Tue Feb 15, 2011 8:41 am

Ok so I need to remove the last item of a list.

ie : (1 2 3 4)
I will get
(1 2 3)

my idea is as follows:

reverse(list)
car(list)
reverse(list)

however I don't know if there is simple function in scheme(racket) that does reverse?

If not, is there an easier way to approach this problem?

Thanks.
dsjoka
 
Posts: 14
Joined: Thu Feb 10, 2011 1:30 pm

Re: reversing a list

Postby gugamilare » Tue Feb 15, 2011 12:27 pm

You idea is ok, but you need to translate it to scheme.

The function reverse does not change its argument, it instead creates a new list and returns it. That is, you have to write:
Code: Select all
(setf list (reverse list))

Note the parenthesis surrounding the name of the function and its argument, not only its argument.

About car, you got it wrong. The function car returns the first element, not the tail of the list. What you want is cdr. And you need to use setf again, because cdr does not change its argument, it just returns the correct value:
Code: Select all
(setf list (cdr list))

I think this is enough for you to get the idea. Good luck!
gugamilare
 
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil

Re: reversing a list

Postby MadMuppet006 » Tue Nov 08, 2011 3:25 pm

Code: Select all
(define reverse-list
  (lambda ( l )
    (define lasts
      (lambda ( l )
   (cond
    ((null? (cdr l))(car l))
    (else
     (lasts (cdr l))))))
    (define onleft
      (lambda ( l )
   (cond
    ((null? (cdr l))(quote ()))
    (else
     (cons
      (car l)
      (onleft (cdr l)))))))
    (cond
     ((null? (cdr l))
      (cons (car l)()))
     (else
      (cons (lasts l)
       (reverse-list (onleft l)))))))


thats how I did it ..
not the best but but it does work.
MadMuppet006
 
Posts: 4
Joined: Wed Nov 02, 2011 11:56 pm

Re: reversing a list

Postby saulgoode » Wed Nov 09, 2011 7:06 am

Like most Schemes, Racket provides a 'reverse' procedure.

Your approach to reversing a list is basically sound, but you are performing some unnecessary steps (and it would be better if it handled the case of an empty list).

The traditional Scheme way of defining a function that loops through a list and returns some result (such as the reversed list) is to define an iteration function which accepts one additional argument, the result to be returned. Each iteration through the list, the result gets updated based upon the first item in the list and then the iteration repeats with the remainder of the list..

Code: Select all
(define (reverse-list-iter lis result)
  (if (null? lis)
    result
    (reverse-list-iter (cdr lis) (cons (car lis) result)) ))


Your function will then call this iteration function with an appropriate initial value for the result (in your case, the empty list).
Code: Select all
(define (reverse-list lis)
  (reverse-list-iter lis '()) )


Of course, it makes sense to nest the definition of the iteration function within your function, to keep things organized and to avoid cluttering up your namespace.

Code: Select all
(define (reverse-list lis)
  (define (iter lis result)
    (if (null? lis)
      result
      (iter (cdr lis) (cons (car lis) result)) ))
  (iter lis '()) )


And by having your reverse function handle an empty list (returning an empty list), your "last item removal" function becomes almost trivial. (And of course, you could just use the standard 'reverse' function instead.)

Code: Select all
(define (butlast lis)
  (if (null? lis)
    '()
    (reverse-list (cdr (reverse-list lis))) ))
saulgoode
 
Posts: 43
Joined: Tue Dec 14, 2010 1:39 am


Return to Scheme

Who is online

Users browsing this forum: No registered users and 1 guest