foldl компилируется, но не foldr

Question

Как небольшое упражнение, я пытаюсь перекодировать все. Этот код, кажется, работает (для бесконечного списка, за исключением):

allComp f acc x = acc && f x 

all :: (a -> Bool) -> [a] -> Bool 
all f xs = foldl (allComp f) True xs 

Но один не компилируется, если я держу такую ​​же подпись:

allComp f acc x = acc && f x 

all :: (a -> Bool) -> [a] -> Bool 
all f xs = foldr (allComp f) True xs 

и ошибка компиляции:

Couldn't match type `a' with `Bool' 
    `a' is a rigid type variable bound by 
     the type signature for all :: (a -> Bool) -> [a] -> Bool 
     at Main.hs:8:8 
Expected type: Bool -> Bool 
    Actual type: a -> Bool 
In the first argument of `allComp', namely `f' 
In the first argument of `foldr', namely `(allComp f)' 
In the expression: foldr (allComp f) True xs 

Может ли кто-нибудь объяснить более четко, почему первая версия компилируется, но не вторая?

Answer 1

Если вы делаете поиск по Hoogle вы увидите, что подпись foldl и foldr отличаются:

foldl :: (a -> b -> a) -> a -> [b] -> a 
foldr :: (a -> b -> b) -> b -> [a] -> b 

Теперь давайте подпись более семантически звук:

foldl :: (a -> b -> a) -> a -> [b] -> a 
foldr :: (b -> a -> a) -> a -> [b] -> a 

Вы видите что порядок типов в первом аргументе (функция) различается. Это происходит потому, что foldl выглядит следующим образом:

foldl f z [x1,x2,...,xn] = f (f (f (... (f z x1) x2) x3)...) xn 

тогда foldr выглядит следующим образом:

foldr f z [x1,x2,...,xn] = f z (f x1 (f x2 (... (f xn-1 xn) ...))) 

Поскольку (&&) ассоциативно, что не имеет большого значения. Вы можете просто сменить его на flip :: (a -> b -> c) -> b -> a -> c:

all f xs = foldr (flip (allComp f)) True xs