question from Yet Another Haskell Tutorial

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

question from Yet Another Haskell Tutorial

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.  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?

Thanks,
Mike





Reply | Threaded
Open this post in threaded view
|

question from Yet Another Haskell Tutorial

Daniel Fischer-4
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
>


Reply | Threaded
Open this post in threaded view
|

question from Yet Another Haskell Tutorial

Michael Mossey


Daniel Fischer wrote:

> 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.
>
>> 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 for the information, glad to know I was correct.

I agree that YAHT is excellent... I am working from several books and
tutorials simultaneously to get various perspectives, and YAHT covers
much of the same material as the books, but in a more compact form, with
good exercises.

-Mike

Reply | Threaded
Open this post in threaded view
|

Re: question from Yet Another Haskell Tutorial

Benjamin L. Russell
In reply to this post by Daniel Fischer-4
On Sun, 29 Mar 2009 14:45:22 +0200, Daniel Fischer
<[hidden email]> wrote:

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

Thank you both, Michael and Daniel.  I have compiled the information
in this thread into a new page, "Errata," in the YAHT Wikibook,
covering discrepancies between the original PDF and corrected HTML
versions of YAHT:

Haskell/YAHT/Errata - Wikibooks, collection of open-content textbooks
http://en.wikibooks.org/wiki/Haskell/YAHT/Errata

Please feel free to add to it or to correct it as would benefit
students of Haskell.

-- Benjamin L. Russell
--
Benjamin L. Russell  /   DekuDekuplex at Yahoo dot com
http://dekudekuplex.wordpress.com/
Translator/Interpreter / Mobile:  +011 81 80-3603-6725
"Furuike ya, kawazu tobikomu mizu no oto."
-- Matsuo Basho^