isPalindrome :: Integer -> Bool
isPalindrome n = reverse x == x
    where x = show n 

is3x3 :: Integer -> Bool
is3x3 n = any (\x -> cond1 x && cond2 x) [101..999]
        cond1 x = n `mod` x == 0
        cond2 x = length (show $ n `div` x) == 3

main = print $ head [p | p <- [999^2,999^2-1..], isPalindrome p, is3x3 p]

I have some doubts about the code I wrote:

  1. isPalindrome: is it ok or is it better to keep dividing by 10, storing the remainder in a list and check if list is equal to the reversed self?
  2. is3x3: is it a good practice to declare functions inside functions? Is there a better way to write the function?
  3. how to delete the parentheses in cond2? $ doesn't work because of ==
  4. [999^2,999^2-1..]:
    • is Haskell smart and calculates 999^2 only once, subtracting 1 every time? Or does it compute 999^2-x for each xth+1 element of the list?
    • is there a better way to write this list?
    • is it better to put the end of the list (in this case 10001) or it doesn't matter in terms of performance? I know lists are lazy but ...
  • \$\begingroup\$ Solving projecteuler.net/problem=4 ? \$\endgroup\$ – Martin R Apr 3 '16 at 11:56
  • \$\begingroup\$ yep, but I avoided putting the name of the problem in order not to spoiler \$\endgroup\$ – Pigna Apr 3 '16 at 12:17
  1. isPalindrome is ok here, no need to make it faster.
  2. In functional programming functions are everywhere, even inside other functions and this is ok. Using ViewPatterns extension it is possible to rewrite is3x3 as:

    is3x3 n = any cond [101..999]
            cond (divMod n -> (d, 0)) = 99 < d && d <= 999
            cond _ = False
  3. I don't know any readable way to rewrite cond2 without parenthesis.

  4. Haskell is smart enough to calculate 999^2 and 999^2-1 at compile time. In terms of performance, if you don't specify end of the list there will be no checks for the end of the list at runtime (which is good in this case).

Using Integer is justified only for big numbers, in your case using Int is enough and could be a bit faster.

Here is another solution:

main = print $ maximum
  [ x * y :: Int
  | x <- [999, 998 .. 100]
  , y <- [x, x-1 .. 100]
  , (==) <*> reverse $ show $ x * y
| improve this answer | |
  • \$\begingroup\$ Thank you! As for the solution you proposed (which is also what 200_success♦ proposed), isn't it slower? I guess it's more idiomatic, but the algorithm is slower. I just timed it with time in terminal. It should even slower with bigger numbers. \$\endgroup\$ – Pigna Apr 4 '16 at 8:41
  • \$\begingroup\$ You are right, it could be much slower depending on number of palindromes and actual value of solution (whether it closer to the 999^2 or to the 100^2). Alternative solution has better asymptotic complexity which is not always related to real performance. \$\endgroup\$ – max taldykin Apr 4 '16 at 9:27
  • \$\begingroup\$ Silly me. If I had remembered what I had written before, I wouldn't have proposed filtering the products instead of filtering the palindromes. \$\endgroup\$ – 200_success Apr 4 '16 at 14:59

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.