Define function in Haskell using foldr

Question

I'm trying to define a function in Haskell using the foldr function:

    fromDigits :: [Int] -> Int

This function takes a list of Ints (each on ranging from 0 to 9) and converts to a single Int. For example:

    fromDigits [0,1] = 10
    fromDigits [4,3,2,1] = 1234
    fromDigits [2,3,9] = 932
    fromDigits [2,3,9,0,1] = 10932

Anyway, I have no trouble defining this using explicit recursion or even using zipWith:

    fromDigits n = sum (zipWith (*) n (map ((^)10) [0..]))

But now I have to define it using a foldr, but I don't know how to get the powers of 10. What I have is:

    fromDigits xs = foldr (\x acc -> (x*10^(???)) + acc) 0 xs

How can I get them to decrease? I know I can start with (length xs - 1) but what then?

Best Regards

Answer 1

You were almost there:

your

fromDigits xs = foldr (\x acc -> (x*10^(???)) + acc) 0 xs

is the solution with 2 little changes:

fromDigits = foldr (\x acc -> acc*10 + x) 0

(BTW I left out the xs on each sides, that's not necessary.

Another option would be

fromDigits = foldl (\x acc -> read $ (show x) ++ (show acc)) 0

Answer 2

The nice thing about foldr is that it's so extemely easy to visualise!

foldr f init [a,b, ... z]
≡ foldr f init $ a : b : ... z : []
≡                a`f b`f`... z`f`init
≡ f a (f b ( ... (f z init)...)))

so as you see, the j-th list element is used in j consecutive calls of f. The head element is merely passed once to the left of the function. For you application, the head element is the last digit. How should that influence the outcome? Well, it's just added to the result, isn't it?

15 = 10 + 5
623987236705839 = 623987236705830 + 9

– obvious. Then the question is, how do you take care for the other digits? Well, to employ the above trick you first need to make sure there's a 0 in the last place of the carried subresult. A 0 that does not come from the supplied digits! How do you add such a zero?

That should really be enough hint given now.

Answer 3

The trick is, you don't need to compute the power of 10 each time from scratch, you just need to compute it based on the previous power of ten (i.e. multiply by 10). Well, assuming you can reverse the input list.

(But the lists you give above are already in reverse order, so arguably you should be able to re-reverse them and just say that your function takes a list of digits in the correct order. If not, then just divide by 10 instead of multiplying by 10.)