Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Question about Real World Haskell (David Frey)
2. Re: Question about Real World Haskell (Patrick LeBoutillier)
3. Re: Compile type Error (Chadda? Fouch?)
4. Understanding cached fibonnacci function (Patrick LeBoutillier)
5. Re: Understanding cached fibonnacci function
(Rafael Gustavo da Cunha Pereira Pinto)
6. Re: Understanding cached fibonnacci function (Ertugrul Soeylemez)
7. Re: Re: Understanding cached fibonnacci function (Daniel Fischer)
8. Re: Re: Understanding cached fibonnacci function
(Patrick LeBoutillier)
9. Re: Re: Understanding cached fibonnacci function (Thomas Davie)
----------------------------------------------------------------------
Message: 1
Date: Thu, 29 Jan 2009 15:27:37 -0800
From: David Frey <[email protected]>
Subject: Re: [Haskell-beginners] Question about Real World Haskell
To: [email protected]
Cc: [email protected]
Message-ID: <dcc70e48121ccb11ef99f8161b698...@localhost>
Content-Type: text/plain; charset="UTF-8"
On Thu, 29 Jan 2009 15:21:24 +0000, Alan Cameron <[email protected]>
wrote:
> In Chapter 3 of Real World Haskell it is not clear to me how to get the
> myInfo into the ghci system there appears to be two definitions for
> ch03/BookStore.hs can anyone help?
>
> Alan Cameron
>
I assume you are referring to this:
-- file: ch03/BookStore.hs
data BookInfo = Book Int String [String]
deriving show
... Book text here ...
-- file: ch03/BookStore.hs
data MagazineInfo = Magazine Int String [String]
deriving show
... More book text here ...
-- file: ch03/BookStore.hs
myInfo = Book 9870135072455 "Algebra of Programming"
["Richard Bird", "Oege de Moor"]
When the book mentions a filename, that means that what follows is from
that file, but may only be a piece of that file. Save all of these pieces
into a file named BookStore.hs and then run "ghci BookStore.hs" in the
same directory as the file.
------------------------------
Message: 2
Date: Thu, 29 Jan 2009 20:05:51 -0500
From: Patrick LeBoutillier <[email protected]>
Subject: Re: [Haskell-beginners] Question about Real World Haskell
To: David Frey <[email protected]>
Cc: [email protected], [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
> When the book mentions a filename, that means that what follows is from
> that file, but may only be a piece of that file. Save all of these pieces
> into a file named BookStore.hs and then run "ghci BookStore.hs" in the
> same directory as the file.
You can find the entire source code from the book here:
http://examples.oreilly.com/9780596514983/rwh-examples2.zip
Patrick
--
=====================
Patrick LeBoutillier
Rosemère, Québec, Canada
------------------------------
Message: 3
Date: Fri, 30 Jan 2009 06:14:45 +0100
From: Chadda? Fouch? <[email protected]>
Subject: Re: [Haskell-beginners] Compile type Error
To: Daniel Fischer <[email protected]>
Cc: [email protected], "emmanuel.delaborde"
<[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=UTF-8
On Thu, Jan 29, 2009 at 7:33 PM, Daniel Fischer
<[email protected]> wrote:
>
> Convert lazy to strict ByteStrings before using md5sum
>
Or you could use Data.Digest.Pure.MD5 instead of
Data.Digest.OpenSSL.MD5, it takes lazy bytestring too.
--
Jedaï
------------------------------
Message: 4
Date: Thu, 29 Jan 2009 13:18:32 -0500
From: Patrick LeBoutillier <[email protected]>
Subject: [Haskell-beginners] Understanding cached fibonnacci function
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Hi all,
I recently stumbled on this example in some wiki:
mfib :: Int -> Integer
mfib = (map fib [0 ..] !!)
where fib 0 = 0
fib 1 = 1
fib n = mfib (n-2) + mfib (n-1)
I don't understand how the results get cached. When mfib is
recursively called, doesn't a new (map fib [0 ..] !!) start over
again? Or perhaps I'm thinking too imperatively here...
Also, if I change the definition to this (adding "a" on both sides):
mfib :: Int -> Integer
mfib a = (map fib [0 ..] !!) a
where fib 0 = 0
fib 1 = 1
fib n = mfib (n-2) + mfib (n-1)
the funtion becomes slow again. Why is that?
Thanks a lot,
Patrick LeBoutillier
--
=====================
Patrick LeBoutillier
Rosemère, Québec, Canada
------------------------------
Message: 5
Date: Fri, 30 Jan 2009 07:39:08 -0200
From: Rafael Gustavo da Cunha Pereira Pinto
<[email protected]>
Subject: Re: [Haskell-beginners] Understanding cached fibonnacci
function
To: Patrick LeBoutillier <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
I don't know exactly how to explain it, but it has to do with memoization
The first version generates a fully memoized function, while the second
creates a memoized version for each call, since the thunk and memoization
for fib is destroyed after each computation.
This is not a precise explanation, but I can't think of a better way to put
it...
On Thu, Jan 29, 2009 at 16:18, Patrick LeBoutillier <
[email protected]> wrote:
> Hi all,
>
> I recently stumbled on this example in some wiki:
>
> mfib :: Int -> Integer
> mfib = (map fib [0 ..] !!)
> where fib 0 = 0
> fib 1 = 1
> fib n = mfib (n-2) + mfib (n-1)
>
> I don't understand how the results get cached. When mfib is
> recursively called, doesn't a new (map fib [0 ..] !!) start over
> again? Or perhaps I'm thinking too imperatively here...
>
> Also, if I change the definition to this (adding "a" on both sides):
>
> mfib :: Int -> Integer
> mfib a = (map fib [0 ..] !!) a
> where fib 0 = 0
> fib 1 = 1
> fib n = mfib (n-2) + mfib (n-1)
>
> the funtion becomes slow again. Why is that?
>
>
> Thanks a lot,
>
> Patrick LeBoutillier
>
> --
> =====================
> Patrick LeBoutillier
> Rosemère, Québec, Canada
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
--
Rafael Gustavo da Cunha Pereira Pinto
Electronic Engineer, MSc.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20090130/548aedb7/attachment-0001.htm
------------------------------
Message: 6
Date: Fri, 30 Jan 2009 15:59:02 +0100
From: Ertugrul Soeylemez <[email protected]>
Subject: [Haskell-beginners] Re: Understanding cached fibonnacci
function
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=US-ASCII
Daniel Fischer <[email protected]> wrote:
> Not to forget the marvellous
>
> import Control.Monad.Fix
>
> fibs :: [Integer]
> fibs = fix ((0:) . scanl (+) 1)
I don't like that one. My favorite is the following, because it's
short, concise and still very comprehensible:
import Data.Function
fibs :: Num i => [i]
fibs = fix (\r x y -> x : r y (x+y)) 0 1
Replace 0 by 1, if you want to exclude it from the sequence. I prefer
to include it.
Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/
------------------------------
Message: 7
Date: Fri, 30 Jan 2009 16:24:07 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Re: Understanding cached fibonnacci
function
To: Ertugrul Soeylemez <[email protected]>, [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Am Freitag, 30. Januar 2009 15:59 schrieb Ertugrul Soeylemez:
> Daniel Fischer <[email protected]> wrote:
> > Not to forget the marvellous
> >
> > import Control.Monad.Fix
> >
> > fibs :: [Integer]
> > fibs = fix ((0:) . scanl (+) 1)
>
> I don't like that one. My favorite is the following, because it's
> short, concise and still very comprehensible:
>
> import Data.Function
>
> fibs :: Num i => [i]
> fibs = fix (\r x y -> x : r y (x+y)) 0 1
But that's too easy to understand!
What a waste of fix, sheesh ;-)
My favourite is
fibs = 0:1:zipWith (+) fibs (tail fibs)
clear, elegant, accessible. But I also like the other one, precisely because,
unless one is very experienced, one has to do a few rounds of "Wait, how on
earth does this work?" before it clicks.
>
> Replace 0 by 1, if you want to exclude it from the sequence. I prefer
> to include it.
Yep. Much more natural if the powers match the index.
>
>
> Greets,
> Ertugrul.
Cheers,
Daniel
------------------------------
Message: 8
Date: Fri, 30 Jan 2009 11:41:29 -0500
From: Patrick LeBoutillier <[email protected]>
Subject: Re: [Haskell-beginners] Re: Understanding cached fibonnacci
function
To: Ertugrul Soeylemez <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
>> fibs = fix ((0:) . scanl (+) 1)
>
> I don't like that one. My favorite is the following, because it's
> short, concise and still very comprehensible:
>
> import Data.Function
>
> fibs :: Num i => [i]
> fibs = fix (\r x y -> x : r y (x+y)) 0 1
Can someone please explain this one? I can't seem to figure out what
'fix' does (the definition in the documentation is a bit to
mathematically inclined for me...).
Thanks,
Patrick
--
=====================
Patrick LeBoutillier
Rosemère, Québec, Canada
------------------------------
Message: 9
Date: Fri, 30 Jan 2009 17:55:25 +0100
From: Thomas Davie <[email protected]>
Subject: Re: [Haskell-beginners] Re: Understanding cached fibonnacci
function
To: Patrick LeBoutillier <[email protected]>
Cc: [email protected], Ertugrul Soeylemez <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset=WINDOWS-1252; format=flowed;
delsp=yes
On 30 Jan 2009, at 17:41, Patrick LeBoutillier wrote:
>>> fibs = fix ((0:) . scanl (+) 1)
>>
>> I don't like that one. My favorite is the following, because it's
>> short, concise and still very comprehensible:
>>
>> import Data.Function
>>
>> fibs :: Num i => [i]
>> fibs = fix (\r x y -> x : r y (x+y)) 0 1
>
> Can someone please explain this one? I can't seem to figure out what
> 'fix' does (the definition in the documentation is a bit to
> mathematically inclined for me...).
It computes a fixed point for a function that is a value which when
passed to the function gives back the same answer. Some examples:
fix id any value is a fixed point for id, no matter what you give
it, it always comes back the same!
fix (+ 1) no values, no matter what you give it, it'll always come
out one bigger, so there's no fixed point here
fix (1:) the infinite list of 1s, if you put a 1 on the front of it,
you get back the inifinite list of ones again.
fix (\r x y -> x : r y (x+y)) Lets try giving this function to
itself: (\r x y -> x : (y : r (x+y) (y+(x+y)))), and again... (\r x y -
> x : (y : ((x+y) : r (y+(x+y)) ((x+y)+y+(x+y))))... you can see
where this is going, if we apply this to 0 and 1, we get 0 : 1 :
(0+1) : (1 + (0 + 1)) : ... fibonacci numbers.
In general, we can write *any* recursive function using the fix
function, we transform the function to accept another argument first,
we replace all recursive calls with calls to this argument, and we
wrap it in the fix function.
Hope that helps.
Bob
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 7, Issue 27
****************************************
