How to express a foldl-based code with foldr?-CodePudding

I am attempting to convert a list of integers into a single integer using the foldr function. I have seen implementations that use the foldl function but am trying to figure out how to do the same thing using foldr.

The output should look something like:

list2int [0,1,2,3,0,4,5]
>123045

My code:

list2int :: [Int] -> Int
list2int = foldr (\x acc -> acc*10   x) 0

However, when I run the code above using the same input, it returns 5403210. .

CodePudding user response：

Let's run through what happens with your function when you fold over [0, 1, 2, 3, 4, 0, 5]:

foldr (\x acc -> acc*10   x) 0 [0, 1, 2, 3, 4, 0, 5]
foldr (\x acc -> acc*10   x) 5 [0, 1, 2, 3, 4, 0]
foldr (\x acc -> acc*10   x) 50 [0, 1, 2, 3, 4]
foldr (\x acc -> acc*10   x) 504 [0, 1, 2, 3]
foldr (\x acc -> acc*10   x) 5043 [0, 1, 2]
foldr (\x acc -> acc*10   x) 50432 [0, 1]
foldr (\x acc -> acc*10   x) 504321 [0]
foldr (\x acc -> acc*10   x) 5043210 []
5043210

But what if we provide foldr with a tuple, containing our accumulator, and a base to multiply each digit by?

Our initial value will be a base of 1 and an accumulator of 0: (1, 0). Each time through, we'll multiply the base by 10.

Prelude> foldr (\x (base, acc) -> (base * 10, acc   x * base)) (1, 0) [0, 1, 2, 3, 0, 4, 5]
(10000000,123045)
Prelude>

Now, consider what happens:

foldr (\x (base, acc) -> (base * 10, acc   x * base)) (1, 0) [0, 1, 2, 3, 0, 4, 5]
foldr (\x (base, acc) -> (base * 10, acc   x * base)) (10, 5) [0, 1, 2, 3, 0, 4]
foldr (\x (base, acc) -> (base * 10, acc   x * base)) (100, 45) [0, 1, 2, 3, 0]
foldr (\x (base, acc) -> (base * 10, acc   x * base)) (1000, 45) [0, 1, 2, 3]
foldr (\x (base, acc) -> (base * 10, acc   x * base)) (10000, 3045) [0, 1, 2]
foldr (\x (base, acc) -> (base * 10, acc   x * base)) (100000, 23045) [0, 1]
foldr (\x (base, acc) -> (base * 10, acc   x * base)) (1000000, 123045) [0]
foldr (\x (base, acc) -> (base * 10, acc   x * base)) (10000000, 123045) []
(10000000, 123045)

This basic pattern of using a tuple to pass state through iterations of a fold may be useful to you in the future.

Now we just need to extract the second number in this tuple, and you have the desired result.

It's also possible to pass the base, and multiply the current number by 10 raised to that base, starting with a base power of 0.

Prelude> foldr (\x (basePow, acc) -> (basePow   1, acc   x * 10 ** basePow)) (0, 0) [0, 1, 2, 3, 0, 4, 5]
(7.0,123045.0)
Prelude>

CodePudding user response：

I don't really recommend this, but it exists.

ghci> foldr (\x k acc -> k $! (10 * acc   x)) id [0,1,2,3,0,4,5] 0
123045

The reason I don't recommend it is that it's roughly the same thing as inlining the definition of foldl', but harder to read.

And this is really a problem that should use foldl' to solve. It associates the operation the correct direction and has the correct strictness. Problems like this are the whole reason it exists.