* zaxis [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---tp25377949p253788... 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

* Peter Verswyvelen [2009-09-10 14:43:10+0200]

On Thu, Sep 10, 2009 at 11:47 AM, Roman Cheplyaka wrote:

...

 step x g a = g (f a x)

is, thanks to currying, another way to write

 step x g = \a -> g (f a x)

I thought currying just meant

curry f x y = f (x,y)

Here you use 'currying' meaning the process of applying the 'curry' operation, i.e. transforming 'uncurried' function to a 'curried' one. (BTW, Wikipedia agrees with you.)

Isn't the reason that

f x y z = body

is the same as

f = \x -> \y -> \z -> body

just cause the former is syntactic sugar of the latter?

Technically, yes. Generally speaking, currying is the idea of interchangeability of the function which takes several arguments and the function which returns another function (i.e. what is used here). -- Roman I. Cheplyaka :: http://ro-che.info/ "Don't let school get in the way of your education." - Mark Twain