From the Scala 99 Problems, lets face the problem number six:
- P06 (*) Find out whether a list is a palindrome.
- Example:
scala> isPalindrome(List(1, 2, 3, 2, 1))
res0: Boolean = true
The first thing I had to do was to find out the meaning of palindrome. From the example, it’s easy to guess, but I prefer to be sure. So, from dictionary.com:
1. a word, line, verse, number, sentence, etc., reading the same backward as forward, as Madam, I’m Adam or Poor Dan is in a droop.
Interesting, so this is valid not only for numbers =)
Now, to some coding! My first solution:
def isPalindrome(list: List[Any]): Boolean = list match {
case Nil => true
case head :: Nil => true
case head :: rest if head == rest.last => isPalindrome(rest.dropRight(1))
case _ => false
}
This first solution uses pattern matching to investigate the list recursively. It checks if the list is empty or if it contains only one element and returns true. Otherwise, it checks if the head of the list equals the last element. If so, the rest of the list (its middle part) is passed recursively to the function. This is one more case where we can see the great power of scala’s pattern matching in action.
Also, the solution will work with strings as well, so it matches the dictionary definition – just call toList on the string. Sample execution from the REPL:
scala> isPalindrome("oio".toList)
res11: Boolean = true
scala> isPalindrome("oioo".toList)
res12: Boolean = false
To be honest, I don’t feel too much creative when thinking about this problem, so the next solution is quite similar to the previous one, but without pattern matching:
def isPalindrome(list: List[Any]): Boolean = {
if (list.isEmpty || list.size == 1) true
else if (list.head == list.last) isPalindrome(list.slice(1, list.size-1))
else false
}
Now lets take a look at the original solution and… I’m stunned by its simplicity. While I went all fancy at things like pattern matching, the original solution goes like this:
def isPalindrome[A](ls: List[A]): Boolean = ls == ls.reverse
Yeah, I should have thought of that…
