P06 – Find out whether a list is a palindrome.
Posted by rbpasker on April 16, 2009
Another easy one, we just use reverse()!
scala> def isPalindrome[T](l: List[T]) : Boolean = l match {
case Nil => true
case _::Nil => true
case h::t => (h == t.reverse.head)
}
isPalindrome: [T](List[T])Boolean
scala> isPalindrome(List(1, 2, 3, 2, 1))
res29: Boolean = true
scala> isPalindrome(List(1, 2, 3, 2, 2))
res30: Boolean = false
scala> isPalindrome(List())
res31: Boolean = true
scala> isPalindrome(List(1,2,1))
res32: Boolean = true
scala> isPalindrome(List(1,2,2))
res33: Boolean = false
And their answer is:
def isPalindrome[T](l: List[T]): Boolean = l == l.reverse
Which tells me i should have looked to see if List has a equality method, which it does: List.equals. But what we see here is not .equals but .==.
Scala departs from Java’s idea of equality by defining == not as reference equality (a==b iff a and b are references to the identical object), but as a synonym for .equals!
The Java behavior of reference equality has been moved to the .eq method.
Bob said
Your isPalindrome fails on List(1,2,3,1) because you are only checking if the head == tail and your test cases aren’t very complete. Try this one:
def isPalindrome[T](l: List[T]) : Boolean = l match {
case Nil => true
case _::Nil => true
case h::t => (h == t.reverse.head) && isPalindrome(t.reverse.tail)
}
Sorry, accidentally posted this under the wrong post.
atla said
I am sorry but this function does not what you intend it to!
isPalindrome (List(1,2,2,4,3,2,1))
gives you TRUE which is obviously wrong, with your definition of a palindrome only the head and tail element have to match… not true. See http://en.wikipedia.org/wiki/Palindrome
Hope you see this as i do.
greets
atla
atla said
You might wanna try this one, you obviously missed only the recursive call
def isPalindrome[T](l: List[T]) : Boolean = l match {
case Nil => true
case _::Nil => true
case h::t => (h == t.reverse.head) && isPalindrome (t – t.reverse.head)
}