Why it is not possible to override (implement) foldr in terms of foldl

Question

We have what can be realized from the point of view . This is explained in detail in the Study Guide on the versatility and expressiveness of folds . The article states that: foldlfoldr

In contrast, it is impossible to redefine foldin terms foldldue to the fact that it foldlis strict at the tail of its list argument, but is foldnot.

However, I do not see how this is proof of the impossibility of a definition foldrin terms foldl(note that foldthere is a synonym in the original article foldr). I am very puzzled, trying to understand how rigor plays a role here. Can anyone expand on this explanation?

Answer 1

In the future, I will refer to foldhow foldr(since this is what it is called in the standard Haskell libraries).

---

Take another look at the definition foldl,

foldl :: (β -> α -> β) -> β -> [α] -> β
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs

note that the base case requires the list argument to be []- in all other cases, the list is evaluated in WNHF, and we immediately use the tail of the list recursively. This establishes the fact that foldlis strict in its (last) list argument.

Now we can write the version foldrusing foldl, but it will only work on lists of finite length. See this page for motivation.

foldr' :: (α -> β -> β) -> β -> [α] -> β
foldr' f v xs = foldl (\g u x -> g (f u x)) id xs v 

, head, ¹ .

import Control.Applicative ((<|>))

safeHead :: [α] -> Maybe α
safeHead = foldr (\x y -> Just x <|> y) Nothing

foldr foldl - foldr', safeHead [1..]. safeHead , foldl .

---

¹ Prelude, listToMaybe

Answer 2

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f acc [] = acc
foldr f acc (x : xs) = f x (foldr f acc xs)

, , foldr , f. Haskell , foldr . f ( x, , ), foldr call " ", .

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acc [] = acc
foldl f acc (x : xs) = foldl (f acc x) xs

( ) foldl , f . f , ; foldl , , , .

, , foldr ; , , (acc). , GHCi:

Prelude> foldr (\x acc -> if x > 10 then "..." else show x ++ ", " ++ acc) "STOP" [1..5]
"1, 2, 3, 4, 5, STOP"

Prelude> foldr (\x acc -> if x > 10 then "..." else show x ++ ", " ++ acc) "STOP" [1..]
"1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ..."

foldr if x , ( acc ).

, , . , foldr , foldr , , , :

Prelude> take 10 $ foldr (\x acc -> x + 100 : acc) [] [1..]
[101,102,103,104,105,106,107,108,109,110]

foldr , map, 100 , , take 10 10 . , " " :.

( ) foldl, , foldl, , "" ; foldl , -, foldl. , , foldl, , foldl , , foldr.

( ); , foldl , foldr, , , .