Calculating the sum of digits without division

So I was looking at the ant puzzle (thanks reddit), and I really hated the way they calculated the sum of the digits.

In Haskell:

sumOfDigits 0 = 0
sumOfDigits n | n < 0     = sumOfDigits (abs n)
              | otherwise = r + sumOfDigits q
  where (q,r) = n `quotRem` 10

It just seemed inelegant - there must be a way to find the sum of the digits without using division and modulus. Especially since
I'll be doing it over and over, for a bunch of sequential numbers.

Consider two sequential numbers.

• Most of the time the difference in the sum of their digits is just one.
• Except when we move from x9 to (x+1)0, then the difference is 8
• Except when we move from x99 to (x+1)00, then the difference is 17
• ...
• Except when we move from x999..9 to (x+1)000..0, then the differce is 9t-1

So in general, the difference between the sum of digits between x and x+1 is 1, minus 9 every tenth,
minus another 9 every hundredth, etc.

This sounds like something I can just calculate:

... zipWith subtract (every 1000 9) . zipWith subtract (every 100 9) . zipWith (every 10 9) $ repeat 1
  where every n k = replicate (n-1) 0 ++ (k : every n k)

Except I've got an infinite number of zipWiths to go through before I get to my most common case. Maybe what I need to do is invert it - start with the most common case on the outside, and have my less common cases inside.

At this point, note that we if we take the list of differences, subtract nine from each, and then put nine ones between each, we get the list of differences back:

listOfDiffs :: [Int]
listOfDiffs = concat $ nineOnes : map (\a -> (a - 9) : nineOnes) listOfDiffs
  where nineOnes = replicate 9 1

This seems like something I can generalize:

spread :: (a -> a) -> [a] -> [a]
spread f as = as'
  where as' = concat $ as : map (\a -> f a : as) as'

listOfDiffs :: [Int]
listOfDiffs = spread (subtract 9) (replicate 9 1)

Giving a simple way to enumerate all the sums of digits for all the numbers:

sumOfDigits :: [Int]
sumOfDigits = scanl (+) 0 listOfDiffs