使用foldr书写foldl [英] Writing foldl using foldr
问题描述
> In Real World Haskell, Chapter 4. Functional Programming Write foldl with foldr: The above code confused me a lot, and some guy called dps rewrote it with some meaningful name to make it clearer a bit: One guy Jef G then did a excellent job by providing a example and showint the underlying machanism step by step: But I still cannot fully understand that, here are my questions: Is there anyone who can help me? Thanks a lot! Some explanations are in order! What is the id function for? What is the role of? Why should we need it here? In the above example, id function is the accumulator in the lambda function? The accumulator is a function that is being built up via repeated function application. There's no explicit lambda, since we name the accumulator, Or as Graham Hutton would write: foldr's prototype is foldr :: (a -> b -> b) -> b -> [a] -> b A Haskell programmer would say that the type of and the first parameter is a function which need two parameters, but the step function in the myFoldl's implementation uses 3 parameters, I'm complelely confused This is confusing and magical! We play a trick and replace the accumulator with a function, which is in turn applied to the initial value to yield a result. Graham Hutton explains the trick to turn And then refactor it via the static argument transformation on Let's now rewrite Which is the same as thinking of Now we have But, we have handy already a very similar recursive function on lists, This looks like a very similar recursive scheme to our So, the universal property of folds states that: where From our earlier foldl designs, we know Which, substituting our calculated definitions of The recursive This is definitely somewhat advanced, so to deeply understand this transformation, the universal property of folds, that makes the transformation possible, I recommend Hutton's tutorial, linked below. References 这篇关于使用foldr书写foldl的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
-- file: ch04/Fold.hs
myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs = foldr step id xs z
where step x g a = g (f a x)
myFoldl stepL zeroL xs = (foldr stepR id xs) zeroL
where stepR lastL accR accInitL = accR (stepL accInitL lastL)
myFoldl (+) 0 [1, 2, 3]
= (foldR step id [1, 2, 3]) 0
= (step 1 (step 2 (step 3 id))) 0
= (step 1 (step 2 (\a3 -> id ((+) a3 3)))) 0
= (step 1 (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2))) 0
= (\a1 -> (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2)) ((+) a1 1)) 0
= (\a1 -> (\a2 -> (\a3 -> (+) a3 3) ((+) a2 2)) ((+) a1 1)) 0
= (\a1 -> (\a2 -> (+) ((+) a2 2) 3) ((+) a1 1)) 0
= (\a1 -> (+) ((+) ((+) a1 1) 2) 3) 0
= (+) ((+) ((+) 0 1) 2) 3
= ((0 + 1) + 2) + 3
id is the identity function, id x = x, and is used as the equivalent of zero when building up a chain of functions with function composition, (.). You can find it defined in the Prelude. step. You can write it with a lambda if you want:foldl f a bs = foldr (\b g x -> g (f x b)) id bs a
foldr is (a -> b -> b) -> b -> [a] -> b.foldl into foldr in the above article. We start by writing down a recursive definition of foldl:foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v [] = v
foldl f v (x : xs) = foldl f (f v x) xs
f:foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v xs = g xs v
where
g [] v = v
g (x:xs) v = g xs (f v x)
g so as to float the v inwards:foldl f v xs = g xs v
where
g [] = \v -> v
g (x:xs) = \v -> g xs (f v x)
g as a function of one argument, that returns a function:foldl f v xs = g xs v
where
g [] = id
g (x:xs) = \v -> g xs (f v x)
g, a function that recursively walks a list, apply some function f. The final value is the identity function, and each step results in a function as well. foldr!
g function. Now the trick: using all the available magic at hand (aka Bird, Meertens and Malcolm) we apply a special rule, the universal property of fold, which is an equivalence between two definitions for a function g that processes lists, stated as:
g = foldr k v
g must be equivalent to the two equations, for some k and v: g [] = v
g (x:xs) = k x (g xs)
v == id. For the second equation though, we need
to calculate the definition of k: g (x:xs) = k x (g xs)
<=> g (x:xs) v = k x (g xs) v -- accumulator of functions
<=> g xs (f v x) = k x (g xs) v -- definition of foldl
<= g' (f v x) = k x g' v -- generalize (g xs) to g'
<=> k = \x g' -> (\a -> g' (f v x)) -- expand k. recursion captured in g'
k and v yields a
definition of foldl as:foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v xs =
foldr
(\x g -> (\a -> g (f v x)))
id
xs
v
g is replaced with the foldr combinator, and the accumulator becomes a function built via a chain of compositions of f at each element of the list, in reverse order (so we fold left instead of right).
