#6 of 99 Problems – is a list a palindrome in scala

This post and the original question are licensed under a Creative Commons Attribution-Share Alike license and all code is released to the public domain.

This is more involved than previous problems. We are checking if a list is a palindrome and we will do this, as in previous problems, using pattern matching on the List. I use 3 scenarios which would be ifs in Java.

  1. If the list is less than 2 items it is empty or has 1 item. I count these as being palindromes.
  2. If the head (first item) and the last (last item) are the same then it might be – let’s recurse 🙂
  3. If 2 items or more and first and last differ then return false.

This means using an if in our case to check first and last items in the 2nd scenario.

A note on pattern matching: The line of code below will create 2 values from the list – head and tail – where head is the first item and tail is everything else. It makes matching and recursion simpler.

case head::tail => // do something...

Anyway, here’s the code:

Question:
Find out whether a list is a palindrome.
Example:

var result = isPalindrome(List(1, 2, 3, 2, 1))
println("Result = " + result)

Output: Result = true

Answer:

import scala.annotation.tailrec

object Class06 extends App {

  var result = isPalindrome(List(1, 2, 3, 2, 1))
 
  @tailrec // we expect tail-recursive optimization
  def isPalindrome(l:List[Any]):Boolean = l match {
    case yes if(l.length < 2) => true  // true if small enough
    case head::tail if (head==tail.last) => isPalindrome(tail.init) // recurse without first and last
    case _ =>  false // this is like an else
  }   

  println("Result = " + result)
}

Original Question here: http://aperiodic.net/phil/scala/s-99/

This shows some of the features of pattern matching in scala. The word yes is just a name I’ve given to the first case which runs off the if condition. There is a convention to use an underscore for catch-all cases, a convention I follow here. The original list of questions doesn’t show anything beyond list==list.reverse but I think this answer is a good example of recursion and pattern matching.

Advertisements

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