Fedora Linux Support Community & Resources Center
  #1  
Old 14th June 2012, 10:16 AM
kernan373
Guest
 
Posts: n/a
windows_7chrome
Question If you know Lisp/Scheme, I need assistance (specifically in Racket)

Hey all,

I'm trying to write a function in Racket to reverse a list, including the lists within the list. The input should be one list and the output should be the reversed list.

I made a function that reverse a list's elements without going into the lists within the lists.
so
Code:
(simple-reverse (list 1 2 (list 'a 'b 'c) 3 4))
would return:
Code:
(list 4 3 (list 'a 'b 'c) 2 1)
Here's what I have so far of the function I want to make:

Code:
(define reverse-function
  (lambda (L)
    (cond
      ((empty? L) empty)
      ((list? (first L)) (cons (reverse-function (first L)) (reverse-function (rest L))))
      (else (cons (first L) (reverse-function (simple-reverse (rest L)))))))
The output expected from input (list 1 2 3 (list 'a 'b 'c) 4 5) should be (list 5 4 (list 'c 'b 'a) 3 2 1). How do I go about doing this? what am I doing wrong?
Reply With Quote
  #2  
Old 17th June 2012, 09:36 AM
SaGS Offline
Registered User
 
Join Date: Nov 2006
Posts: 135
windows_xp_2003opera
Re: If you know Lisp/Scheme, I need assistance (specifically in Racket)

Although I don’t know Racket, I hope the following few comments might help a bit:

(A)
Quote:
(reverse-function (simple-reverse (…))
If reverse-function did what it is supposed to do, and since simple-reverse also reverses the top level of the list, then the 2 function calls cancel each other from the point of view of the top level of the argument. Why do you apply one to the result of the other?

(B)
In 2 places you have something similar to
Quote:
(cons (… first L) (… rest L))
so the order of the top level elements does not change.

(C)
Why exactly do you want to derive reverse-function from simple-reverse, as opposed to implementing the reversing from scratch?

Certainly this does not avoid iterating through all elements, because simple-reverse does not care about nested lists and while it processes a list you do not know there are such ones to handle them yourself. If you absolutely want to use simple-reverse (as in an assignment that explicitly requires this), you could:
  1. Iterate through all top level elements of the list received as an argument.
  2. Call your reverse-function recursively on each such element that is a list; the atoms are left unchanged.
  3. Collect all these results (atoms + deep-reversed nested lists) into a list, in the original order. Note this list is almost what you want, except the top level is not yet reversed.
  4. Apply simple-reverse to the list obtained in the previous step.

(D)
But if you have to iterate through all elements, at all levels, why bother with simple-reverse?

A small change to (C) allows you to get the result you want directly: while collecting the results in the 3rd step, put them in a list in reverse order. Then the 4th step isn’t necessary anymore, less memory is used (there’s no need to allocate the intermediary almost-fully-reversed list) and the reversing should be faster.

I’ve done the 2 in Lisp as an exercise, and the complexity is comparable. The difference came from making the ‘from scrach’ version to work with ‘improper lists’ (those who’s last cdr is not NIL, like (a b c . d)); the Lisp reverse function (which seems to correspond to your simple-reverse) does no work with such constructs, and I didn’t bother to implement a workaround in this case.

Last edited by SaGS; 17th June 2012 at 09:39 AM.
Reply With Quote
Reply

Tags
assistance, lisp, lisp or scheme, racket, recursion, scheme, specifically

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Lisp, the language of the gods. :) dd_wizard Wibble 9 16th January 2010 06:02 PM
Writing GNOME Programs in LISP Quasaur Using Fedora 3 27th November 2009 03:31 PM
How to install CMU Lisp (not the common lisp in fedora repo) on Fedora 10? premudriy Programming & Packaging 10 1st May 2009 06:16 AM
About LISP dludenar Programming & Packaging 2 16th January 2007 02:58 PM
Segfault in GNU Common lisp ajayd Using Fedora 0 9th April 2006 08:07 PM


Current GMT-time: 16:41 (Thursday, 30-10-2014)

TopSubscribe to XML RSS for all Threads in all ForumsFedoraForumDotOrg Archive
logo

All trademarks, and forum posts in this site are property of their respective owner(s).
FedoraForum.org is privately owned and is not directly sponsored by the Fedora Project or Red Hat, Inc.

Privacy Policy | Term of Use | Posting Guidelines | Archive | Contact Us | Founding Members

Powered by vBulletin® Copyright ©2000 - 2012, vBulletin Solutions, Inc.

FedoraForum is Powered by RedHat
Quedlinburg Photos - Birmingham - Oak Hill Photos