# 99 Scala Problems 06 - Find out whether a list is a palindrome

## The problem

**P06** (*) Find out whether a list is a palindrome.

Example:

```
scala> isPalindrome(List(1, 2, 3, 2, 1))
res0: Boolean = true
```

## Initial thoughts

The algorithm is pretty simple. A list is palindrome when it is equal to its reversed version. So both a procedural and a recursive solution may get a reversed version of the list and then compare the two.

For long lists this could be a performance issue, so a recursive solution could be interesting. It is sufficient to check if head and tail are equal, then remove them and recursively check the remaining list. The last step will either check a list of one element or an empty list (depending on the length of the list being odd or even), which are both palindrome by definition.

## The procedural solution

```
def isPalindrome[A](l: List[A]):Boolean = {
l == l.reverse
}
```

Nothing special to highlight here.

## The recursive solution

The recursive solution may mimic the procedural implementing a helper function that reverses the list. See problem 05 for an implementation of such a function.

A recursive solution for the palindrome check shall make use of functions to extract the head and tail elements from the list. Since pattern matching cannot separate the tail element, we have to use `List`

type methods.

```
def isPalindrome[A](l: List[A]):Boolean = l match {
case Nil => true
case List(a) => true
case list => (list.head == list.last && isPalindrome(list.tail.init))
}
```

The corresponding tail recursive function is

```
def isPalindrome[A](l: List[A]):Boolean = {
def _palindrome(res: Boolean, rem: List[A]): Boolean = rem match {
case Nil => res
case List(a) => res
case list => _palindrome(res && rem.head == rem.last, rem.tail.init)
}
_palindrome(true, l)
}
```

## A custom operator

Scala version 2.10+ define an extractor for pattern matching last element of a list, which is `:+`

. The souce code can be found here-

Since I am using Scala 2.9 I want to use this occasion to learn how to implement an operator for the pattern matching.

First of all: I recommend reading the following pages Case Classes and Pattern Matching, List patterns, Extractors. They describe in a very simple and clear way everything you need to know at this point about pattern matching and further clarify what discussed in problem 05 about the `::`

class.

The version proposed in Issue 2575 works only on `List`

types but is a good starting point for me

```
object :+ {
def unapply[A] (l: List[A]) = l match {
case Nil => None
case _ => Some( (l.init, l.last) )
}
}
```

This allows to use the `:+`

pattern matching operator (namely an *extractor*) to do something like

```
scala> val init :+ tail = List(1,2,3)
init: List[Int] = List(1, 2)
tail: Int = 3
```

As a matter of fact the concept is very simple, even if its implementation is very rich and powerful. The `unapply()`

method deconstructs the incoming value returning an `Option`

, either `None`

if the value does not match the format or `Some()`

with a tuple of extracted values.

Following the above example I come up with a first-last extractor `fl()`

```
object fl {
def unapply[A] (l: List[A]) = l match {
case Nil => None
case l => Some(l.head, l.last)
}
}
```

which works as expected

```
scala> val head fl last = List(1,2,3)
head: Any = 1
last: Any = 3
scala> val head fl last = List(1)
head: Int = 1
last: Int = 1
```

To use it in the `isPalindrome()`

recursive function, however, I need something that also returns the list without the first and the last element.

```
object frl {
def unapply[A] (l: List[A]) = l match {
case Nil => None
case l if (l.length == 1) => Some(l.head, l.last, List())
case l => Some(l.head, l.last, l.init.tail)
}
}
```

This cannot however be used as an infix operator, because it has three input values, so pattern matching will use the standard call form

```
scala> val frl(first, last, rem) = List(1,2,3,4,5)
first: Int = 1
last: Int = 5
rem: List[Int] = List(2, 3, 4)
```

With this extractor my recursive function is greatly simplified

```
def isPalindrome[A](l: List[A]):Boolean = l match {
case Nil => true
case frl(first, last, rem) => (first == last) && isPalindrome(rem)
}
```

and its corresponding tail recursive form is

```
def isPalindrome[A](l: List[A]):Boolean = {
def _palindrome(res: Boolean, rem: List[A]): Boolean = rem match {
case Nil => res
case frl(first, last, rem) => _palindrome(res && first == last, rem)
}
_palindrome(true, l)
}
```

## Final considerations

The palindrome problem was straightforward, but this time I had the occasion to understand **pattern matching operators** and **extractors**.

## Feedback

Feel free to use the blog Google+ page to comment the post. The GitHub issues page is the best place to submit corrections.

## Part 6 of the "99 Scala Problems" series

##### Previous articles

- 99 Scala Problems 01 - Find the last element of a list
- 99 Scala Problems 02 - Find the last but one element of a list
- 99 Scala Problems 03 - Find the Kth element of a list
- 99 Scala Problems 04 - Find the number of elements of a list
- 99 Scala Problems 05 - Reverse a list

##### Next articles

- 99 Scala Problems 07 - Flatten a nested list structure
- 99 Scala Problems 08 - Eliminate consecutive duplicates of list elements
- 99 Scala Problems 09 - Pack consecutive duplicates of list elements into sublists
- 99 Scala Problems 10 - Run-length encoding of a list.
- 99 Scala Problems 11 - Modified run-length encoding
- 99 Scala Problems 12 - Decode a run-length encoded list
- 99 Scala Problems 13 - Run-length encoding of a list (direct solution)
- 99 Scala Problems 14 - Duplicate the elements of a list
- 99 Scala Problems 15 - Duplicate the elements of a list a given number of times
- 99 Scala Problems 16-20