[Haskell-cafe] Would you mind explain such a 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 know myFoldl implements foldl using foldr. However i really donot know how it can do it ? Please shed a light one me, thanks! -- View this message in context: http://www.nabble.com/Would-you-mind-explain-such-a-code---tp25377949p25377949.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
Re: [Haskell-cafe] Would you mind explain such a code ?
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---tp25377949p25378268.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
Re: [Haskell-cafe] Would you mind explain such a code ?
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). 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
Re: [Haskell-cafe] Would you mind explain such a code ?
* 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
Re: [Haskell-cafe] Would you mind explain such a code ?
On Thu, Sep 10, 2009 at 11:47 AM, Roman Cheplyaka r...@ro-che.info 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) 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? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Would you mind explain such a code ?
* Peter Verswyvelen bugf...@gmail.com [2009-09-10 14:43:10+0200] On Thu, Sep 10, 2009 at 11:47 AM, Roman Cheplyaka r...@ro-che.info 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Would you mind explain such a code ?
On Thu, Sep 10, 2009 at 14:43, Peter Verswyvelen wrote: 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) 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? In some functional programming languages, these are not equivalent. For example, Clean does not have currying, so f :: Int Int - Int f x y = x + y is not the same as f :: Int - Int - Int f x = (+) x Notice the difference in types. The first is more like 'f :: (Int, Int) - Int' in Haskell. Sean ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
