Send Beginners mailing list submissions to
beginners@haskell.org
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
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Understanding cached fibonnacci function (Heinrich Apfelmus)
2. Re: Understanding cached fibonnacci function (Ertugrul Soeylemez)
3. linked lists (Matthew J. Williams)
4. Re: linked lists (David Frey)
5. Circular Linked Lists (Matthew J. Williams)
6. Re: Circular Linked Lists (Erik de Castro Lopo)
7. Re: Circular Linked Lists (Rafael Gustavo da Cunha Pereira Pinto)
8. Re: Circular Linked Lists (Dave Bayer)
9. Re: Circular Linked Lists (Brent Yorgey)
10. Re: Circular Linked Lists (John Hartnup)
----------------------------------------------------------------------
Message: 1
Date: Sat, 31 Jan 2009 11:23:29 +0100
From: Heinrich Apfelmus <apfel...@quantentunnel.de>
Subject: [Haskell-beginners] Re: Understanding cached fibonnacci
function
To: beginners@haskell.org
Message-ID: <gm18pl$hc...@ger.gmane.org>
Content-Type: text/plain; charset=ISO-8859-1
Patrick LeBoutillier wrote:
>>
>> 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...).
Well, you can just try to replace fix by its definition and see what
happens:
fix (\r x y -> x : r y (x+y)) 0 1
=
(let go = (\r x y -> x : r y (x+y)) go in go) 0 1
=
let go = \x y -> x : go y (x+y) in go 0 1
=
let go x y = x : go y (x+y) in go 0 1
In other words, fix can define a recursive function.
--
http://apfelmus.nfshost.com
------------------------------
Message: 2
Date: Sat, 31 Jan 2009 16:43:37 +0100
From: Ertugrul Soeylemez <e...@ertes.de>
Subject: [Haskell-beginners] Re: Understanding cached fibonnacci
function
To: beginners@haskell.org
Message-ID: <20090131164337.401c1...@tritium.xx>
Content-Type: text/plain; charset=UTF-8
Thomas Davie <tom.da...@gmail.com> wrote:
> >> 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!
Beware that 'fix' doesn't simply return an arbitrary fixed point. It
gives you _the_ least-defined fixed point, which is bottom for 'fix id'.
By the way, it's a very aggressive implementation of bottom. Trying to
evaluate 'fix id' may crash your system, unless you set proper memory
limits.
> fix (+ 1) â no values, no matter what you give it, it'll always come
> out one bigger, so there's no fixed point here
It does have a fixed point. Every function has a fixed point. Its
fixed point is 1+1+1+1+... It's easy to verify:
(+1) (1+1+1+1+...) = 1+1+1+1+...
However, the fixed point has the least possible definedness, which means
it's bottom.
> 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.
Same story here, but (1:) is not strict in its argument, so you get
higher definedness than bottom.
> 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.
I find it easier to explain in terms of typed lambda calculus. The
problem with it is that you can't express recursion directly in raw
lambda notation. The fixed point operator 'fix' gives you the power to
do this:
fix f = f (fix f)
If you pass a lambda to 'fix', then it results in a function, which gets
itself as its first argument, so you can express recursion. Say, you
would like to write the greatest common divisor algorithm, which is:
gcd x 0 = x
gcd x y = gcd y (x `mod` y)
Now in raw lambda calculus, you can't write equations like above. You
can only express functions in terms of their lambdas:
(\x y -> if y == 0 then x else ...)
The problem should be clear: There is no way for the function to call
itself. Now the fixed point operator comes into play. It turns the
first argument of the function into a recursive reference to itself:
fix (\recurse x y -> if y == 0 then x else recurse y (x `mod` y))
Of course, with all the expressive power you've got in Haskell, it's
never necessary and seldomly useful to use the fixed point operator.
You would write the GCD function just in the usual style. But
sometimes, particularly for infinite unfolds, it's more convenient than
'unfoldr' or 'iterate', without making code incomprehensible.
Greets,
Ertugrul.
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/
------------------------------
Message: 3
Date: Tue, 03 Feb 2009 02:01:33 +0000
From: "Matthew J. Williams" <matthewjwillia...@googlemail.com>
Subject: [Haskell-beginners] linked lists
To: beginners@haskell.org
Message-ID: <4987a57e.1f07420a.4730.2...@mx.google.com>
Content-Type: text/plain; charset="us-ascii"; format=flowed
Dear All
What would be the haskell equivalent of the C++ linked list complete
with nodes? the list structure -- x:[} -- is the closest I've found.
Sincerely
Matthew J. Williams
------------------------------
Message: 4
Date: Mon, 02 Feb 2009 18:15:27 -0800
From: David Frey <dpf...@shaw.ca>
Subject: Re: [Haskell-beginners] linked lists
To: beginners@haskell.org
Message-ID: <6f0b9611b74e935347ea6b59c8298...@localhost>
Content-Type: text/plain; charset="UTF-8"
On Tue, 03 Feb 2009 02:01:33 +0000, "Matthew J. Williams"
<matthewjwillia...@googlemail.com> wrote:
> Dear All
> What would be the haskell equivalent of the C++ linked list complete
> with nodes? the list structure -- x:[} -- is the closest I've found.
>
> Sincerely
> Matthew J. Williams
>
There are certainly some similarities between std::list from C++ and
Haskell's list, but there are also a lot of differences partly because C++
and Haskell are very different languages.
What properties of lists are you interested in comparing?
------------------------------
Message: 5
Date: Tue, 03 Feb 2009 02:45:32 +0000
From: "Matthew J. Williams" <matthewjwillia...@googlemail.com>
Subject: [Haskell-beginners] Circular Linked Lists
To: beginners@haskell.org
Message-ID: <4987afcd.130c420a.134e.4...@mx.google.com>
Content-Type: text/plain; charset="us-ascii"; format=flowed
Dear All
How would one mimic, in Haskell, a C++ circular linked list i.e.,
where the last element precedes (points to) the first?
Sincerely
Matthew J. Williams
------------------------------
Message: 6
Date: Tue, 3 Feb 2009 13:53:17 +1100
From: Erik de Castro Lopo <mle...@mega-nerd.com>
Subject: Re: [Haskell-beginners] Circular Linked Lists
To: beginners@haskell.org
Message-ID: <20090203135317.beaed216.mle...@mega-nerd.com>
Content-Type: text/plain; charset=US-ASCII
Matthew J. Williams wrote:
> How would one mimic, in Haskell, a C++ circular linked list i.e.,
> where the last element precedes (points to) the first?
Try this, "Tying the Knot":
http://www.haskell.org/haskellwiki/Tying_the_Knot
Erik
--
--
-----------------------------------------------------------------
Erik de Castro Lopo
-----------------------------------------------------------------
"I consider C++ the most significant technical hazard to the survival
of your project and do so without apologies." -- Alistair Cockburn
------------------------------
Message: 7
Date: Tue, 3 Feb 2009 11:46:06 -0200
From: Rafael Gustavo da Cunha Pereira Pinto
<rafaelgcpp.li...@gmail.com>
Subject: Re: [Haskell-beginners] Circular Linked Lists
To: beginners@haskell.org
Message-ID:
<351ff25e0902030546g774a251as22bf76805e2fd...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
Matthew,
I would strongly suggest taking a look on SPJ's presentation at OSCON 2007
(video at http://blip.tv/file/324976). He shows a very interesting circular
list (with a zipper).
Since you are interested in functional data structures, Chris Okasaki's book
"Purely Functional Data Structures" is a great source too!
On Tue, Feb 3, 2009 at 00:53, Erik de Castro Lopo
<mle...@mega-nerd.com<mle%2...@mega-nerd.com>
> wrote:
> Matthew J. Williams wrote:
>
> > How would one mimic, in Haskell, a C++ circular linked list i.e.,
> > where the last element precedes (points to) the first?
>
> Try this, "Tying the Knot":
>
> http://www.haskell.org/haskellwiki/Tying_the_Knot
>
> Erik
> --
> --
> -----------------------------------------------------------------
> Erik de Castro Lopo
> -----------------------------------------------------------------
> "I consider C++ the most significant technical hazard to the survival
> of your project and do so without apologies." -- Alistair Cockburn
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> 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/20090203/71a5c24d/attachment-0001.htm
------------------------------
Message: 8
Date: Tue, 3 Feb 2009 08:56:34 -0500
From: Dave Bayer <ba...@cpw.math.columbia.edu>
Subject: Re: [Haskell-beginners] Circular Linked Lists
To: "Matthew J. Williams" <matthewjwillia...@googlemail.com>
Cc: beginners@haskell.org
Message-ID: <19bf564d-0337-48c3-8996-8aa923998...@math.columbia.edu>
Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
On Feb 2, 2009, at 9:45 PM, Matthew J. Williams wrote:
> Dear All
> How would one mimic, in Haskell, a C++ circular linked list i.e.,
> where the last element precedes (points to) the first?
You are getting deep answers to what is perhaps a simple question. You
haven't said exactly what you want to do with a circular linked list,
and people are perhaps fearing the trickiest applications.
Have you tried the Prelude function cycle?
> cycle :: [a] -> [a]
> cycle ties a finite list into a circular one, or equivalently, the
> infinite repetition of the original list. It is the identity on
> infinite lists.
For instance, in ghci one gets
> Prelude> [1..3]
> [1,2,3]
> Prelude> take 10 $ cycle [1..3]
> [1,2,3,1,2,3,1,2,3,1]
cycle doesn't actually construct in memory a cyclic data structure, as
one might in C. It's more like those repeat bars in sheet music.
------------------------------
Message: 9
Date: Tue, 3 Feb 2009 09:17:12 -0500
From: Brent Yorgey <byor...@seas.upenn.edu>
Subject: Re: [Haskell-beginners] Circular Linked Lists
To: beginners@haskell.org
Message-ID: <20090203141712.ga24...@seas.upenn.edu>
Content-Type: text/plain; charset=us-ascii
>
> cycle doesn't actually construct in memory a cyclic data structure, as one
> might in C. It's more like those repeat bars in sheet music.
It doesn't?
cycle xs = xs' where xs' = xs ++ xs'
That sure looks like a cyclic data structure to me! xs' references a
thunk which computes (xs ++ xs'); this thunk, in turn, references
xs'. cycle is memory-efficient precisely because it *does* actually
construct a cyclic data structure.
-Brent
------------------------------
Message: 10
Date: Tue, 3 Feb 2009 14:52:33 +0000
From: John Hartnup <john.hart...@gmail.com>
Subject: Re: [Haskell-beginners] Circular Linked Lists
To: beginners@haskell.org
Message-ID:
<6c1ba2fc0902030652r36860d5na77a32f21f9cb...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
2009/2/3 Brent Yorgey <byor...@seas.upenn.edu>:
>
> cycle xs = xs' where xs' = xs ++ xs'
>
> That sure looks like a cyclic data structure to me! xs' references a
> thunk which computes (xs ++ xs'); this thunk, in turn, references
> xs'. cycle is memory-efficient precisely because it *does* actually
> construct a cyclic data structure.
That's just magnificent!
--
"There is no way to peace; peace is the way"
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 8, Issue 1
***************************************
