[Haskell-beginners] question from Yet Another Haskell Tutorial

[Daniel Fischer]

Am Sonntag 29 März 2009 08:33:13 schrieb Michael Mossey:
> I have a question about a problem in Yet Another Haskell Tutorial
> (problem 7.1). My answers seems to disagree with Hal's, and it fact
> something looks wrong in Hal's answer (maybe it's an error in his
> paper).  The problem is to write the following function in "point-free"
> style:
>
> func5 f list = foldr (\x y -> f(y,x)) 0 list
>
> Here's how I approached it. It's easy to drop 'list' by the
> eta-reduction (using partial application):
>
> func5 f = foldr (\x y -> f(y,x)) 0
>
> But how to get rid of f? First I reasoned that f is a function of a
> tuple. That is, it is not curried. So to curry it:
>
> func5 f = foldr (\x y -> (curry f) y x) 0
>
> The second argument to foldr is obviously flipping the arugments, so
>
> func5 f = foldr (flip $ curry f) 0
>
> Now I want to use the eta-reduction again, but I have to transform 
this
> expression into something that takes f as its last argument instead of
> the 0. I can use flip again, this time on foldr:
>
> func5 f = flip foldr 0 (flip $ curry f)
>
> Now f can be dropped:
>
> THE FINAL ANSWER: func5 = flip foldr 0 . flip. curry
>
> This works, in a couple of my test cases.

As it should, since it is correct.

A simple way to check for sanity of the results is:

Prelude> :t flip foldr 0 . flip. curry
flip foldr 0 . flip. curry :: (Num c) => ((c, b) -> c) -> [b] -> c

Prelude> :t \f list -> foldr (\x y -> f (y,x)) 0 list
\f list -> foldr (\x y -> f (y,x)) 0 list :: (Num b) =>
                                             ((b, a) -> b) -> [a] -> b

Prelude> :t \f -> foldr (uncurry $ flip f) 0
\f -> foldr (uncurry $ flip f) 0 :: (Num b1) =>
                                    (b -> a -> b1 -> b1) -> [(a, b)] -> b1

So you see that your result has the correct type, while Hal's hasn't.

> Now Hal gives this as the
> answer:
>
> func5 = foldr (uncurry $ flip f) 0
>
> The first problem is that there's no argument f, though he refers to 
it.
> So maybe he meant
>
> func5 f = foldr (uncurry $ flip f) 0
>
> But more problems. He's applying flip to f, but f takes only one
> argument (a 2-tuple). Then he's uncurry-ing it, but I thought it 
needed
> currying, not uncurry-ing.
>
> Can anyone figure out what Hal is up to, or does it look like a simple
> mistake?

Simple mistake. YAHT was never systematically proofread to catch all 
such mistakes, so there are several still in. Nevertheless, it is an 
excellent tutorial.

>
> Thanks,
> Mike
>