Haskell reverse Integer with recursion

Tag: haskell , recursion Author: gerryleo Date: 2013-10-21

I want to reverse an Integer in Haskell with recursion. I have a small issue.

Here is the code :

reverseInt :: Integer -> Integer
reverseInt n
|  n>0 = (mod n 10)*10 + reverseInt(div n 10)
|  otherwise = 0

Example 345

I use as input 345 and I want to output 543

In my program it will do....

reverseInt 345
mod 345 10 -> 5
reverseInt 34
mod 34 10 -> 4
reverseInt 3
mod 3 10 -> 3
reverseInt 0
0=0 (ends)

And at the end it returns the sum of them... 5+4+3 = 12.

So I want each time before it sums them, to multiple the sum * 10. So it will go...

5*10 + 4
54*10 + 3

Best Answer

Here's a relatively simple one:

reverseInt :: Int -> Int
reverseInt 0 = 0
reverseInt n = firstDigit + 10 * (reverseInt $ n - firstDigit * 10^place)
    n' = fromIntegral n
    place = (floor . logBase 10) n'
    firstDigit = n `div` 10^place


  1. You take the logBase 10 of your input integer, to give you in what place it is (10s, 100s, 1000s...)
  2. Because the previous calculation gives you a floating point number, of which we do not need the decimals, we use the floor function to truncate everything after the decimal.
  3. We determine the first digit of the number by doing n 'div' 10^place. For example, if we had 543, we'd find place to be 2, so firstDigit = 543/100 = 5 (integer division)
  4. We use this value, and add it to 10 * the reverse of the 'rest' of the integer, in this case, 43.

Edit: Perhaps an even more concise and understandable version might be:

reverseInt :: Int -> Int
reverseInt 0 = 0
reverseInt n = mod n 10 * 10^place + reverseInt (div n 10)
    n' = fromIntegral n
    place = (floor . logBase 10) n'

This time, instead of recursing through the first digit, we're recursing through the last one and using place to give it the right number of zeroes.


Thanks a lot Alex. I have to say it was a bit complicated as an idea but simple and with a nice explanation. Thanks again.

Other Answer1

reverseInt :: Integer -> Integer
reverseInt n = snd $ rev n
                 rev x
                   |  x>0 = let (a,b) = rev(div x 10)
                            in ((a*10), (mod x 10)*a + b)
                   |  otherwise = (1,0)

Explanation left to reader :)


Excuse me, but where is the explanation? Sorry, I am new on forum. I don't know what "let .... in" does. Neither the "$"
The trick is that each recursion also return another number which describe the multiplication with 10 at that level so that prev level can use this number and multiply it with 10 and return result of that to above level and so on
Thanks you for your answer. Your code is almost what I need. I just don't know what the $ does and the let....in. We haven't learn this so far. How can we replace this with something more simple?
snd $ rev n can be replace with snd (rev n) and let is like creating local variables
Thanks a lot for your help Ankur. I googled and but we haven't still learned this. It just returns the second number of a (a,b). let (a,b) = rev(div x 10) --> created two local variables. Why are we using = rev(div x 10). And on in((a*10), (mod x 10)*a + b) --> Whats the value of a? Can you show me step to step how it goes?

Other Answer2

I don't know convenient way to found how many times you should multiply (mod n 10) on 10 in your 3rd line. I like solution with unfoldr more:

import Data.List
listify = unfoldr (\ x -> case x of
                             _ | x <= 0 -> Nothing
                             _          -> Just(mod x 10, div x 10) )

reverse_n n = foldl (\ acc x -> acc*10+x) 0 (listify n)

In listify function we generate list of numbers from integer in reverse order and after that we build result simple folding a list.


Thanks for the answer. I must not use a list. If I could use it would be easy. I have to make it work only with recursion and if (|).
+1 for using a nice hylomorphism!

Other Answer3

Or just convert it to a string, reverse it and convert it back to an integer:

 reverseInt :: Integer -> Integer
 reverseInt = read . reverse . show


Neither String can be used.

Other Answer4

More (not necessarily recursion based) answers for great good!

reverseInt 0 = 0
reverseInt x = foldl (\x y -> 10*x + y) 0 $ numToList x
    numToList x = if x == 0 then [] else (x `rem` 10) : numToList (x `div` 10)

This is basically the concatenation of two functions : numToList (convert a given integer to a list 123 -> [1,2,3]) and listToNum (do the opposite).

The numToList function works by repeatedly getting the lowest unit of the number (using rem, Haskell's remainder function), and then chops it off (using div, Haskell's integer division function). Once the number is 0, the empty list is returned and the result concatenates into the final list. Keep in mind that this list is in reverse order!

The listToNum function (not seen) is quite a sexy piece of code:

foldl (\x y -> 10*x + y) 0 xs

This starts from the left and moves to the right, multiplying the current value at each step by 10 and then adding the next number to it.

I know the answer has already been given, but it's always nice to see alternative solutions :)


Oh, and if you haven't seen $ before - it can be thought of as "put brackets from here to the end of the line". So foo $ x + y === foo (x + y) and foo $ bar $ x + y === foo (bar (x+y))