2
\$\begingroup\$

I decided to avoid the trivial isPalindrome lst = lst == reverse lst and tried writing a method with pattern matching and recursion.

allButFirstAndLast :: [a] -> [a]
allButFirstAndLast = tail . init

isPalidrome :: [a] -> Bool
isPalidrome [] = True
isPalindrome [a] = True
isPalindrome [a,b] = a == b
isPalindrome lst = (isPalindrome (allButFirstAndLast lst)) &&
                   ((head lst) == (last lst))
\$\endgroup\$
1
  • 3
    \$\begingroup\$ IMO it's seldom a good idea to avoid trivial solutions as long as there isn't something forcing you to \$\endgroup\$
    – Random Dev
    Apr 15 '15 at 4:39
5
\$\begingroup\$

The implementation is correct, but not efficient. The problem are the calls to last and init, which are both O(n), which makes the whole function O(n^2). On the other hand, lst == reverse lst is just O(n).

See Finding palindromes in a linked list.

Also the pattern

isPalindrome [a,b] = a == b

is redundant, you can omit it and let it be handled by the generic case.

\$\endgroup\$
1
  • \$\begingroup\$ You could maintain start and end indices to avoid the n^2 issue; but that would compromise on elegance. \$\endgroup\$ Apr 20 '15 at 22:10

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.