Euler #4: Refined Palindrome in Haskell

Question

This is my attempt at the Problem Euler #4 in Haskell ("Find the largest palindrome made from the product of two 3-digit numbers.")

import Data.List
isPalindrome :: Show a => a -> Bool
isPalindrome n = l == reverse l
 where l = show n
maxPalindrome :: (Integral a, Show a) => a
maxPalindrome = maximum $ head . transpose $ allPalindrome <$> [999, 998 .. 1]
 where allPalindrome x = filter (isPalindrome) $ (x *) <$> [999, 998 .. x]

To my surprise I didn't see any such optimisation in the snippets I found (the head . transpose is there to only consider the highest of each pairs), which surprised me. However this is still running about 0.5 seconds which I find still slow?

Is there a way to make it run faster? I am aware of Project Euler #4 in Haskell however, my question is not about the algorithm I use but about its implementation.

Do you have any other recommendation about my code?

Thank you very much in advance

• Zeta: "However this is still running about 0.5 seconds which I find still slow?" How did you test that? After all, the execution time differs between interpreted and compiled. For example, in GHCi I get 0.27 seconds (consistently), whereas in a compiled variant (-O2) I end up with 0.03s (main = print maxPalindrome).
• snow_lemurian_snow: Oh sorry I imported it in ghci and used :set +s. Time was 0.8 on the first try, and 0.5 on other tries, even if I closed ghci and opened it back. I did not notice compilation could have such an important speed factor

Answer 1

Your code is fine, but I would suggest some small changes. Instead of head . transpose, I would use concatMap (take 1). This captures your intend to take the first (and therefore largest) number from each allPalindrome.

Next, I would use Int instead of (Integral a, Show a), since 999 * 999 is smaller than maxBound :: Int. Why? Because by default, Integer will be used for Integral types, if they were note specified. Therefore, you end up with maxPalindrome handled as a Integer, which is slower than Int.

And last, but not least, I would stop at 111, since 111 * 111 is a palindrome.

We end up with:

isPalindrome :: Show a => a -> Bool
isPalindrome n = l == reverse l
 where l = show n
maxPalindrome :: Int
maxPalindrome = maximum $ concatMap (take 1) $ allPalindrome <$> [999, 998 .. 111]
 where allPalindrome x = filter isPalindrome $ (x *) <$> [999, 998 .. x]
main :: IO ()
main = print maxPalindrome

Note that you should compile your code if you want to check its performance.

Alternatively, if you want to keep maxPalindrome's type, use :: Int:

maxPalindrome :: (Integral n, Show n) => n
maxPalindrome = maximum $ concatMap (take 1) $ allPalindrome <$> [999, 998 .. 111]
 where allPalindrome x = filter isPalindrome $ (x *) <$> [999, 998 .. x]
main :: IO ()
main = print (maxPalindrome :: Int)

• snow_lemurian_snow: I am confused about your comment on using Int rather than (Integral a, Show a). I thought it was a good practice to use Num a or equivalent in general, because that was more modular and could be used in any given situation ( granted it doesn't apply here, but I was curious as to wether this good practice was actually a good one at all). Thanks for concatMap (take 1), by the way, I was so focused on using head on partial values I did not realize take 1 worked too.
• Zeta: @snow_lemurian_snow in general, that's correct. You want your functions to be general. But in this case, there's no input for your maxPalindrome taht determines the resulting type, which makes it already a little bit of a hassle, since functions that have a polymorphic can mess up optimization. For example genericLength returns a Num a => a, but if you use it like let l = genericLength xs in fromIntegral l / l, you'll end up taking the length twice. Since you were interested in performance, I changed it to Int.
• snow_lemurian_snow: Alright, thank you very much, it was very clear. I will look into Integer to see how slow it is, and use Int when appropriate if I want to speed things up