Scala Problem Number Six

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…

Advertisements
This entry was posted in scala and tagged , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s