From: Kevin Goodier
Subject: recursive function that returns true/false (newbie stuff)
Date: 
Message-ID: <6aei0l$7ko$1@newsreader.wustl.edu>
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).  

From: Erik Naggum
Subject: Re: recursive function that returns true/false (newbie stuff)
Date: 
Message-ID: <3094699721088415@naggum.no>
* 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/
From: Kevin Goodier
Subject: Re: recursive function that returns true/false (newbie stuff)
Date: 
Message-ID: <6ag9t5$oql$1@newsreader.wustl.edu>
Erik Naggum says...
>| 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?


>  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
     ยทยทยทยท@cec.wustl.edu
     http://students.cec.wustl.edu/~bkg2/
From: Erik Naggum
Subject: Re: recursive function that returns true/false (newbie stuff)
Date: 
Message-ID: <3094764034583296@naggum.no>
* 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/
From: Erik Naggum
Subject: Re: recursive function that returns true/false (newbie stuff)
Date: 
Message-ID: <3094767813890115@naggum.no>
* 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/
From: Tim Bradshaw
Subject: Re: recursive function that returns true/false (newbie stuff)
Date: 
Message-ID: <ey37m7n34nr.fsf@todday.aiai.ed.ac.uk>
* Erik Naggum wrote:
* 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?

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
From: Bruce Tobin
Subject: Re: recursive function that returns true/false (newbie stuff)
Date: 
Message-ID: <34CD16A3.E47E8947@infinet.com>
Kevin Goodier wrote:

> 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.