Check if an array is a palindrome in pure immutable Scala

Problem

A palindrome is a sequence of things that is the same when reversed.

For example, 'aabb' is not a palindrome, 'ababb' is not a palindrome, but 'aba', 'abba' are.

This problem is similar to CheckStringIsAPalindrome and CheckNumberIsAPalindrome

Solution

def isArrayPalindrome[T](array: Array[T]): Boolean =
  array.view
    .zip(array.reverse.view)
    .forall({
      case (a, b) =>
        a == b
    })

Test cases

assert(
  isArrayPalindrome(Array(1, 2, 1)),
  "Array of integers is a palindrome"
)
assert(
  isArrayPalindrome(Array('a', 'b', 'a')),
  "Array of Char is a palindrome"
)
assert(isArrayPalindrome(Array(1, 2, 2, 1)), "Even Array is a palindrome")
assert(!isArrayPalindrome(Array(1, 2, 1, 2)), "Array is not a palindrome")

Scala Concepts

Pattern Matching

Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.

assert("Hello World".collect {
  case character if Character.isUpperCase(character) => character.toLower
} == "hw")

assert("Hello World".filter(Character.isUpperCase).map(_.toLower) == "hw")

assert((1 to 10).collect {
  case num if num % 3 == 0 => "Fizz"
  case num if num % 5 == 0 => "Buzz"
}.toList == List("Fizz", "Buzz", "Fizz", "Fizz", "Buzz"))

Pattern matching is used by methods like Collect, but can also be easily integrated into normal functions.

Pattern matches are effectively "Partial Functions", of type PartialFunction[Input, Output] which is isomorphic to Input => Option[Output]. See Option Type.

View

The .view syntax creates a structure that mirrors another structure, until "forced" by an eager operation like .toList, .foreach, .forall, .count.

In the example below, we can see the view in action:

var counted = 0

val resultingList = List(1, 2, 3, 4).view
  .map { num =>
    counted = counted + 1
    num + 1
  }
  .take(2)
  .toList

assert(resultingList == List(2, 3))

assert(counted == 2)

If we add a side-effect inside a map (don't do this normally!), We note that items 3 and 4 are never touched/evaluated, meaning we perform a "lazy" computation.

This is very similar to an Iterator, except views can be Indexed, and also reversed, which is a tremendously useful fact when dealing with arrays, for example when you want to zip two arrays together, such as in CheckArrayIsAPalindrome

On views, you can perform almost any typical collection operation, such as `maxBy`, `count`, `flatMap` and so forth.

And you can get views from almost any data type. Benefits other than lazy computation include potentially fusing of operations by the Java compiler, because instead of creating a new list for every stage, you evaluate new items one-by-one, meaning that if there are any optimisations to be made per one-item basis, you may get a performance boost.

Zip

'zip' allows you to combine two lists pair-wise (meaning turn a pair of lists, into a list of pairs)

It can be used over Arrays, Lists, Views, Iterators and other collections.

assert(List(1, 2, 3).zip(List(5, 6, 7)) == List(1 -> 5, 2 -> 6, 3 -> 7))

assert(List(1, 2).zip(List(5, 6, 7)) == List(1 -> 5, 2 -> 6))

assert(List(5, 6).zipWithIndex == List(5 -> 0, 6 -> 1))

Explanation

The more standard solution is to check Array indices directly, but there is a Scala-idiomatic solution which lets you do it without checking array sizes and indices and so forth.

You could directly compare the array against its reverse, but this means passing through the array three times: once to reverse, and then twice to zip up the array with its reverse, and then compare.

In Scala, 'indexed views' provide you with the ability to map an Array to its reverse, and then 'zip' the two arrays together so that you can then compare the last item of the array against the first, one before last with one after after first and so on, thereby doing the check of whether the array is indeed a palindrom