Why the foldr function gives me a negative result when the list contains a zero?-CodePudding

Here an example to illustrate what I mean

Prelude> foldr (-) 0 [0,1]  
-1

I thought here it would basically do 0 - 0 = 0; 1 - 0 = 1; but the actual result is -1

I tried it with other examples

Prelude> foldr (-) 1 [1,3]   
-1

Prelude> foldr (-) 1 [1,9]
-7

I probably misunderstood how foldr works so I would be happy about an explanation :)

CodePudding user response：

Consider the following function:

printfoldr f init xs = foldr (\el acc -> "("    el    f    acc    ")") (show init) $ map show xs

This function simulates how the foldr function expands and outputs its string representation.

Let's run a few tests:

λ> printfoldr "-" 0 [1,2,3,4]
"(1-(2-(3-(4-0))))"

-- the test cases you provided
λ> printfoldr "-" 0 [1,2]
"(1-(2-0))" -- This reduces to -1 which is the result you had

λ> printfoldr "-" 1 [1,3]
"(1-(3-1))" -- This reduces to -1 which is also the result you had

λ> printfoldr "-" 1 [1,9]
"(1-(9-1))" -- reduces -7 which is also correct

So in general, foldr with type foldr :: (a -> b -> b) -> b -> t a -> b works as follows:

x0 `f` (x1 `f` ...(xn-2 `f` (xn-1 `f` (xn `f` init))))

where f is of type (a -> b -> b), x is of type a and init is of type b.

CodePudding user response：

Try foldr (-) 0 [1, 2, 3, 4, 5]. You should get 3. That's because the fold is equivalent to (1 - (2 - (3 - (4 - (5 - 0))))) -- it's starting from the right. If you try foldl, you should get -15. That's because it's starting from the left and is equivalent to (((((0 - 1) - 2) - 3) - 4) - 5).

Your shorter example, foldr (-) 0 [0, 1], is equivalent to 0 - (1 - 0), which reduces to -1.

CodePudding user response：

foldr is defined as follows:

foldr f b [] = b
foldr f b (x:xs) = f x (foldr f b xs)

You recursively fold the tail of the list, then apply f to the head and the recursive result. Note that the base value is used at the end of the sequence, not the beginning.

Thinking of it as simply applying the function to one value after another only works if f is associative. For example, 1 (2 (3 0)) == ((1 2) 3) 0.

Subtraction, though, is not associative. In general, x - y - z is only equal to (x - y) - z, not x - (y - z).