By Leonardo Giordani Published on Last update on

# 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
}
}
```

which works as expected

```scala> val head fl last = List(1,2,3)
last: Any = 3
scala> val head fl last = List(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.