Verifying foldl implementation in terms of foldr
I want to verify following implementation of foldl in terms foldr is correct:
foldl4 = foldr . flip
I used following tests in HUGS:
foldl4 (+) 3 []
foldl4 (+) 3 [1,2,3]
They worked.
Please suggest any more tests I could do.
Thanks
here is a simple test: foldl (flip (:)) [] should be reverse ...
if you want to test foldr vs foldl you probably should not use commutative operations ;)
here is some proof straight from GHCi:
λ> foldl (flip (:)) [] [1..5]
[5,4,3,2,1]
λ> foldl4 (flip (:)) [] [1..5]
[1,2,3,4,5]
and as flip (+) = (+) you can guess straight from your definition:
foldl4 (+) y xs
{ def }
= foldr (flip (+)) y xs
{ flip (+) = (+) }
= foldr (+) y xs
if you want some hint of how to do foldl with foldr : you should use functions for the accumulator/state/b part of foldr :: (a -> b -> b) -> b -> [a] -> b - think of continuation passing and try to replace the : in
x : (y : (z : [])
with some smart function to get
((b `f` x) `f` y) `f` z
remember you want to mimick
foldl f b [x,y,z] = ((b `f` x) `f` y) `f` z
with foldr which basically replaces : with it's first parameter and [] with it's second if you pass [x,y,z] as the 3rd:
foldr f' b' [x,y,z] = x `f'` (y `f'` (z `f'` b'))
and you now want to shift the parens
Those two are not the same. foldl and foldr do semantically different things, but flip only induces a syntactic difference, so foldr . flip foldr . flip cannot ever ever be foldl .
Something that is foldl for example (on finite lists) is
foldl5 = (.) (. reverse) . foldr . flip
That first part might look confusing, but it basically applies reverse to the third argument rather than the first.
上一篇: foldl和foldr等价的充分条件
下一篇: 用foldr验证foldl的实现