recursive function that returns true/false (newbie stuff) 
Author Message
 recursive function that returns true/false (newbie stuff)

I've been using LISP a total of 3 days now, and I'm still waiting for my
big reference book to come in, so I'm swimming in murky waters here.  I have
two questions regarding the following code (which seems to work fine, but just
doesn't seem right):

-----
(defun make-palindrome (lst)
        (append lst (reverse lst)))

(defun is-palindrome (lst)
        (if (null lst)
                'T ;list is empty and is therefore a palindrome
                (if (equal (first lst) (nth (- (length lst) 1) lst))
                        (is-palindrome (reverse (rest (reverse (rest lst)))))
                        'NIL))) ;list is not a palindrome                      
-----

My general question: is this the correct way to implement the return values for
is-palindrome?  Am I returning the correct "booleans" ('T and 'NIL), in the
correct places, and is the recursive part of this implemented efficiently?  

My specific question: this code sucks.  At least, that's what it seems to me
(being a LISP beginner), so does anyone have other suggestions on how to
implement an "is-palindrome" function?  The way it compares first and last
characters seems ugly, and the "(reverse (rest (reverse (rest lst))))" seems
incredibly ugly.  

I'd appreciate any tips anyone can provide.  The specific variant of LISP that
I'm using is AKCL (if that matters).  



Thu, 13 Jul 2000 03:00:00 GMT  
 recursive function that returns true/false (newbie stuff)

* Kevin Goodier
| My general question: is this the correct way to implement the return
| values for is-palindrome?  Am I returning the correct "booleans" ('T and
| 'NIL), in the correct places, and is the recursive part of this
| implemented efficiently?

  well, (EQUAL LIST (REVERSE LIST)) would be a lot more efficient, as well
  as answering the question right away, although it, too, does two list
  traversals.  can you determine whether a list is palindromatic in one
  pass, or do you need at least two?  how about a vector?  how many passes
  do _you_ make over the list?

  also consider whether "x" is a degenerate palindrome and needs a special
  case, or does it just help efficiency to add one?

#:Erik
--
The year "98" was new 1900 years ago.  |  Help fight MULE in GNU Emacs 20!
Be year 2000 compliant, write "1998"!  |  http://sourcery.naggum.no/emacs/



Thu, 13 Jul 2000 03:00:00 GMT  
 recursive function that returns true/false (newbie stuff)

Erik Naggum says...

Quote:
>| My general question: is this the correct way to implement the return
>| values for is-palindrome?  Am I returning the correct "booleans" ('T and
>| 'NIL), in the correct places, and is the recursive part of this
>| implemented efficiently?

>  well, (EQUAL LIST (REVERSE LIST)) would be a lot more efficient, as well

See, this is the kind of silly thing that I missed!  Yeah, you're right, that
*would* work.  I for some reason assumed that the comparison had to be
performed character by character.  If I understand correctly, EQUAL is the only
equality operator that will work in this case?

Quote:
>  as answering the question right away, although it, too, does two list
>  traversals.  can you determine whether a list is palindromatic in one
>  pass, or do you need at least two?  how about a vector?  how many passes
>  do _you_ make over the list?

The only other method I could think of was to find the mid point of the list,
split it into halves, reverse one of those halves, and then compare them.  This  
solution wouldn't be any better than what you mentioned above, though.  

Efficiently is not a concern for this particular problem, but one thing that
could help would be to check if the list length is odd.  If so, it isn't a
palindrome.  So, out of curiousity, how would one check for an odd number in
LISP?  Is there a mod operator?

------------->
     Kevin Goodier

     http://students.cec.wustl.edu/~bkg2/



Thu, 13 Jul 2000 03:00:00 GMT  
 recursive function that returns true/false (newbie stuff)

* Kevin Goodier
| I for some reason assumed that the comparison had to be performed
| character by character.

  yes, that is of course true.

| If I understand correctly, EQUAL is the only equality operator that will
| work in this case?

  well, no, if this is a string (REVERSE works on strings, no need to use a
  list), you have a choice of EQUAL, EQUALP, STRING=, and STRING-EQUAL.

| Efficiently is not a concern for this particular problem, but one thing
| that could help would be to check if the list length is odd.  If so, it
| isn't a palindrome.

  a palindrome is a word (or phrase) that reads the same either way.
  often, a phrase is considered palindromatic if the letters used are the
  same either way, regardless of interspersed punctuation.  Guy L. Steele
  in Common Lisp the Language, 2nd edition, had great fun with a longer
  version of a traditional palindrome one (thanks to Digital Press for
  releasing the sources):

 "A man, a plan, a canoe, pasta, heros, rajahs, a coloratura, maps, snipe,
  percale, macaroni, a gag, a banana bag, a tan, a tag, a banana bag again
  (or a camel), a crepe, pins, Spam, a rut, a Rolo, cash, a jar, sore hats,
  a peon, a canal--Panama!"

| So, out of curiousity, how would one check for an odd number in LISP?  Is
| there a mod operator?

  yes, but ODDP and EVENP are slightly more intuitive.

#:Erik
--
The year "98" was new 1900 years ago.  |  Help fight MULE in GNU Emacs 20!
Be year 2000 compliant, write "1998"!  |  http://sourcery.naggum.no/emacs/



Fri, 14 Jul 2000 03:00:00 GMT  
 recursive function that returns true/false (newbie stuff)

* Kevin Goodier
| Efficiently is not a concern for this particular problem, but one thing
| that could help would be to check if the list length is odd.  If so, it
| isn't a palindrome.

* Erik Naggum
| a palindrome is a word (or phrase) that reads the same either way.

  I forgot that the point of that sentence was to say "it makes no
  difference whether something that reads the same both ways has odd or
  even length".  in other words, "v", "eve", "level", etc, are all
  palindromatic.  you code actually catches it, but rather inefficiently,
  which is why I suggested that you might need to detect it.  see for
  yourself what it does with a singleton list...

#:Erik
--
The year "98" was new 1900 years ago.  |  Help fight MULE in GNU Emacs 20!
Be year 2000 compliant, write "1998"!  |  http://sourcery.naggum.no/emacs/



Fri, 14 Jul 2000 03:00:00 GMT  
 recursive function that returns true/false (newbie stuff)

* Kevin Goodier

Quote:
> | My general question: is this the correct way to implement the return
> | values for is-palindrome?  Am I returning the correct "booleans" ('T and
> | 'NIL), in the correct places, and is the recursive part of this
> | implemented efficiently?
>   well, (EQUAL LIST (REVERSE LIST)) would be a lot more efficient, as well
>   as answering the question right away, although it, too, does two list
>   traversals.  can you determine whether a list is palindromatic in one
>   pass, or do you need at least two?  how about a vector?  how many passes
>   do _you_ make over the list?

If I was being really nerdy, I think I'd argue that the best way to do
it is to copy the list into a vector & then work on the vector -- you
should cons less because vectors ought to be more compact than lists
(no cdr pointers), and you can then avoid half the work EQUAL does
too.  But that's kind of a C micro-optimisation position.

--tim



Fri, 14 Jul 2000 03:00:00 GMT  
 recursive function that returns true/false (newbie stuff)

Quote:

> My general question: is this the correct way to implement the return values for
> is-palindrome?  Am I returning the correct "booleans" ('T and 'NIL), in the
> correct places, and is the recursive part of this implemented efficiently?

To answer the part of your question nobody has answered yet, t and nil, when
quoted, return themselves.  For example,

(eq t 't)

and

(eq nil 'nil)

both return true.  Your use of the quote operator is redundant.



Fri, 14 Jul 2000 03:00:00 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. If Observable#notify_observers returned true/false then false could imply veto of change

2. why is true and false = true ?

3. Newbie question: Bool Function returns neither True nor False?

4. 0.1 + 0.2 + 0.7 = 1.0 ( true or false )

5. True/False In dictionary +

6. true/false 1/0 - please help

7. True or false with Tintools

8. FALSE EQUATE(NOT TRUE)????

9. Check Box Properties in Dictionary does not retain True/False value

10. Should /SAVESTOREDPROC = FALSE or TRUE?

11. TRUE or and FALSE,...

12. Saving data from a True False Structure

 

 
Powered by phpBB® Forum Software