How can I fold with state in Haskell?

Question

I have a simple function (used for some problems of project Euler, in fact). It turns a list of digits into a decimal number.

fromDigits :: [Int] -> Integer
fromDigits [x] = toInteger x
fromDigits (x:xs) = (toInteger x) * 10 ^ length xs + fromDigits xs

I realized that the type [Int] is not ideal. fromDigits should be able to take other inputs like e.g. sequences, maybe even foldables ...

My first idea was to replace the above code with sort of a "fold with state". What is the correct (= minimal) Haskell-category for the above function?

Answer 1

You should avoid the use of length and write your function using foldl (or foldl'):

fromDigits :: [Int] -> Integer
fromDigits ds = foldl (\s d -> s*10 + (fromIntegral d)) 0 ds

From this a generalization to any Foldable should be clear.