recursive function that returns true/false (newbie stuff)
Kevin Goodier
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).
Erik Naggum
* 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/
Kevin Goodier
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
bk...@cec.wustl.edu
http://students.cec.wustl.edu/~bkg2/
Erik Naggum
* 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 Naggum
* 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...
Tim Bradshaw
* 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
Bruce Tobin
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.