Converting Integer into list of digits without 'mod' and 'div'

Question

I currently have the Haskell function below which converts an integer into a list of digits taken from the original integer. My question is thus: Is there a way to do this without using mod and div? For example, if I wanted to do the same thing with a string I could create a function utilising other functions such as head and tail etc.

I struggled with this problem for a while before finally come to SO and finding the answer in another post. What got me asking this question is the fact that I would have never thought of using mod and div myself!

toDigits :: Integer -> [Integer]
toDigits n 
 | n < 1 = []
 | otherwise = toDigits (n `div` 10) ++ [n `mod` 10]

Answer 1

You mentioned that you could do the same thing on strings with list operations. Indeed, that would be another way. You could convert the integer to a string and then convert each character to an integer:

import Data.Char (digitToInt)

toDigits :: Int -> [Int]
toDigits = map digitToInt . show

Here I used Int rather than Integer, but you can use Integer if you really want with a little more trouble:

toDigits :: Integer -> [Integer]
toDigits = map (fromIntegral . digitToInt) . show

Answer 2

@icktoofay's answer uses show, a generic way to convert some value to a String (in other words, get its string representation). A value should be of a type that is an instance of a typeclass Show. For example, Int is an instance of Show (enter :i Int in ghci and seek for a string instance Show Int -- Defined in `GHC.Show'). But a function isn't an instance of Show, so let f n = n in f will throw an error, because how would you convert a function to a string? (See also: If functions as instances of the Show typeclass). Anyway, using show function is idiomatic, so you can stick to it.

There is however a way to extract a digit from a number using logarithms, powers and integer divisions. Remember that you can remove digits from the left by finding a remainder, and remove digits from the right by integer division. In both cases, the right operand is some power of 10. For example:

*Main> 123 `mod` 10
3
*Main> 123 `div` 100
1

But how do you know, which power of 10 you should use to divide by? By finding a logarithm base 10: #digits of N = log₁₀N + 1, e.g. log₁₀12345 = 4. Unfortunately you can't use logBase, because it uses floating point arithmetic, which is inaccurate. For example:

*Main> logBase 10 1000
2.9999999999999996

You can use custom function iLogBase for integers—copy the code from the link into your source code. This way to find a first digit of a number I use the following code:

firstDigit :: (Integral a) => a -> a
firstDigit n = n `div` (10^log)
  where log = fst $ iLogBase 10 n

Creating a more general function of finding an arbitrary digit of a number and converting a number into a list of digits is left to you as an exercise :).

Also, the code in your question is inefficient. List concatenation (++) operation has the complexity of O(n), that is, every time you want to append an element to and end of list, it has to add the left list to the right list one by one, until you have a resulting list. Check out the source for (++), basically [1,2,3] ++ [4] becomes 1 : 2 : 3 : [4], which is terribly inefficient, as it takes 3 cons (:) operations just to add a list. And as you append numbers to the end multiple times, it has to repeat the same process each time, therefore overall complexity of your function is O(n^2).

On the other hand (:) is instant, that is, has complexity of O(1). No matter how long is your list, prepending an element to the beginning is cheap. So instead of adding an element to the end, I would recommend, adding it to the beginning and an the end simply reversing the list once (for information, Lisp people call this push/nreverse idiom):

reverse $ (n `mod` 10) : toDigits (n `div` 10)