Haskell-Project Euler 4

Question

I am very new to Haskell and i thought that to get a hang of writing haskell programs,i might solve some project euler problems.

So i went on with it and implemented the problem number 4 of Project Euler.

The problem Statement:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

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

But there seems to be something wrong with my solution.

Here it is:

projectEuler4 :: (Ord a,Num a) => a 

projectEuler4 = max palindromeList
  where palindromeList = [reverse(x*y)|x<-[1..999],y <- [1..999]]

GHCI gives me this error:

ProjectEuler4.hs:2:17:
Could not deduce (a ~ ([[a0]] -> [[a0]]))
from the context (Ord a, Num a)
  bound by the type signature for
             projectEuler4 :: (Ord a, Num a) => a
  at ProjectEuler4.hs:1:18-35
  `a' is a rigid type variable bound by
      the type signature for projectEuler4 :: (Ord a, Num a) => a
      at ProjectEuler4.hs:1:18
In the return type of a call of `max'
Probable cause: `max' is applied to too few arguments
In the expression: max palindromeList
In an equation for `projectEuler4':
    projectEuler4
      = max palindromeList
      where
          palindromeList
            = [reverse (x * y) | x <- [1 .. 1000], y <- [1 .. 1000]]

I dont know what this means and am frustrated for not finding the reason for the error. Any help will be appreciated.Thanks.

---

So After reading some of the answers and comments, i did something like This:

projectEuler4 :: (Ord a,Num a) => a 
projectEuler4 = max' palindromeList
    where palindromeList = [reverse(show(x*y))|x<-[1..999],y <- [1..999]]

max' :: (Ord a) => [a] -> a
max' [] = error "Empty List"
max' [p] = p
max' (p:ps) = max p (max' ps)   

Still doesn't work.

---

OK..

BY following @bheklilr's advice, i changed my program:

products :: [Integer] -> [Integer] -> [Integer]
products ns ms = [x * y | x <- ns, y <- ms]

isPalindrome :: Integer -> Bool
isPalindrome n = let s = show n in s == reverse s

palindromes :: [Integer]
palindromes = maximum filter (isPalindrome "") (products [100..999] [100..999])

Now what do i put in place of the inverted comma? I am seriously confused.

Answer 1

The first big error is that you're calling

reverse (x * y)

Since x * y is a number, and reverse only works on lists, this won't compile. You can convert the number to a String (which is a list) with show:

reverse $ show $ x * y

However, reversing the string is not what you really want to do, you want to filter find all the palindromes, so you need to filter your list of (x * y)s by a predicate. Instead you could write

palindromeList = [z | x <- [1..999], y <- [1..999], let z = x * y, if show z == reverse (show z)]

But since this marches off the side of the screen, I would recommend breaking it up into smaller functions

-- Generates all products
products :: [Integer] -> [Integer] -> [Integer]
products ns ms = [x * y | x <- ns, y <- ms]

-- Checks if a number is a palindrome
isPalindrome :: Integer -> Bool
isPalindrome n = let s = show n in s == reverse s

-- Generates problem-specific palindromes
palindromes :: [Integer]
palindromes = ??? -- Implementation here.  Hint: filter

The next big problem is because you're using the max function, which has the type

max :: Ord a => a -> a -> a

But we really want to find the max of a list, so we turn to maximum, which has the type

maximum :: Ord a => [a] -> a

So you can finalize your program as

projectEuler4 :: Integer
projectEuler4 = maximum palindromes

One final thought: the problem says that you need to find the largest palindrome that is a multiple of 2 three-digit numbers, but your range that you're looking over is [1..999], which includes 1 and 2 digit numbers. What could you do to not check those? Conveniently, it'll make the program faster.

Answer 2

Prelude> :t max
max :: (Ord a) => a -> a -> a

That's the type of max. When you call it on some argument of type a, you get a result of type a -> a - a function. That is because max is normally called with two values; partial application results in a function which still waits for the second argument before calculating the result, the biggest of two values.

The error shows that Haskell has deduced the type of palindromeList as [[a0]] so the result's type is [[a0]] -> [[a0]]. You gave it as (Ord a,Num a) => a and Haskell can't match the two.

What you intended was to use maximum, which processes a list and finds the biggest value in it:

Prelude> :t maximum
maximum :: (Ord a) => [a] -> a

The definition of palindromeList is wrong too. For starters, the numbers from 1 through 99 in [1..999] are not triple-digit numbers. Then you need to test them. reverse (x*y) of course is wrong: reverse :: [a] -> [a] but result of multiplication of two numbers is a number, but - this is still not a test even when you fix it.

A test is something like show (x*y) == reverse (show (x*y)).

Answer 3

You are trying to reverse a number with:

reverse(x*y)

reverse only works on lists. Fortunately, a String is a list, and show is the canonical way to create the String representation of a value.

So try something like:

reverse (show (x*y))

Answer 4

You are asked to find the largest product of two three-digit numbers that is palindromic. The program will generate a list of palindromic numbers and find the maximum of that list. The first step is to generate the terms of the product, call them x and y. This is accomplished using the generators x <- [100..999] and y <- [x..999]. Note that if we are considering a particular value of x, we only need to consider values of y that are greater than or equal to x; if not, we repeat ourselves. Next, we need to determine whether xy is palindromic. The easiest way to accomplish this is to convert xy into a string, call it s, and then check whether reverse s == s holds. To do this, use show :: Show a = a -> String. The maximum of the generated list can be found with the function maximum :: Ord a => [a] -> a.

euler4 :: Integral a => a
euler4 = maximum [ x * y | x <- [100..999], y <- [x..999], palindromic (x * y) ]
  where palindromic n = show n == reverse (show n)

There are several problems with your code. First, projectEuler4 should be an integer value, and all integer values are already instances of Ord and Num. The correct constraint is Integral a => a. This will give the choice of Int or Integer. Second, max :: Ord a => a -> a -> a gives the maximum of two members of the Ord type class, rather than the maximum of the elements of a list Third, reverse :: [a] -> [a] operates on lists, not numeric values; you will need to convert x * y to a String before applying it to reverse. Fourth, y <- [999] means that y is is generated from the singleton list containing just 999, not the list of numbers from x to 999 or 100 to 999.

The Haskell tutorial at haskell.org has a good overview of list comprehensions. I would also look for overviews of the Haskell type system, and learn to use the interactive GHC environment - especially the command :t (if you're unsure about a function's type and unfamiliar with the standard library).