I'm solving a practice problem in Haskell where I'm trying to count the palindrome numbers between 2 given integers. Single-digit numbers are palindromes. I've tried solving it with a helper function but I can't make it take the smaller number from the main function. Any help would be appreciated! So far I typed this:
main :: IO()
main = do
print $ countPalindromes 5 13 == 5 -- 6 7 8 9 11
print $ countPalindromes 13 5 == 5 -- 6 7 8 9 11
rev :: Int -> Int
rev n = helper n 0
where
helper :: Int -> Int -> Int
helper 0 result = result
helper n result = helper (div n 10) (result * 10 mod n 10)
isPalindrome :: Int -> Bool
isPalindrome x = rev x == x
countPalindromes :: Int -> Int -> Int
countPalindromes a b
| a > b = helper b a 0
| otherwise = helper a b 0
where
helper :: Int -> Int -> Int -> Int
helper a b count
| a <= b && isPalindrome (a - 1) = count 1
| otherwise = helper (a - 1) b count
CodePudding user response:
That's not your problem. The problem is that helper a b count
only returns count 1
if a
is a palindrome, without ever checking if a 1
, a 2
, etc, are palindromes as well. When the first number is a palindrome, it returns 0 1 == 1
and done. (Your definition of helper
is also counting the wrong way; it's decrementing a
instead of incrementing as you need to do if you ever want a <= b
to be false.)
helper
needs to recurse whether or not a
is a palindrome; the only difference is in the value of its third argument.
helper a b count | a > b = count -- base
| isPalindrome a = helper (a 1) b (count 1)
| otherwise = helper (a 1) b count
Note that b
never changes; it doesn't need to be an argument to helper
. Instead, you can make a recursive call to countPalindromes
to ensure a < b
:
countPalindromes :: Int -> Int -> Int
countPalindromes a b
| a > b = countPalindromes b a
| otherwise = helper a 0
where
helper :: Int -> Int -> Int
helper a count
| a > b = count -- base case
| isPalindrom a = helper (a 1) (count 1)
| otherwise = helper (a 1) count
Tail recursion also isn't terribly important in Haskell. You can write helper
more naturally
helper a | a > b = 0
| isPalindrome a = 1 helper (a 1)
| otherwise = helper (a 1)
Note, too, that the only difference between isPalindrome
returning True
or False
is whether you add 1
or 0
to the recursive return value. You can capture that with fromEnum
:
helper a | a > b = 0
| otherwise = (fromEnum (isPalindrome a)) helper (a 1)
As an exercise, note that you don't need explicit recursion at all. You can use filter
to get the values in range that are palindromes, then simply count the number of values in the resulting list.