Функция Haskell foldl (\ x y -> x * 2 + y * 2) 0 поведение

Question

Я столкнулся с проблемой. В чем разница между этими двумя функциями:

foldl (\x y -> x*2 + y*2) 0 [1,2,3] = 22 
foldr (\x y -> x*2 + y*2) 0 [1,2,3] = 34 

foldl (\x y -> x*2 + y*2) 0 [1,2,3] ⇒ f(f(f(0,1),2),3) 
foldr (\x y -> x*2 + y*2) 0 [1,2,3] ⇒ f(3,f(2, f(1,0))) 

, где f = \x y -> x*2 + y*2.

Я понимаю результат foldl:

x = f(0,1) = 2 
y = f(x,2) = 8 
z = f(y,3) = 22 

Но почему foldr сумма после результата каждого шага?

2 + 8 + 22 = 34 

Answer 1

У вас есть оценка foldr назад. Он должен выглядеть следующим образом:

foldr f 0 [1,2,3] == f 1 (f 2 (f 3 0)) 

Для контраста, то foldl оценка (что является правильным в вашем вопросе) выглядит

foldl f 0 [1,2,3] == f (f (f 0 1) 2) 3 

Если вы чувствуете себя комфортно думать о списке [1,2,3] как то же самое, 1:2:3:[], эта схема foldr может помочь:

Answer 2

Ваше определение foldr немного не работает. Вместо f(3,f(2, f(1,0))) оно должно быть f(1,f(2, f(3,0))).

foldl f z [1,2,3] = ((0 `f` 1) `f` 2) `f` 3 
        = ((0*2 + 1*2) `f` 2) `f` 3 
        = (2 `f` 2) `f` 3 
        = (2*2 + 2*2) `f` 3 
        = 8 `f` 3 
        = 8*2 + 3*2 
        = 22 

foldr f z [1,2,3] = 1 `f` (2 `f` (3 `f` 0)) 
        = 1 `f` (2 `f` (3*2 + 0*2)) 
        = 1 `f` (2 `f` 6) 
        = 1 `f` (2*2 + 6*2) 
        = 1 `f` 16 
        = 1*2 + 16*2 
        = 34