2
\$\begingroup\$

The problem: Palindrome: Implement a function to check if a linked list is a palindrome

If it's a palindrome, the list must be the same backwards and forwards

Below is the code I wrote:

  def isPalindrome[A](list:List[A]):Boolean= (list.head, list.last)match{
    case (a,b) if a==b&&list.size>2 => isPalindrome[A](list.tail.dropRight(1))
    case (a,b) if a==b&&list.size<=2 => true
    case (a,b) if a!=b =>false
  }

May I know is there any way to improve it?

\$\endgroup\$
  • \$\begingroup\$ What's a "padorom"? \$\endgroup\$ – 200_success Dec 4 '16 at 7:14
  • \$\begingroup\$ @200_success already modified to explain the padorom \$\endgroup\$ – sweetyBaby Dec 4 '16 at 7:19
  • \$\begingroup\$ Yes, I know what a palindrome is, but what's a "padorom"? \$\endgroup\$ – 200_success Dec 4 '16 at 7:20
  • \$\begingroup\$ Sorry for mistaking the spelling, it should be palindorome :) \$\endgroup\$ – sweetyBaby Dec 4 '16 at 7:43
  • 4
    \$\begingroup\$ What's a palindorome :) ? \$\endgroup\$ – Grajdeanu Alex. Dec 4 '16 at 8:01
3
\$\begingroup\$

What you do is very inefficient. You check if the elements of the list are similar from the outside in, and that too utilising both very unintuitive pattern matching and guard clauses.

Note: You do not need to specify the type parameter A in the recursive call to isPalindrome(), as the compiler can infer that.

Your code, on simple singly linked lists, is O(n2), thanks to the repeated O(n) calls to list.last. The code that I explain and provide below runs in O(n), as reversing a list is O(n) and subsequently checking for equality is also O(n).

What is the definition of a palindrome?

While what you have mentioned is absolutely correct, there's an easier way to think about it.

A sequence is a palindrome whenever it is equal in every way to a sequence that contains the elements of the first sequence in reverse order.

That is, a list is a palindrome if and only if it is equal to its reverse.

I think that as your code already uses enough library functions, why not try this:

def isPalindrome[A](list: List[A]) = list == list.reverse

Simple, succinct, and to the point.

I'm absolutely sure your code is overcomplicated for its intended purpose, and functional programming is not just about pattern matching and recursion, it's about being able to create greater functionality from pre-existing functions.

\$\endgroup\$
1
\$\begingroup\$

Finding list.last is an O(n) operation, so this entire function, with recursion, would be O(n2). It should be achievable in O(n).

\$\endgroup\$
  • \$\begingroup\$ What if one had both head and last references? It's possible and it's most probably done that way (not sure). Then list.last (pardon the alliteration) is an O(1) operation. \$\endgroup\$ – Tamoghna Chowdhury Dec 4 '16 at 8:14
  • \$\begingroup\$ @TamoghnaChowdhury As stated in the documentation: "List has O(1) prepend and head/tail access. Most other operations are O(n) on the number of elements in the list." \$\endgroup\$ – 200_success Dec 4 '16 at 8:19
  • \$\begingroup\$ Well, I wasn't sure, so thanks for enlightening me. I thought that Scala would have a more efficient list... \$\endgroup\$ – Tamoghna Chowdhury Dec 4 '16 at 8:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.