[Haskell-cafe] Would you mind explain such a code ?

[Roman Cheplyaka]

* zaxis <z_axis at 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 at 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