Project Euler #4 in Haskell

Project Euler #4 asks:


Find the largest palindrome made from the product of two 3-digit numbers.

The code is as follows:

module Main where

import Data.List (sortBy)
import Data.Ord (comparing)

palindromes :: [Integer]
palindromes = [calcPalindrome a b c | a  Bool
is3Digit n = n >= 100 && n  Integer -> Bool
isDiv n d = n `mod` d == 0

-- returns all multiples of 2 3-digit numbers
-- for palindromes
isMultiple :: Integer -> Bool
isMultiple n = not $ null threeMultiples
    where
        multiples :: [(Integer, Integer)]
        multiples = do
            d  is3Digit m && is3Digit n) multiples

problem4 :: Integer -> Integer
problem4 n =
    head $ filter isMultiple $ sortBy (flip compare) $ filter (< n) palindromes

main :: IO ()
main = do
    _ <- getLine
    contents <- getContents
    let cases = map read $ lines contents
    let results = map problem4 cases
    mapM_ print results

I'd appreciate comments on isMultiple and problem4 as they seem rather messy. Any other general comments are welcome too.

Proof technique

I was pleasantly surprised at the speed of this algorithm (generating all 6-digit palindromes, then taking the largest one with two 3-digit factors), as compared to the alternative approach (multiplying all 3-digit pairs, then finding the largest product that is a palindrome). I would have expected the latter to be faster, as factoring is normally a more expensive operation — but you take advantage of a clever shortcut. That, I suppose, is part of the point of Project Euler questions.

On the other hand, I would consider the program to be slightly incomplete. The property that the palindrome is divisible by 11 only holds if it contains an even number of digits. As a counterexample, 101 ∙ 101 = 10201 is a number within the parameters of the question (a palindrome that is the product of two 3-digit numbers) that is not divisible by 11. Your palindromes function only generates 6-digit candidates for consideration. While there is no need for your program to produce a result that requires no human interpretation, it would be desirable to note the assumption (or proof) of the existence of a 6-digit result, at least as a comment.

Implementation

I am puzzled by your boilerplate main function. Reading an input number as an upper bound on the palindrome candidates seems superfluous. An excessively large input won't scale the problem to cover 4-digit × 4-digit products, either, as your palindromes function is hard-coded to produce 6-digit candidates only. So, this would have sufficed:

problem4 :: Int 
problem4 = head $ filter isMultiple $ sortBy (flip compare) $ palindromes

main :: IO ()
main = do
    print problem4

Integer is overkill. The numbers involved fit very comfortably under maxBound::Int.

sortBy (flip compare) is just the same as reverse. But why reverse anything at all, when you could just generate the palindrome candidates in descending order in the first place?

palindromes :: [Int]
palindromes = [calcPalindrome a b c | a <- [9,8..1], b <- [9,8..0], c <- [9,8..0]]
    where
        calcPalindrome a b c = 100001 * a + 10010 * b + 1100 * c

is3Digit is fine, though I would find is3Digit n = 100 <= n && n < 1000 more aesthetically pleasing.

isMultiple could be better named, and the do … return would be better written as a list comprehension. (See Do notation considered harmful.)

isProductOfThreeDigitNumbers :: Int -> Bool
isProductOfThreeDigitNumbers n = not $ null threeDigitFactors
    where
        -- All palindromes with an even number of digits are divisible by 11
        factors = [(d, n `div` d) | d  is3Digit m && is3Digit n) factors

Then, problem4 would just be

problem4 :: Int
problem4 =
    head $ filter isProductOfThreeDigitNumbers $ palindromes

StackExchange Code Review Q#74665, answer score: 4