Custom 'fold' function needs counter

Question

My homework went really well until I stumpled upon the last task.
First, I had to define a custom List structure:

data List a = Nil | Cons a (List a) deriving Show

Another task was to write a custom fold function:

foldList :: (a -> b -> b) -> b -> List a -> b
foldList f b Nil        = b
foldList f b (Cons a l) = f a (foldList f b l)

The second parameter is the value that is used at the end of the list (at a Nil element).

I also had to write a function prodList that multiplies every element of the provided list with each other:

prodList :: List Int -> Int
prodList = foldList (\x y -> x * y) 1

The 1 at the end is the neutral element of multplication. It therefore has no effect on the calculation.

The last one, though, is hard for me to solve.
I have to write a function binList that calculates the decimal value of list that represents a binary number. The least significant bit is the first element of the list, the binary number is therefore reversed.
A given example is that the result of binList (Cons 1 (Cons 0 (Cons 0 (Cons 0 (Cons 1 Nil))))) should be 19 (since (10001)_2 is (19)_10). The result of the list [1,1,0,1], however, should be (1011)_2=(11)_10).
The culprit of the assignment is, that we have to use foldList.

I know how to calculate each digit, but I struggle to find a way to find out which index i I'm currently at:

binList :: List Int -> Int
binList = foldList (\x y -> 2^i*x + y)

There probably is a nice, curry way to solve this in Haskell. Could you explain to me how you would solve this assignment?

Answer 1

If you were to write out the calculation, it would look like this:

x0 + 2 * x1 + 4 * x2 + 8 * x3 + ...

This might suggest you need to use the index, but if you factorize this expression, you get this instead:

x0 + 2 * (x1 + 2 * (x2 + 2 * (x3 ...

Do you see how it can be written as a fold now? Notice that there is a self-similarity that looks kind of like this:

x + 2 * x'

Hopefully that's enough of a hint for you :)