* zaxis <z_a...@163.com> [2009-09-10 00:51:21-0700] > > thanks for your quick answer! > > As I understand foldr (\x g -> g . (`f`x)) id xs will return a function > such as (`f` 3).(`f` 2).(`f` 1) . You have already made it clear ! However, > why does the "step" function below has three parameters ? I think foldr > will call step using two parameters, the 1st is list element and the 2nd is > a funtion whose initial value is id).
That's right. step x g a = g (f a x) is, thanks to currying, another way to write step x g = \a -> g (f a x) This is what we want -- function of two arguments, which returns a new value of accumulator (which in this case is a function itself). And g (f a x) can be rewritten as g ((f a) x) = g (a `f` x) = g ((`f` x) a) = (g . (`f` x)) a, thus step x g = \a -> g (f a x) = \a -> (g . (`f` x)) a = g . (`f` x) (the last step is called 'eta-reduction'). Remember that g is a previous value of accumulator and step x g is its new value, so on each step we compose accumulator with (`f` x) to get the new value. So in the end it will look like you wrote above. > myFoldl f z xs = foldr step id xs z > where step x g a = g (f a x) > > > staafmeister wrote: > > > > > > > > zaxis wrote: > >> > >> 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 know myFoldl implements foldl using foldr. However i really donot know > >> how it can do it ? > >> > >> Please shed a light one me, thanks! > >> > > > > Hi, > > > > Nice example! Well this is indeed an abstract piece of code. But basically > > foldl f z xs starts with z and keeps applying (`f`x) to it > > so for example foldl f z [1,2,3] = ((`f`3).(`f`2).(`f`1)) z > > > > Because functions are first-class in haskell, we can also perform a foldl > > where instead of calculating the intermediate values we calculate the > > total function, i.e. ((`f`3).(`f`2).(`f`1)) and apply it to z. > > > > When the list is empty z goes to z, so the start function must be id. > > So we can write > > (`f`3).(`f`2).(`f`1) = foldr (\x g -> g . (`f`x)) id xs > > > > This is almost in your form. > > > > Hope this helps, > > Gerben > > > > -- > View this message in context: > http://www.nabble.com/Would-you-mind-explain-such-a-code---tp25377949p25378882.html > Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe -- Roman I. Cheplyaka :: http://ro-che.info/ "Don't let school get in the way of your education." - Mark Twain _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe