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))
  • 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
    Commented Apr 15, 2015 at 4:39

1 Answer 1


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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