Home > Net >  Linear recursive method for counting palindrome numbers between 2 integers in Haskell
Linear recursive method for counting palindrome numbers between 2 integers in Haskell

Time:03-08

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.

  • Related