Menu
I'm currently on chapter 4 of Real World Haskell, and I'm trying to wrap my head around implementing foldl in terms of foldr.
(Here's their code:)
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)
I thought I'd try to implement zip using the same technique, but I don't seem to be making any progress. Is it even possible?
566
If you know that you'll have to traverse the whole list no matter what (e.g., summing the numbers in a list), then foldl' is more space- (and probably time-) efficient than foldr .
To recap, with foldr , the purpose of the function argument is to take the first element of the list and the results of having folded the rest of the list, and return the new value. With foldl , the function argument takes a default value, the first element of the list, and returns a new default value.
Difference Between foldl and foldr The difference is that foldl is tail-recursive, whereas foldr is not. With foldr and non-optimized patterns, proc is applied to the current value and the result of recursing on the rest of the list. That is, evaluation cannot complete until the entire list has been traversed.
foldr takes two arguments: A combining function and an identity value. It then returns a function that takes a list and returns an accumulated value.
zip2 xs ys = foldr step done xs ys
where done ys = []
step x zipsfn [] = []
step x zipsfn (y:ys) = (x, y) : (zipsfn ys)
How this works: (foldr step done xs) returns a function that consumes ys; so we go down the xs list building up a nested composition of functions that will each be applied to the corresponding part of ys.
How to come up with it: I started with the general idea (from similar examples seen before), wrote
zip2 xs ys = foldr step done xs ys
then filled in each of the following lines in turn with what it had to be to make the types and values come out right. It was easiest to consider the simplest cases first before the harder ones.
The first line could be written more simply as
zip2 = foldr step done
as mattiast showed.
171
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
