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 ***************************************