Project Euler 4
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.
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.
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)) .
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))
上一篇: 欧拉项目8
下一篇: 欧拉项目4